algoNote

プログラミング関連

セグメントツリーを勉強した

セグメントツリーを勉強したのでメモとしてコードを載せておきます。

区間add - 区間sum

RSQ and RAQ | Aizu Online Judge

列に対して次の2種類のクエリを処理します。

  1. 区間[l,r]に値xを一様に加える
  2. 区間[l,r]の値の和を求める

lazy[v] := 頂点vの区間に足されている値 とするセグメントツリーを作ります。

区間update - 区間min

RMQ and RUQ | Aizu Online Judge

列に対して次の2種類のクエリを処理します。

  1. 区間[l,r]のすべての値をxに更新する
  2. 区間[l,r]の値の最小値を求める

lazy[v] := 頂点vの区間をすべて上書きする値 とするセグメントツリーを作ります。

区間add - 区間max

  1. 区間[l,r]のすべての値にxを加える
  2. 区間[l,r]の値の最大(最小)値を求める

これらのクエリを処理するセグメントツリーをStarry Sky Treeと呼ぶらしいです。実装は上の2つを組み合わせるだけです。

code-festival-2015-final-open.contest.atcoder.jp

押すボタンを決めたら、誰が押すかは関係が無いので、押している区間が最大でいくつ被っているかがわかればいいです。

N-1点以上取るために必要な人数の最小値が欲しいので、どれか1つ押さない場合について考えます。

はじめにすべて押すと仮定してStarrySkyTreeですべての区間に+1しておいて、押さないボタンを決めたらその区間を-1して最大を計算、を繰り返します。

Codeforces Round #149 Div2 E.XOR on Segment

codeforces.com

与えられる数列a[i]に対して次の2種類のクエリを処理します。

  1. 区間[l,r]のすべての値にxをXORする
  2. 区間[l,r]の値の和を求める

「ある区間の値すべてにXORをした結果の和」は簡単には求まらないので区間add区間sumのようにはいきません。

そこで、値をビットに分割してそれぞれ1ビット目のセグメントツリー、2ビット目のセグメントツリー…というようにビット毎にセグメントツリーを作ります。

kビット目のセグメントツリーは、{a[0]のkビット目, a[1]のkビット目, a[2]のkビット目 … }という列を元に構成して、各頂点が対応する区間の要素の和を持つようにします(val[i])。

XORのクエリについては、xのkビット目を見て1ならk番目のセグメントツリーに対して区間[l,r]の値を反転させます。ここで lazy[v] := 頂点vの区間の値を反転させるかどうか として遅延伝搬で処理します。頂点vの区間のビットを反転すると val[v] = 区間の幅 - val[v] となります。

SRM 718 Div2

※Hardを解いてからアップしようと思って書いてあった記事が下書きにあったので(Hardはまだ解けていませんが)アップしておきます。

SRM718Div2に参加しました。

Hardが解けなかったり、終了間際にmedのミスに気づいてresubmitしたりと満足いく結果ではありませんでしたが、ついに念願の青コーダーになることが出来ました。(嬉しい!)

[easy] RelativeHeights

問題概要

配列hが与えられる。hから任意1要素削除して得られる列において、要素の大きい順にインデックスを並べた列をgとすると、gとしてあり得る列はいくつあるか。

制約

  • {1 \leq |h| \leq 50}

解法

要素の数が50以下なので全探索できます。setなどを使ってカウントすれば良いです。

ソースコード

[medium] InterleavingParenthesisDiv2

問題概要

‘(’,‘)'からなる括弧列s1とs2が与えられる。2つの括弧列の左の括弧から任意に取っていってマージされた括弧列を作る。新しく出来る括弧列が次の「正しい括弧列の条件」を満たすとき、括弧列の作り方は何通りあり得るか。(新しく作られる括弧列が同じでも、マージの仕方が違う場合別としてカウントする) 109+7で割った余りを答えなさい。

正しい括弧列の条件

  • “”(空の括弧列)
  • X,Yがそれぞれ正しい括弧列であるとき"XY"
  • Xが正しい括弧列であるとき"(X)"

