「みんなのプロコン」2017 本選 A - YahooYahooYahoo

• 問題

解法

典型的な文字列AとBの編集距離を求める問題において, B = "yahoo" と固定したバージョンになる.
(は正規表現における閉包)

i=1,2,.. として 部分文字列S[0,i) を最終的な状態 "yahoo"* の前半と一致させることにしよう.
それまでの最小の編集距離に注目する上では, 末尾が "yahoo" の何番目になっているかということにだけ注目すれば良い.
よって, dp[i][j] := (S[0,i) を 末尾が"yahoo"のj番目(0-index)になるようにした,最小の編集距離 ) とする.

すると, 遷移は dp[i][j] からs[i] をそのまま足して 1<=k<=5 回末尾に insert, または末尾を 1回deleate したパターンを考えればわかる.
1<=k<=5 回でなく1回だけinsertすると考えて dp[i][j] から dp[i][j+1] に遷移させることもできるが, その場合解説にあるように2周しないといけない.
初期値と答えに注意.

コード

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C - ロト2

• 問題

解法

a_i は K と共通の因数しか注目しなくて良いことがわかるので, a_i = gcd(a_i, K) とみなして良い.
Kの約数は高々 2sqrt(K) しかないので(エラトステネスの篩をやっていくとわかる), a_i として現れる数は O(sqrt(K)) しかない.

定跡としてこの分布をとると,(つまり cnt[a] := aの現れる回数 とする)
全ての a<=b (a,bはcntのkey) についての全探索がO(K)となって間に合う.

ただし a==bのときは abがKの倍数になるならば cnt[a](cnt[a]-1) を足すことに注意(自分自身とは組にできないため)

コード

square869120Contest #3 D - お土産購入計画2 / Souvenirs (600)

• 問題

解法

• 最短路なので2人とも(0,+1) or (+1,0) で進む
• 1人だったら? -> DPで(x,y)または(何回進んだか,x)をキーとして持ってやればできる
• なぜなら(x,y)で最大のお土産を持つためには(x-1,y)or(x,y-1)で最大のお土産を持っている必要があるため
• 2人でも2人の座標を持ってやればできそう
• (x,y)両方とも持つ必要はなく, (ターン数,1人目のx,2人目のx) を持てばOK
• 漸化式は
• 2人とも同じとこにいく(nx,ny)=>+a[nx][ny]
• 2人が別のとこにいく(nx1,ny1),(nx2,ny2) => +a[nx1][ny1]+a[nx2][ny2] でOK

メモ

1人ならDPできるねーからマップを2つに分けて各々DPするか?みたいな方向に行ってしまってできなかった.
どういう状態を持つべきか,とかの訓練が足りなさそう

コード

AGC 026 C - String Coloring

• 問題

解法

• 制約から半分全列挙をエスパーする
• 2Nとあるので半分と後半に分けてみる
• 前半の赤色がa文字とすると,前半の青色はN-a,後半の青色はaになる
• 前半の赤色=reverse(後半の青色) かつ 前半の青色=reverse(後半の赤色)である必要がある
• どちらも全列挙してkeyを(赤色の文字列,青色の文字列),valueを何個できるかで持っておけばOK

メモ

これ思いつかなかったの厳しい

コード

AGC 026 B - rng_10s

• 問題

解法

• 明らかに,解説で除いている3ケースはわかる.
• そうでないとき, 個数をy個とすると無限に買い続けられるときは y = C の周りを振動する
• 無限ループするので,yが周期をもつ-> C+1 <= y <= C+B の値を全て取りうる? .. そうであればC+1-B>=0を判定すればOK
• 実際上のようなケースは gcd(B,D)=1のときに限られることがわかる
• ex. (A,B,C,D) = (7,3,1,6) は 7,4,1,7,4,1,..
• g = gcd(B,D) のとき A+kg であってCより大な最小のものがCより大きい最小な個数っぽい
• このようなkは k=(A-C-1)/g で求められるのでこれで A-kg-B>=0 であればOK

以上で1回のクエリがO(1)で解けた.
わざわざクエリ方式にしたのは嘘解法が無限に作れそうだからっぽい.

メモ

解けたが,解説のような綺麗な解法はできなかった.
以下のことを意識すると良いかも?

• 2回定数加算の操作があるときは1つのmodをとってみる(操作が1回になるため)

コード

codeFlyer 2018 final D - 数列 XOR(600)

• 問題

解法

考察

• XOR swapによりswapが可能( a ^= b, b ^= a )
• これによってa_i, a_j (i!=j) で操作ができる
• あるbitだけ立っている要素があればそれを使ってそのbitを自由に立たせることが可能
• そのような要素は {1101, 1001} のような1bitだけ異なる数があっても作ることができる
• それが作れれば {a} と {b} でその要素ができるか?という基準で判定さえすればOK
• しかし上の {1101, 1001} の 1001のように2bitが必ず同じように現れることもありえる
• 全ての組み合わせは2⁶⁴で判定するのは無理だし..?

上の操作が行列の行基本変形に酷似していることに頑張って気付こう.
結果的にいえば, 1bit目が立っているものを調べてそのような要素(a_rank)がなければそのbitは無視し,あるならばその他の要素(a_i)をその要素とのxor (a_i ^= a_rank)にして消していくというのをやれば良い.
これはxorをmod2での加算と見て,bit方向を列と見たときのGaussの消去法に他ならない.
またxorは逆操作が可能なので {a} -> {b} という操作が可能か?という問題でなく, {a}, {b} を共に共通の標準形にできるか?という問題に言い換えることができる.
よって {a}, {b} に上の操作をして,等しくなればYes,そうでなければNoになる.

メモ

• 逆操作が可能なら共通要素に変換できるか?という問題になる
• bitを列にして行列で捉える味方

コード

Mujin Programming Challenge 2018 F - チーム分け(600)

• 問題

解法

良解説を聞くのが良い

• とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく
• 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理
• 視点を変えて,人数がk人であるようなグループを全て作っていく,というようなことを考える
• 昇順にやっていこうとすると,2人組を作るときにaの値が(2,3)をペアにするのと(2,4)をペアにするのは区別しないといけない
• 降順を考えると,x人のグループを作ろうとしているときにa_i>=xであるようなa_iは区別しなくていいことに気づけたら勝ち

def.
dp[i][j] := (i人以上のチームをすでに作っていて, i人チームを作るときに自由に使える人がj人残っている)
初期.
dp[N+1][0] = 1
遷移.
解説の通り
ans.
dp[1][0]

メモ

これむずいけど好き.
制約はゆるい方から決めて行った方がいいのかな

コード