📚
グリッド ABC377 C Avoid Knight Attackを理解し忘れないようにする。
問題文概要
グリッドにコマが置かれていて問題文通りにコマが動く。
新たなコマを配置する際に、すでに置いてあるコマにとらない位置の数を求める。
コンテスト中の方針
問題文をよく読んでいないのにもかかわらず、グリッドでNが大きい問題が見たことがなかった理由のみで、計算量削減プランを考えることから逃避してしまった。また、Dが２ぶたんを使いそうだったのでそちらに時間を使ってしまった。
今後は、せめて問題文の内容を理解することに最低10分程度使ってから次の問題に取り掛かる。
解説見た
- 前提として、Nは10^9なのでループを回すとTLEになる。よって全体のグリッド
N \times N - 計算量を削減する方針として、全体のグリッドの個数
N \times N - ネックになる点
- コマが複数個あった際に進む方向が被った際の対応をどうするか？
- setで現在のコマの位置とその進む方向を追加して重複に対応する。
- 最後に全体のグリッドのマスの個数からsetのサイズを引けばいい。
- コマが複数個あった際に進む方向が被った際の対応をどうするか？
- ネックになる点
補足
この問題のような、直接考えるのが難しい時は、反対の条件を求めて全体からそれを引いて、求めたいものを求める考え方はよくある典型考察らしい
Discussion