制約

  • {1 \leq |s1| \leq 50}
  • {1 \leq |s2| \leq 50}

解法

まず、ある括弧列が正しい括弧列かどうか判定する方法を考えます。 ある括弧列について'(‘→+1、’)‘→-1として累積和を取って行くときに、途中で和が負になったらその文字列は正しい括弧列ではありません。(括弧列の中に’)‘に対応する’(‘が存在しないことになるため) さらに、最後まで和をとったときに0になっていない場合も正しい括弧列ではありません。それ以外は正しい括弧列になります。

そして、この問題を解くために次のDPを考えます

dp[i][j][k][l] := s1をi文字、s2をj文字使ったとき、上で考えた累積和がkであるときに、マージした括弧列の長さがlであるような括弧列の作り方の個数

dpの更新は

  • s1[i]==‘(’ なら dp[i+1][j][k+1][l+1]+=dp[i][j][k][l];
  • s1[i]==‘)’ なら dp[i+1][j][k-1][l+1]+=dp[i][j][k][l];
  • s2[j]==‘(’ なら dp[i][j+1][k+1][l+1]+=dp[i][j][k][l];
  • s2[j]==‘(’ なら dp[i][j+1][k-1][l+1]+=dp[i][j][k][l];

です。(MODで余りを取ることに注意)

求める答えはdp[s1.size()][s2.size()][0][s1.size()+s2.size()]%MODになります。

ソースコード

[hard]

まだ解けていません。。

SRM 717 Div2

おそらく全完したのは今回が初めてなので嬉しいです。嬉しいのでブログを書きました。

体感難易度としてmedの方がeasyより簡単な気がしました。(逆でしょ)

[easy] NiceTable

問題概要

0,1からなるテーブルが与えられる。このとき0,1からなる配列x,yを考える。
すべてのi,jについてt[i][j] == x[i] XOR y[i] となるようにx,yを決められるとき"Nice",そうでないときは"Not nice"を出力する。

  •  {1 \leq 縦 \leq 5}
  •  {1 \leq 横 \leq 5}

解法

全探索

縦横の長さはともに高々5なので、x,yを全探索出来ます。実装としてはビットで管理すると簡単です。

別解

テーブルの1列目と1行目を見ることで、適当にx,yを仮定することができるので、それが条件を満たすか調べます。

XORには {A \oplus B = C} であるとき {B = A \oplus C} , {A = B \oplus C} となるという性質があります。
これを利用してx,yを仮定していきます。

コンテスト中にはこちらの解法を書きました。

ソースコード

NiceTable

[medium] LexmaxReplace

問題概要

アルファベット小文字からなる文字列s,tが与えられる。sの文字をtの文字を使って書き換えていくことで作ることのできる文字列のうち辞書順最大のものを求める。ただしtの文字をすべて使う必要はない。

  • {1 \leq |s| \leq 50}
  • {1 \leq |t| \leq 50}

解法

辞書順最大にしたいのだから、なるべく左にある文字をできるだけ大きくすればよいことが分かります。 したがってtの文字を降順ソートして、左から順番に使っていけばよいです。

ソースコード

LexmaxReplace

ちなみに、idxがt.size()と等しくなった時にbreakする処理を抜かしていたことに提出してから気づいてresubmitしたのですが、 この処理を書かなくても通った人もいるそうです。

同じミスをやっている人が部屋にいるのを見つけたのですが、時間切れでチャレンジしそこねました(結果的にチャレンジしなくて正解でしたね)

[hard] DerangementsDiv2

問題概要

整数n,mが与えられる。このとき、1,2,3,…,n+mのn+m要素からなる配列を並べ替えてできる順列のうち、初めのm要素についてp(i)!=iとなるような順列の個数を109+7で割った余りを求める。ここでp(i)は順列のi番目の値を指す。

  • {0 \leq n \leq 50}
  • {1 \leq m \leq 50}

解法

方針として、すべての順列の個数からp(i)==iとなるiがあるような順列の個数を引くことで求めます。

p(i)==iとなるiがあるような順列の個数をnegとすると、negは包除原理を用いて求めることが出来ます。


例としてn=1,m=3を考えてみます。

1が被っている順列は
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
これは (4-1)! = 3! = 6 通りあります。
同様に2が被る順列の個数、3が被る順列の個数もそれぞれ 3! = 6 通りあります。
どの数字が被るかが {_3C_1} = 3 通りあるので、1つ以上の数字が被る順列の個数は 6 * 3 = 18通りあります。

次に 1と2が被っている順列は
[1, 2, 3, 4]
[1, 2, 4, 3]

1と3が被っている順列は
[1, 2, 3, 4]
[1, 4, 3, 2]

2と3が被っている順列は
[1, 2, 3, 4]
[4, 2, 3, 1]

よって2つ以上の数字が被る順列はそれぞれ (4-2)! = 2! = 2 通りあります。
どの2つの数字が被るかが {_3C_2} = 3通りあるので、2つ以上の数字が被る順列の個数は 2 * 3 = 6通りあります。

最後に1,2,3が被るような順列は
[1, 2, 3, 4]
(4-3)! = 1! = 1通りです。 被る数字の選び方は {_3C_3} で1通りなので3つ以上の数字が被る順列の個数1通りです。

よってこの場合のnegは包除原理を用いて、

neg = (1つ以上の数字が被る順列の個数) - (2つ以上の数字が被る順列の個数) + (3つ以上の数字が被る順列の個数) = 18 - 6 + 1 = 13

と求まります。

したがって、この例での答えは (3+1)! - neg = 4! - 13 = 11 となります。


これを一般化すると、1〜mのうちk個以上が被っているような順列の個数は {_mC_k \times (n+m-k)!} で表すことができるので、 答えは

{ \displaystyle
ans = \lbrace (n+m)! - \sum_{k=1}^{m}{_mC_k \times (n+m-k)! \times (-1)^{k-1}} \rbrace \% 10^{9}+7
}

となります。

ソースコード

DerangementsDiv2

Google Code Jam 2017 Round1B A.Steed 2: Cruise Control

A問題のsmallとlargeだけ通して寝落ちしてました。。

A.Steed 2: Cruise Control

問題概要

Dashboard - Round 1B 2017 - Google Code Jam

アニーさんは馬に乗って初め地点 {0} にいて、距離 {D} の地点を目指して直線の道を進む。 道には {N} 頭の馬 {H_i} がいて、それぞれは初め地点 {K_i} にいて最高速度は {S_i} である。 各馬は前の馬に追いついたらそれ以降はその馬と同じスピードで走る。 アニーさんの乗っている馬が減速せずに一定のスピードで進む(他の馬に追いついて減速するイベントが起こらないように進む)とき 距離 {D} の地点に到達できる最短の時間を求めよ。

制約(large)

  • {1 \leq N \leq 1000}
  • {0 \lt K_i \lt D \leq 10^{9}}
  • {1 \leq S_i \leq 10000}
  • {K_i \neq K_i (i \neq j)}
続きを読む

Codeforces Round #380 Div2 C.Road to Chinema

codeforces.com

問題概要

$n$台の車についてコスト($c_i$)と燃料の容量($v_i$)が与えられる。
$s$kmを$t$分以内に走ることの出来る車の中でコストの最小値を求めたい。
ただし、途中$k$箇所($g_i$km地点)では燃料の補給が自由に行える。(何回でも)
また、いずれの車も次の2つのモードがあり自由に切り替えて走ることが出来る。

  • normalモード : 1kmを2分、燃料1L消費
  • acceleratedモード : 1kmを1分、燃料2L消費

制約

  • $ 1 \leq n \leq 2 \cdot 10^{5} $
  • $ 1 \leq k \leq 2 \cdot 10^{5} $
  • $ 1 \leq s \leq 10^{9} $
  • $ 1 \leq t \leq 2 \cdot 10^{9} $
  • $ 1 \leq c_i,v_i \leq 10^{9} $
続きを読む