2021/03/01
今日から再開する
Unfair Nim
黄diff
A[0]^A[1]==A[2]^...^A[N-1]となればいい。
2進法の下の位から、桁dpで移動する石の数を考えていく。
A[0]は上の位から借りているか、A[1]で繰り上がりが起きているか、の情報をdpに持たせる。
釘 (Nails)
JOI 難易度8
縦方向に見て、横にどれだけ伸びるかをまとめて求めた後、横方向に見て輪ゴムの中にあるかを求めた。
公式解説では斜めのimosをしたり、自分=max(自分, max(左上, 右上)-1)の性質を使ったりしていて、天才だった。
distribution - 冊子の配布 (Distribution)
JOI 難易度8
木の2乗dpみたいな感じでやるとO(n^2)になる。
通知
PAST O
解けなかった。想定解法を見て天才に思ったけど、PASTに出てるし、汎用性が高そうだから典型なのかな。友達が√M以上の人はT=1のクエリで愚直に通知を送らず、T=2のクエリのときに送られたかを見るようにする。そうすると、各クエリはO(√M)になり間に合う。
輪投げ
PAST O
DPを考えたけど無理だったので諦めた。
最小費用量で解ける。存在をすっかり忘れていた。思いついたとしても解けたかは微妙。正直、どんな問題を解けるのかがよく分かってない。......ライブラリを見ると「割り当て問題はこれ！らしい」と書いてあった。
typhoon - 台風 (Typhoon)
JOI 難易度9
イベントソートをした。台風の被害にあった数はBITとimosでいい感じにした。
