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]

メモ

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

コード

ARC 103 D - Robot Arms (600)

• 問題

解法

sample2をじっと見ると,必要条件として

• X_i, Y_i の和のパリティが全て一致する

というのがあることがわかる
パリティに注目するのはよくやるのでこれは気づかないとどうにもならない.

実際に,そのときdとして1を20個/21個用意すれば300点は取れる.
(例えば (-3,2) のとき LLLUU(UD)*8 )

このような構築ゲーで2冪に注目するのが定跡なことを念頭に置いて,
アームを 2⁰ , 2¹, 2² , ..と増やしていくことにしよう.
すると 2^k まで使ったときに, abs(x) + abs(y) <= 2^k+1 - 1 のひし形内の和が奇数の点を全て取れることがわかる.
abs(x),abs(y) < 2³⁰ - 1 だから, abs(x) + abs(y) < 2³¹ - 2 で k = 30としてやれば十分.
和がevenの時は 2⁰, 2⁰, 2¹, .. , 2³⁰ とすれば良い.
このようにすれば必ず構築できることもわかったので,列挙した必要条件が必要十分条件だったこともわかった.(よくあるパターン)

実際の構築に関しては 2^k のkが大きい方から決めていき,
abs(x+dx) + abs(y+dy) が0に近くなるようにしてやれば良い
そうしていけば最終的に(0,0)に一致することは上で確かめられている.

メモ

2冪は頭にあったけど実際に書いて見なかったのがよくなかった.

コード

ARC 103 E - Tr/ee (700)

• 問題

解法

まず十分条件を列挙していく.
0-indexedとして,

• s[0] = 1
• s[N-1] = 1
• s[i] = s[N-1-i]

D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン.

s = "100..01.." として,k番目に初めて1が現れるとする.
このとき,1つの辺を切断することで現れる高さ2の部分木は,k-1個の子をもつものしか作れないことがわかる.
これをどんどんやっていくと,
k-1番目までで x_1 = 1, x_2, x_3, .. (1<=a_i<=k-1) の子が作れるとして,
次に1がk番目に現れたとする. このとき,
k-1 = a_1 * x_1 + a_2 * x_2 + .. とx_iの線形和でノードがk個(子要素がk-1個)の木を作ってやることが必要になる.
一瞬DPをしたくなるが, よく見れば a_1 = k-1, a_2 = a_3 = .. = 0 としてやって 1の子要素で数を合わせれば良いことがわかる.
実際そうすれば解説動画のように必ずその木が作れることがわかり, 列挙した必要条件が必要十分条件であることもわかる.

メモ

閃きゲーかと思ったけど,実際に考察ができて見るとただの論理的帰着な気もする..
構築ゲーに関しては最小単位で数合わせ+2冪を考えてみるのがテンプレかな.
今回からけんちょんさんのブログの書き方(タグ付けとか)がわかりやすいので真似していくことにした.

コード

CODE FESTIVAL 2018 qual A C - 半分

• 問題

解法

関連した以下のような簡単な問題について考える.

• n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか.

これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける)
def : dp[i][j] := ( 前からi個取った数列 {a_0, .., a(i-1)} に対して j 回 操作を行った時のできる数列の数 )
初期化 : dp[0][0] = 1 , dp[0][k] = 0 (k>0)
漸化式 : dp[i+1][j] = sum(0<= k <= j)( dp[i][j] )

これに沿ってこの問題を考えてみると,以下のようになる

• 数列の各要素に対して以下の操作を合計K回行う. 数列は何通りできるか
• 操作は cnt_i = floor( log2( a_i) ) + 1 として, cnt回行うまでは毎回違う数に変化し, cnt回以降はずっと0.

この問題に対して先ほどと同じDPは使えない.
なぜなら a_i に対して cnt_i 回操作を行った場合とそれより多く操作を行った場合を複数回数え上げてしまうため.
なので, disjointに数え上げるために以下の制約を付け加える.

• a_i に対しては cnt_i 回までしか操作を行えないとする

この制約を付け加えた時点で,求める答えが変化することに注意する.

• 元々条件での答え
• : 合計K回操作を行った数列の数
• 制約を加えた時の答え
• : 合計K回操作を行った or 何回操作をやったかに関わらず1つでも0を含む数列の数 制約を加える前は 0 ができたら何回でも操作を稼げたが,制約でそれができなくなったからである.

またK<=10⁹だが, A_i <= 10¹⁸ < 2⁶⁰ より cnt_i < 60.
つまり 操作は 数列全体に対して 60N回もできないので K = min(K,60N) とすれば良い.

答えを数えるために,以下のようにおく.
dp1[i][j] := ({a_0, .. ,a(i-1)} が0を含まず,j回操作を行った時の組み合わせ)
dp2[i][j] := ({a_0, .. ,a(i-1)} が0を含み,j回操作を行った時の組み合わせ)

この時, a_i にk回操作をすると考えると漸化式が立てられる.
dp1[i+1][j] = sum(0 <= k < cnt_i ) dp1[i][j-k]
dp2[i+1][j] = sum(0 <= k <= cnt_i )(dp2[i][j-k]) + dp1[i][j-cnt_i]

答えはdp1,dp2が全てdisjointであることを考えれば
dp1[K][N] + sum_( 0<= j <= K ) dp2[i][j]
で求められる.

メモ

まあ解けなかったんだけど

コード

Warshall-Floyd の本質ミス

ミス

o rep(k,N) rep(i,N) rep(j,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);
x rep(i,N) rep(j,N) rep(k,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);

なぜか

Warshall-Floydの証明を考えれば明らか.
証明
Warshall-Floydが何をしているかというと,最初のループがk回終わった時点で, V_k = {0,.. ,k-1} を経由点とする最短路を全て求めている.
これによって帰納法により全点最短経路が求められる.
逆に,そうしなければ正しく最短路が求められない.

メモ

1行で書けるので毎回書いてたけど,間違えて覚えたらしい.
ハマった.