知能大安売り

知識を売買 読者がバイバイ メェ～ン😭

shop_oneメソッド！～早解きの極意～(茶色上位〜水色の人向け)

タイトルはこれです。

この記事は、早解きを強くしたい人の為の記事です。一応ベースはABCを想定して書いています。
早解きでレートを稼ぐまで言わずとも、この記事で苦手の解消ができれば幸いです。
僕も正直早解きが得意ではなかったのですが、結構精進量でカバーできます。 今では立派な早解き芸人です
早解きと聞いたらうげぇ〜となってしまう人もチラッと見てみて下さい。

早解きの効能

(ここポエムなので飛ばしても何の問題も無いです)

早解きの強化は、特にAGCで2問解くのは厳しい、500~点が解けない事が多い人に強くオススメします。
理由としては、AGCやARC級コンテストに気楽に出れるようになるからです。これが一番だと思います。
後は自分のレート帯の問題に当たれる時間も長くなるので、解ける確率も高くなり、 パフォーマンスに安定感が出てきます。
とはいえ難しい問題が普通に通せるのなら今更強化する必要も無いんじゃないかなと思います。

早解きのエッセンス

だいたいこんな感じだと思います。

  • バグらせない
  • ペナを出さない
  • 考察を素早く正確に仕上げる
  • (タイピング速度)

誰しもどれかしらに引っかかっているとは思います。

早解きの手法

バグの除去

まずはバグをコードに埋め込まないような考察と実装についてを述べていきます。
バグらせる原因はだいたい2つです。

  1. 実装で埋め込むバグ
  2. 考察の甘さから来るバグ

実装によるバグとは、

  • 2重forのカウンタ使い間違え
  • 変数の初期化忘れ
  • 変数名の重複
  • whileループ条件書き間違え
  • 配列サイズ

等です。
大抵の場合サンプルが通らなかったりするので提出前には気がつく事がほとんどですが、 時間の無駄です。なるべく取り除いていきましょう。

これについては沢山コードを書いて、いつもの書き方を徹底することが重要だと思います。
これは思いつく例ですが、

  • 入力を受け取らない変数は最初に初期化
  • while(que.empty())になっていないかの意識
  • 合計するなら必ずsumにする
  • 関数の返り値ならres
  • for文は使わずREPマクロを使う
  • 強力な静的コンパイラやサジェストを使う
  • intは使わない

少しずつ自分なりのルールを決めていきましょう。
ミスが目立つ場所はマクロ化したり、どこかにメモしてコーディング中に思い出したりする事も効果的です。
この部分は実装力も問われるので、実装力に不安のある人はJOIやAOJ-ICPC埋めも選択肢に入れて もいいと思います。
特にAtCoderしかしていないと、重い実装に突然触れる事になるため困惑してバグを埋め込みやすいです。
ただ、闇雲に実装するのではなく、どのように実装すると楽でバグが出にくいかと 考えるのを含めて実装力です。

考察の甘さによるバグは配列の添字が違ったり、コーナーケースを見落としていたりです。
こちらはサンプルは通るときがあるので、ペナもつきより痛いバグです。

今回はコーナーケースへの対応を考えてみます。
コーナーケースは、特にABC-Bくらいまでだと無駄な高速化を考えたりして起きるケースが多いです。
ABC-Bくらいまででは無理にO(1)解法を考える必要はありません。 全探索が楽に書けるならそれが一番です。

ABC-C,Dでは愚直シミュレーションや全探索は通らないことも多いので、 うまく辞書型等も使って自明なままにできそうな考察を考えてみましょう。
これらが駄目そうなら、普通に解くしかありません。
幸い、ABCでえげつないコーナーを出してくることは早々ないです。
色々コーナーケースは考えられるのですが、最低限、 それぞれの値の最大値最小値を手入力して壊れないか位はチェックしましょう。
ダメだった場合は、落ちてるケースの個数からコーナーケースなのか、 もしくはただの嘘なのかをおおよそ判別できます。

また、計算量の概念の把握は必須です。おおまかでいいので計算量の把握はしましょう。
今回は全探索しても大丈夫、今回はシミュレーションしたら間に合わないと、 素早い判断を下すため、ざっくりでいいので何が出来て何が出来ないの仕分けをしましょう。
logについては、不安なら*50程度を考えると良いと思います。
また、サンプルを試さないのは危険です。絶対に自信が合っても試した方が良いです。
FA狙いの人はしなくていいと思います。僕はやったこと無いのでわかりません。

精進方法としては、考察は自分にとって簡単だけど、実装が比較的重い問題を、サンプルを 試さずに提出するのがおすすめです。自分のコードを見る力が付いてくるはずです。

練習問題(反転すると解き方の例が書いてあります)

