kwm_t

kwm_tのメモ

ABC195

■A - Health M Death
if (0 == H % M)


■B - Many Oranges
全探索


■C - Comma
n桁の数に打たれるカンマの数は、(n - 1) / 3


■D - Shipping Center
制約が小さいのでどうにでもなります
価値の大きな荷物から順番に、その荷物を入れられる最小の箱に詰め込んでいく


■E - Lucky 7 Battle
dp[i][j]:= N - iターン終了時点で、mod7がjの状態に持っていければ高橋くんが勝てるのならばture
そうでないならfalse

初期値は、dp[0][0] = true
高橋くんはいずれかの遷移で高橋くんの勝ちパターンに入れるならtrue
青木くんはいずれの遷移でも、高橋くんの負けパターンに入るならtrue
とdpを遷移させ
最終的にdp[N][0] = trueなら高橋くんが、falseなら青木くんの勝ち

つまるところXor Battle(agc45-A)


■F - Coprime Present
Eを解き終えたときには残りが20分のため考察が終わらず
B-Aが小さいので、共通の素因数として持つ可能性がある素数は高々20種類
なので状態数が(B-A)*(2^20)程度なら十分に高速にbitdpの処理ができるので
dp[i][j] = i個目まで見て、jの立っている素数はすでに選択したものに含まれている選び方
とする。



■感想
B,C,Dがいつもより少し重たくないですか?
EとFは配置が逆なら正解者数も大きく変わりそう。