エクサウィザーズ C

C

所感

にぶたんが見えた時まだあと20分あったのに通せなかったのは流石に†反省†

問題概要

問題をうまく要約できないので元のページを見て(は？)
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c

取った方針

全てのゴーレムが呪文を唱え終わった時にどこにいるかを出力してみる or 解説みたいな考え方をする と左に消えるゴーレムの右端と右に消えるゴーレムの左端を求めればよい(あるn,mが存在して、n-1番目以前 or m+1番目以降 のゴーレムは消える ようなn,mが求まる)ことが分かる。
ゴーレム一つに対するシミュレーションはO(Q)ででき、二分探索をするとO(QlogN)で左端と右端を求められる。が二分探索をバグらせて終了

正しい方針

落ち着いて二分探索をする。 最大値を求める二分探索と最小値を求める二分探索でバグらせるので境界から逃げずにしっかり二分探索を使う or めぐる式をする
解が存在しない時にも気を付ける。(判定関数をfとしたときに、得られた解がf(x) == true となるかを確認しハンドリングする)

得られた知見

• 二分探索(最大値/最小値) or めぐる式
• 解が存在しない可能性がある場合は得られた解を確認する
• わからん場合は愚直解を書いてトニカク何かしら画面に出す(気づきが得られがちだし、～500ならこれだけで終わることもある)
  • 10年前S〇PIXで死ぬほど言われた奴
  • アホ だったので最後まで書き出して教員に煽られたりしていた(1クラスに1人はいがち)
• 500は解ける

  解くのに必要な要素

  ・二分探索

周辺調査によって得られた知見

特になし