AtCoder Grand Contest 043 B - 123 Triangle
1,2,3->0,1,2と読み替えて良い。(N>=2、かつ2段目以降は+1分が相殺されるため)
こういう問題はまずは偶奇を見る。
するとパスカルの三角形的に考えて、Σ n-1Ck a[k] の偶奇であることがわかる。これが奇数なら答えは1であることが確定する。
次に偶数のとき、答えは0か2になる。a[i]の中に1が入ってる場合を考えると、0, 1, 2との差分は必ず1か0になる。実験するとわかるが、どこかに2の要素があったとしても1がどこからか近づいてきて2を消す挙動をする。そのため、1がある場合は必ず答えが0である。
次に0, 2のみの場合を考える。これは2->1と読み替えるとさっきの偶奇の問題 Σ n-1Ck a[k] に帰着する。
本番ではnCkの偶奇の計算がTLEして通せず。実はこれは非常に軽い判定法があるらしい。
spherical-harmonics.hatenablog.com
n == ( r | (n - r) ) ? 1 : 0
これを実装したら通った。計算量はO(N)。
yukicoder No.1012 荷物収集
ちょっと複雑な累積和。次のような状況を想定する。
[左の荷物群の初期位置] 運びたい位置X [右の荷物の初期位置]
累積和を取ることで、「左の荷物群をその荷物群の中での右端まで異動するためのコスト」のテーブルが構成できる。
あとは「左の荷物群の中での右端」からXまでの移動コストだが、これは左の荷物群の総量と「左の荷物群の中での右端」からXまでの距離の積になる。これで左側がクエリごとにO(1)で計算できた。右側も同様。
あとは左と右に荷物を振り分ける作業であるが、これは二分探索すればよい。計算量はO(log(N) * Q)。
二分探索で見つけたインデックスに±1といった調整が必要になるので、二分探索した結果がどこにあるのか常にイメージで持っておく or 適当に総当りのいずれかが必要。
Yukicoder No.1013 〇マス進む
ダブリングの練習。
まず「次の場所 % n」の値をダブリングテーブルを前処理しておく。
for (int i = 1; i < m; i ++) {
for (int j = 0; j < n ; J++) {
table[i][j] = table[i-1][table[i-1][j]]
}
}
ダブリングテーブル自体はこんな感じで更新できる。
さらにp[i]進んだときに何周するかがわかれば良い。
これもダブリングと同じようにマスjから2^(i-1)だけ進んだときに何周したか、というのをテーブルで書いておく
for (int i = 1; i < m; i ++) {
for (int j = 0; j < n ; J++) {
table2[i][j] = table[i-1][j] + table2[i-1][table[i-1][j]]
}
}
位置のダブリングテーブルを使うとこんな感じでかける。最後に「周回数 * n + 位置」をそれぞれのクエリにO(log(K)) で計算する。
全体計算量はO(N log(K))
AtCoder Beginner Contest 154 F - Many Many Paths
二次元のある長方形領域 (r1≦y≦r2, c1≦x≦c2) の中の yCx の和を計算する問題。
とりあえず2次元の中の何かの和を考えるときは、包除原理を使うことにより 0≦y<≦r, 0≦x≦c で計算するルーチンを書いておき、あとから余計な部分を引くのが定石。
では、あるr,c が与えられたとき、0≦y<≦r, 0≦x≦c でのΣyCx の計算だがいろいろな方法がある。
一つはWolfram Alphaを使う方法。適当に入力すると式を簡約し今回は計算量の小さい式を勝手に計算してくれたみたいなので、使えるようにしておきたい。
本番で考えたのはyCxの計算は格子点領域の中である地点から別の地点へ向かう最短経路の数の数え方に一致することから、このDPの漸化式を考察した。すると、その長方形領域を斜めで縦でも横でも良いがあるラインで考え、そのライン上のyCxの和が計算できたとする。その時、最短経路の数え方は隣接した格子の数を足し合わせる、ということを考えると、
[あるライン上の yCxの和] = [一つ前のライン上の yCxの和] * 2- [ラインの端っこの調整]
という漸化式が成り立つ。この漸化式に従って、計算していき、ライン上の yCx の和をどんどん足し合わせて行けば良い。O(max(R,C))
AtCoder Beginner Contest 154 E - Almost Everywhere Zero
桁DPの典型的な問題。非常にNの大きい問題で、N以下で条件を満たすものの数を数えよ、という場合はだいたい桁DPでやるのがよい。
DPは上位の桁(文字列でIndex 0の文字)から見て、状態として「ある桁まで見たとき、0以外の数がK個」「ある桁まで見たとき、それまでの数字がすべてNに一致しているか否か」という状態を持って桁DPをすればよい。計算量はO(Nの桁数)
今回は既に桁に現れた0以外の数という状態が特殊だが、桁DPの場合上位の桁から見る場合は与えられたNと「ある桁まで一致しているか、それともN以下の数の桁が一回でも現れたか」という2個の状態を持って判断するのが鉄則。
感想：桁DP苦手だなと思ってたけどスラスラ行けたので意外とものにできてそう。
第6回 ドワンゴからの挑戦状 本選 A - 2525敷き詰め
構築ゲーなので「こうすればいい」ではなく発想法をメモ。
まず2でも5でも連結サイズが小さいことに着目する。HやWが大きい場合、例えば角や辺以外に2を配置するとその周囲8マスには2が1個しか置けないことから残りが5であることが確定する。すると5の連結サイズが7になってしまい条件を満たさない。
よって2は辺や角に配置する必要がある。
次に5を辺や角以外に配置する場合、色々試すと3x3の配置が1個見つかる。これがコーナーケースなので埋め込もう。
よって上記コーナーケースを除くと、2も5も辺や角にしか配置できないことがわかる。そのようなケースはmin(H,W)<=2 であることがわかる。
まずmin(H,W)=1の場合はかんたんで、2と5を交互に並べていけばよくmax(H,W) mod 7 が0, 2, 5のいずれかで可能。
次にmin(H,W)=2の場合を考える。以下問題にあるサイズ2またはサイズ5の連結成分を形によらず「2または5のブロック」と呼称する。min(H,W)=2の場合、合計マス数は必ず偶数になるため、5のブロックを1個以上使う場合その数は必ず偶数個使う必要がある。また5のブロック同士はくっついてはならない。そのため、最低でも5*2+2=12のブロックが必要になり、これはmax(H,W)=6に相当する。
同じような考えで、HまたはWの長い方に伸ばすことを考えると次のような構成が考えられる。
...|2のブロック｜5のブロック｜2のブロック｜5のブロック｜…
このとき考えられるパターンとして
- 2のブロックが2n+1個、5のブロックが2n個で合計14n+2, つまりmax(H,W)=7n+1
- 2のブロックが2n個、5のブロックが2n個で合計14n+2, max(H,W)=7n
- 2のブロックが2n-1個、5のブロックが2n個で合計14n-2, max(H,W)=7n-1
の3通りが考えられる。これらはちょっと試すと具体的に構成可能であり、それらを場合分けするとAC。
感想：場合分けゲーは苦手です。
SoundHound Inc. Programming Contest 2018 -Masters Tournament- B - Removing Blocks
N!の総和系なので、確率・期待値でやるべき問題。
まずは1回のコストの期待値を考える。答えはこれにN!をかけてやればよい。すると、ブロックj を取り除いたときに、ブロックiが連結である確率をP(i, j)としたとき、1回のコストの期待値はΣa[i] * P(i, j) となる。iを固定した時、Σ(a[i] * ΣP(i,j)) であるから、ΣP(i, j) のjに対する総和が求まればよい。
ブロックjを取り除いたときにiが連結になる確率が一番の肝であるが、これは区間[i, j]の中で一番最初に取り除かれるブロックがjである、という確率に等しい。これが最重要でここでハマる可能性が高い。
これさえわかればあとは簡単で、P(i, j) = 1 / (1 + | i - j |) であることがわかるので、これを計算し、ΣP(i, j) ( ただしjに関する和）が求まる。
期待値、確率系の問題では愚直に！やnCrを用いて書き下すのも重要だが、部分的に切り出して感覚的に明らかな確率に落とし込むというのも重要。
私は最初連結であるという確率を「(区間1) i (区間２) j (区間３)」という３区間に分け、nの順列を考えたときに(区間2)に相当する部分がiやjより後ろにある、という計算をしてハマってしまった。
