有向グラフの連結性を見るときに uf を使ってはいけない
- D問題、解けないのはともかく TLE 解法実装して時間使っちゃたのがよくない
- TLE 解法を実装した原因: T=100 を考慮し忘れて、10^8 想定の計算量が 10^10 くらいの計算量になっちゃってた（計算量見積もりのミス）
- 計算量見積もりをミスした原因: よくあるマルチテストケースの問題は、総和が 10^5 で抑えられますみたいな感じで、テストケースの個数が計算量に依存しないがちだから、T のこと忘れちゃってた可能性
- 2×2 のケースは考慮していたが、2×4 や 4×2 のケースを見落としていた
- 内側がないケースは例外ケースとして処理をした。
- 2×2 のケースしかないと誤解してしまった
- 例から考えて、その例がすべてだと誤認してしまうパターン
- テストケース追加で作ったが、縦=横のケースしか作ってなかった
- hとw逆にしていたケースでも気づけないので良くない
- 攻撃されている回数（2×2の黒マスに含まれているマスの数）の大きい順の貪欲だとうまくいかないことに気づいたのはよい。
- 2×5みたいなケースを作って確認をした（これを作った段階でテストケースに追加していれば……）
- テクニック
- D問題が解けないのは仕方ないとして、F問題が解けないのは復習不足感がすごいなぁ..…
- 「交差しない」の言い換えミス
- やったこと: 「辺 a-b が他の辺と交差しない」を a-b の間にある辺の端点の数が偶数個と捉えた。しかしこれは「交差しない」なら「端点の個数が偶数個」が言えるだけで「端点の個数が偶数個」なら「交差しない」は言えないので間違っていた。
- 原因1: 必要十分条件・必要条件に関する自覚がなく、結果として十分性の確認が抜けてしまいがち
- まず言い換えというのが必要十分条件を求めることである自覚がなかった。
- 「交差しない」という状況を思い浮かべて「端点の個数が偶数個」を言うのは、必要条件を求めることに相当する。しかし必要条件を求めるという自覚がなかった
- その結果、十分性を確認する思考に至らなかった
- 実際、十分条件は満たさなく、正しい言い換えになっていなかった。
- 原因2: 帰納的な考察（例から考える）を演繹と同様に正しいものと無意識に扱ってしまっていた
- 交差しない例を思い浮かべて、その状況がすべてだと無意識に考えてしまった
- （交差する例を思い浮かべていなかった）
- 原因まとめ
- 必要十分条件・必要条件に関する自覚がなく、結果として十分性の確認が抜けてしまいがち
- 例から言えることがあくまでも予想であるという自覚が薄い（帰納的考察をしているときに帰納的である自覚が薄い。
- 対処法
- 十分性を確認する習慣をつける方法
- 元々の目的を自覚する
- 「条件を扱いやすくしたい」という目的は、扱いやすい必要十分条件を求めることに相当する
- 目的の言語化を意識する
- 必要条件を考える段階で自覚する
- 「この条件が成り立つとしたらこう言える」というのは、必要条件を求めることに相当する
- この自覚がないと、後で十分性を確認するという発想にならない
- 「本当にそれで大丈夫？」を考える習慣
- 帰納的な考察（例を用いた考察）をしている場合は、常にそれが正しくない可能性（証明が別途必要であること）を自覚的になる