だいたい茶色〜緑前半から集めました

  • C - 数を3つ選ぶマン
    考察するとなんかいい感じの解法が浮かびそうですが3重for文を回してソートのほうが事故が起きにくいです。
    自明なので考察のミスもありません。
    3分以内に解きましょう。

  • B - Minesweeper
    周囲八方向をどう書くか、は決まった方法を考えておくと良いです。僕は
    vx={0,1,0,-1,1,1,-1,-1},vy={1,0,-1,0,-1,-1,1,1}
    としてしまうことが多いです。(これはグリッド上で動く時にも応用できます)
     5,6分以内に解けるといいペースです。

  • B - Ringo's Favorite Numbers
    高速化を狙おうとするとコーナーケースに引っかかりやすいです。
    一番大きな答えもそんなに大きくならなそうなので、そういう時は全探索です。
     3,4分で解けるといいです。

  • D - Lucky PIN
    たかだか101010通りの種類しか無いので、全て可能かどうかを考えてみます。
    シュミレーションにはO(N)しかかからないので今回は通ります。
    ですが、例えば暗証番号が4桁だったりNがもっと大きかったりすると、 途端に雲行きが怪しくなります。
    107か108程度に収まるかが大事です。
     10分くらいが目標です。

エスパー力

こちらの方が重要性が高く思います。ここはなんか普通の競プロ考察記事みたいになってしまいました。
エスパー力を高めて、問題分を削ぎ落として読みましょう。

スムーズに解くためには、入力を受け取るプログラムを書きながらまず制約をみてエスパーをするように僕はしています。
まあ問題見ながら書くか、考察終わってから書くかは好きな方で良いと思います。

たとえば

  • N=10~20で全探索
  • N=300~500でグラフっぽいならワーシャルフロイド
  • dpの香り
  • クエリなら何らかの前計算

エスパーしにくい制約なら問題文を見てみます。

  • 〇〇な値を求めよでN=105なら二分探索、
  • 合計が欲しそうなら累積和(いもす)
  • なんかソートしたそう

このようにおおよそのアタリを付けてからいざ問題に取りかかります。 外れてたり、Ad-hocならしょうがないので考察し直しましょう。

次はよくある解法を考えてみます。
例えば

  • 2つの文字からなる文字列を圧縮すると分かりやすい ((L,R)等)
  • 単調増加が途切れた部分を見る
  • 木なら根か葉に注目
  • 貪欲が正しい
  • 行動の順番を入れ替える事が可能である
  • x座標とy座標は独立に考えられる
  • ゲームなら圧倒的有利がどちらかを考える
  • グラフで距離を求めたら何か見える
  • XOR系は上位(下位)桁から独立に考える
  • なんかセグ木で殴れる

これも無限にあるので列挙は不可能です。
問題に出会った時、過去問に似たようなものは無かったかを考えてみましょう。

練習方法は、精進中も同じように似た過去問をイメージすることです。

練習問題

こちらは先程より難易度が上がります(緑中後半)。茶色だと少し厳しいかもしれません。

  • C - Switches
    N=10,もう全探索だけを考えます。
    改めて問題分を読むとtrue false全探索をするだけと分かるのでやりましょう。
     7分くらいで解けると良いです。

  • D - Integer Cards
    操作をする順番の言い換えが出来そうなので、そうして考えてみます。
    すると、貪欲に取る方法が見えてきます。
    Cが大きいので正しく実装しないとTLEしますし、適当にやると面倒くさい実装になってしまいます。
     8分で解ければ良いと思います。

  • D - 2017-like Number
    これまた複合系です。
    まずクエリなので前計算、そして和が欲しいそうなので累積和が考えられます。
    和が欲しいということで、それぞれの数字が2017likeかの判定をしたいです。
    すると、一つ一つの判定を高速化するために必要なのは素数判定の高速化です。
    色々な素数判定をするので、エラトステネスのふるいを考え、実際間に合いそうなので全ての数字について 2017likeかを判定し、累積和を取ることで全てのクエリがO(1)となります。
    このように複合してても一つ一つを考えることでいつものに落とし込めます
     10分程度で解けたら結構慣れて来ています。

おまけ タイピング速度

滅茶苦茶な速さは要らないと思いますが、最低限は必要です。
適当ですがe-typingでAくらい出来るとまず間違いないと思います。
それよりかはテンプレートやスニペットを充実させる方が良いと思います。
また、磨くなら速度より正確性を磨きましょう。

まとめ

記事がとっちらかったので無理やり纏めます。

  1. 実装力を疎かにしない
  2. なるべく自明な方法で解く
  3. 過去の近い問題を思い出して考察を素早く

早解きは精進料が物を言うと思っています。引き出しを増やしましょう。
少し意識しながら精進するだけで違うと思うので、今日から少しずつやってみてはいかがでしょうか。

追記

僕のスニペットとマクロの仕様状況とかも書いておきます。
僕はあまりスニペットマクロは使わないです。REPマクロもやってません。
せいぜい開始時にインクルードファイルとmain文をささっと書いてくれる物しか使いません。
ライブラリとかは、使う頻度が高い順にUnionFind,エラトステネス,SegmentTreeです。
これもあまり使わずですが、早解きに上２つはあると気楽かもしれません。