pyてよn日記

一寸先は闇が人生

競プロ覚書:問題を解くときの方針

自分にとっては C 問題が一つの壁なので,それを解くときの方針をまとめてみました.知見を得たら追加していきたいと思います(茶色の戯言なので優しい目で見守ってください).

参考になりそうなサイト

yukicoder.me

問題を解くときの基本方針

気持ち的なもの

  • ABC の A,B 問題で速解きすることは大事だけど焦りすぎないこと.冷静に.焦って提出してペナルティ 5 分くらうよりかは,1-3 分かけて見直した方が良い.
  • どんなに A, B を早く解いたところで C 問題解けないとレートは上がっていかない...

一般

  • 焦らず,問題をちゃんと読む.読み間違えで時間を溶かすのはもったいない.
  • 簡単な問題に落とし込めないか?問題の操作を素直に行うだけでは上手くいかない(シミュレーションできそうな制約なら話は別).
  • シミュレーション後,最終的な結果がどうなっているかを考えると答えが出るときがある.
  • シミュレーション・ゲームなどの分かりやすい例でなくても,最終状態がどうなっているか,最終状態の一つ前はどうなっているかを考えてみる(例えば,無向グラフの辺を壊していくクエリを与えられた時に,最終状態,最終状態の一つ前を考えると問題が考えやすくなる,ABC120).
  • +1,-1,くっつける,倍にするなどの操作の順序をよく考える.足してからくっつける,くっつけてから足すなど操作を単純化する.
  • gcd, lcm が使えないか.
  • ソートしたらどうなるか.
  • ソートされた数列から区切り(ある数以上,より大きい)を見つけるときは二分探索
  • 累積和を取ったらどうなるか.
  • 操作後の偶奇性はどうなってるか.
  • 場合分けをしたときに漏れを見つけるのは大変,確実に場合分けができているかちゃんと確認すること.(自分で考えた場合分けが勘違いなこともある
  • 差分更新:次の状態が前の状態とほとんど変わらないとき,前の状態を活用できる(漸化式っぽい考え方? ABC120)

制約が小さいとき

  • 制約が小さい = 難しいことを考えずにシミュレーションを実行できる可能性
  • 制約が小さい = 全探索
  • 全探索(計算量を落とすことを意識)
    • 愚直な多重 for 文
    • 工夫した多重 for 文(3 つある時に 2 つ決まれば残り 1 つが定まる)
    • 制約が小さいもので for 文
    • 三つある時は真ん中を固定して for 文(O(N)になる)
    • DFS は使えないか?(対象に対して使う使わないとかで分岐できないか)
    • bit 全探索は使えないか?
    • std::next_permutation は使えないか?

計算量チートシート

Mister(@mistter_gp)さんのツイートより引用.制約から見える解法の計算量.

N<=

8 : next permutation
16 : bit全探索
32 : 半分全列挙
100 : ???
103 :  O(N^{2})
105~106 :  O(N \log N) \  or \  O(N)
109~ :  O(\log N) \  or \  O(1)

典型と呼ばれるもの

Union-Find 木

  • 辺を消去する処理を辺を繋げる処理に変えて考える
  • クエリを逆から読む

私にはまだ少し早いけどもいずれ必要になるかもと思ったので以下の記事をメモ.

shibh308.hatenablog.com

提出前後で気をつけること

テストケースのチェック

  • 添字のチェック:i, j, k などが合っているか?ロジックの間違いではなく,添字間違いのせいで WA になっているケースがある
  • 簡単な例,極端な例(制約ギリギリ,なければ自分で作る)は必ず手元で実験する.
  • 提出前にコーナーケース(入力が最小の場合,最大の場合),オーバーフローになりそうな WA を予測してみる.
  • サンプルが1つしかない(少ない)問題は実験するとめっちゃ単純な法則がある.

オーバーフロー関連

  •  10^{9} を超える数からは long long型を使う
  • C++ の整数演算では,2 の冪乗( 2^{32},  2^{64})の mod が暗黙に行われており,演算の途中で  2^{32}(int の場合)や  2^{64}(long long の場合)が含まれると,演算の結果が(0 を因数に持たなくとも) 0 になりうる.(ABC033-C)

計算量関連

一般

  •  10^{8} は簡単な処理なら O(N) で回せる( 10^{8}/1sec).
  •  10^{7} の処理は O(N) で回せる.
  •  (10^{5})^{2} = 10^{10} は TLE になる.

順列

  •  N \le 8 なら  O(N!) は通る(8! = 40320(104 程度)).
  •  N \le 10 までなら  O(N!) が通る( 10! = 3628800( 10^{6} 程度)).
  • std::next_permutation で生成した配列への操作は  O(N! * N^{2}) 以上(並び替えに  O(N),並び替え後の操作で  O(N) 以上).
  • 特に  N \le 8 ならば, O((N!) * N^{3}) でも通る( 8! * 8^{3} = 20643840( 2 * 10^{7} 程度)).

過去のコンテストの反省点

ABC119

  • 「制約が小さいから全探索だ」と頭では分かっていたつもりなのに,いつまでも貪欲法でなんとかしようとしていた(列挙の仕方がそもそも浮かばない,分からない).
  • 目先の +1,-1 に囚われ,合成と延長・短縮どっちを順番にやればいいのだろうかと考えていた(延長・短縮の順序は合成をやりきった後で良い).
  • (上にも通づるが)問題文を素直に受け取りすぎ.C 問題以降は問題文を素直に読んでも問題は解けない.「結局どういう問題なのか」と落としこもうする思考が必要(これも頭では分かっているつもりなのにコンテスト中に焦ると俯瞰できなくなる).

結論,大局を見る問題を単純な問題に落とし込む訓練をしていく必要がある(難しいことだけど練習しないことには).