思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

【競技プログラミング】問題を解くときの切り口

目次

はじめに

  • 競技プログラミングにおいて脱・初心者を目指して,問題を解いて得られた知見や先人の知恵・発想を少しずつまとめていきたいと思います.
  • (筆者としては)抽象的な表現で一般化を図っているつもりです.

    分かりづらい点・勘違い・誤解などがありましたらご指摘いただけると幸いです
    連絡先:@k_hiro1818

全般

問題文から得られる情報

  • 情報量が多すぎる

    • 図として書いてみる.
  • 得られた規則性・法則性を数式として表現できないか?

    • 前段階として,ノートなどに書き出してシミュレーションしてみる
  • シミュレーションするときには,数が増えた場合や境界付近がどうなるかを愚直に確認する.

  • 複数の操作を独立として扱えないか?

方針

  • 提出した解法の大部分がWA

    • 反例がないかを列挙する.

計算量の削減

  • 思いついた解法がTLEしてしまう

    • 愚直解(全探索)で,同じ(ような)計算を複数回していないか?

    • 回答に直接つながる部分を計算する前に,共通部分を事前に処理できないか?

    • 重複したデータ・操作をまとめられないか?

      • 標準的な形に変形できないか?
    • 制約が小さいことを利用して,視点を変えることはできないか?

      • 例:区間(1次元)を座標(2次元)に置き換える.
  • 考慮すべき条件が複数あるように思える

    • 点や軸などの条件を1つに固定して,その他の条件を変えることはできるか?

    • 着目する範囲を限定できないか?(計算・考察しなくても済む部分はないか?)

    • 最終的な状態にだけ着目して,途中経過をスキップできないか?

    • 条件を整理して,操作の順番に依存しない部分/依存する部分をまとめられないか?

    • 制約条件の厳しいほうから見たときに,着目すべき項目を減らせないか?

コーナーケースの特定

  • サンプルをフル活用

  • 制約条件に含まれる境界値から,回答の条件を満たさないケースを列挙

  • 極端な条件が揃ったときを書き出してみる

整数

数列

  • 並び順が結果に影響しないときは,ソート済みとして考えられないか?

  • 「書き換える」という操作を別の視点(集合全体から選択)からみてみることはできないか?

  • 対象データについて,操作の前後を区別せずに一つの集合として考えられないか?

  • 環状のままだと対処しづらいため,規則性・法則性を保持したまま,直線として扱えないか?

  • 左右から確認したときに,交差することを許容するかどうか?

  • 値の並びに周期性はないか? 周期性がある場合は, N周期+余りの形に分解できないか?

  • 後ろから見る,指定された操作をするとどうか?

最大公約数

  • 各項が kの倍数のとき、その合計も kの倍数

  • 数列において,整数同士の差を取り合うような状況にある

グリッド

  • 片方の軸にだけ注目するとどうなるか?

  • それぞれの軸は,独立として扱えないか?

  • 「経路が重複しない」を「始点と終点を除いた,すべての格子点が重ならない」と言い換えることはできないか?

  • 最短経路は,始点から終点に向けて,右方向と上方向への移動で達成できそうか?

  • 始点のとり方を工夫できないか?

グラフ

  • さまざまなグラフの種類(完全グラフ,スターなど)の存在を知る

ゲーム

  • 決着がついた状態から,最初の状態に戻っていく.

  • 最適に行動する=相手がどんな行動をとったとしても,自分が勝てるように行動する

  • 変数が多いときは N=2の例で実験する.

構築系問題に対するアプローチ

  • 条件を満たす上限値・下限値を列挙できないか? また,求めた上限値・下限値から,目標とする値に近づけることはできないか?

  • 最後の状態から最初の状態に戻すとどのように変化していくか?

実装における注意事項

  • 無限ループが発生していないか?

  •  N個の配列の両端に要素(0番目と N+1番目)があると仮定できないか?

  • 標準ライブラリで,便利なデータ構造や関数がないか?

データ構造

  • データの追加と最大値を取り出す操作を高速に行いたいときは,優先度付きキューを使う

その他

  • 順位表から得られる情報もうまく活用する.

今後の予定

  • 知見の蓄積

  • 類型化した結果を図で表現

参考

https://github.com/hamko/procon/blob/master/typical.png

shibh308.hatenablog.com

更新履歴

  • 2019/04/30 更新
  • 2019/05/11 更新
  • 2019/05/26 更新
  • 2019/06/23 更新
  • 2019/06/27 更新
  • 2019/06/28 更新
  • 2019/07/17 更新
  • 2019/08/08 更新
  • 2019/08/11 更新
  • 2019/08/16 更新

記事などを執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが、@k_hiro1818までご一報ください。