@@https://past.atcoder.jp/競技プログラミングコンテストサイトAtCoderが、有料の検定を始める。会社が社員や応募者に対して試験を受けさせる[TOPSIC](https://products.sint.co.jp/topsic)に対して、AtCoderは今も問題を卸している。今回の検定は会社の採用に応募しようとする人が受けるのが主だろうか。それなら無料で毎週のコンテストに出てレートを獲得すれば、「AtCoderで黄色です」も「アルゴリズム実技検定エキスパートです」も同じ事だと思うのだけど、一度のコンテストで結果が出るのがウリらしい(AtCoderの普段のコンテストはある程度の回数をこなさないとレートが付かない)。dir="ltr">・「一日の受験でAtCoderの色と同等の評価が得られる」が最大のメリットです。レーティングを持っている人にはちょっとメリットが小さいです。2019</a></blockquote>仕事が忙しくて、お金はあるけれど時間が無いという人向けと。時間を掛けるかお金を払えというのはソシャゲーっぽい。この資格やAtCoderのレートで選考が有利になったり会社から報奨金が出たりするという流れに期待しているので、仕事でプログラムを書いているけれど競技プログラミングはやっていないという人向けに記事を書いてみる。実務の役に立つのかTwitterなどで定期的に燃えている話題である。大百科に端的にまとまっている。競技プログラミングをやると、可読性より速度を優先するため、汚いコードを書く癖がつく。競技プログラミングをいくらやったところで、ライブラリの使い方や設計技術は身につかない。競技プログラミングのランキングをあげても就職の役には立たない。競技プログラミングを極めた人のコードは美しい。美しさが分からないのも無能の証。競技プログラミングを通じてアルゴリズムの考え方を身につければ、設計などもおのずと洗練されてくる。計算量の見積もりもせずに設計してプロジェクトを破綻させるのは、非競プロerの方。お前らIT土方の就職には役立たないが、一流の人材を求めるところでは評価する会社もある。https://dic.nicovideo.jp/a/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0私の考えだと、AtCoderの300点問題(サンプル問題のF)くらいまでは業務でプログラムを書けるかどうかと相関がある。300点くらいの問題が解けるならば業務のプログラムも書けるし、業務でプログラムが書けるなら300点くらいまでは解ける。それより先は、競技プログラミングのほうは業務で使わなそうなアルゴリズムとかの知識と技術が必要になるし、業務のほうもライブラリの使い方とか設計ができるのかという話になってくるのであまり関係が無い。野球選手がサッカーをすればその辺の人よりは上手いだろう、程度の繋がりはあると思う。アルゴリズム実技検定の配点が興味深い。難しい問題ほど点数が低い。サンプル問題は過去のコンテストの問題から持ってきているので点数が書かれているけれど、この点数でもなお難しさには合っていないと思う。点数が100点から200点くらい増えると、解くのに掛かる時間が倍掛かるイメージ。AtCoderとしても、300点から400点くらいの問題が解けるかどうかを見分けられるようにしたいという意図があるのだろうか。|問題|元の点数|検定の点数|累積|先頭から解いたときの称号||---|--:|--:|--:|---||A|100|9|9|-||B|200|8|17|-||C|200|8|25|エントリー||D|300|7|32|エントリー||E|300|7|39|エントリー||F|300|7|46|初級||G|400|6|52|初級||H|400|6|58|初級||I|400|6|64|中級||J|500|6|70|中級||K|500|6|76|中級||L|500|6|82|上級||M|600|6|88|上級||N|600|6|94|エキスパート||O|600|6|100|エキスパート|業務に関係のないところがむしろ楽しいという考えもある。保守性とか他人が読みやすいとかそういうことは一切気にせずにコードを書き殴れる。サーバー側でのチェックさえ通れば、もう読み返すこともない。業務ならテストは通ったが実可動で大丈夫だろうかと不安になることもあるけれど、競技プログラミングならばたとえバグっていてもチェックが通ったなら勝ちである。Tips普段プログラムを書いているけれど、AtCoderのコンテストに出たことがない人向け。ググって良い普段のコンテストで「2人以上で結託し、解答する行為」は禁止されているので、チャットで他人に相談したりするのはNG。コンテスト中のインターネットの使用は禁止されていない。アルゴリズム実技検定でも多分同様でしょう。[オンライン整数列大辞典](https://oeis.org/?language=japanese)(OEIS)というサイトがあって、数列で検索ができる。数列の計算式も出てくる。これで検索するだけで解ける問題もある。作問者にしてみれば面白くないので、めったにないだろうけど。使うアルゴリズムを事前に書いておいて、それをコピペして使っても良い。ある程度慣れた人はみんな自分用に用意していると思う。何度提出しても良いAtCoderはコンテスト終了後にまとめて採点される形式ではない(他のコンテストではそういう形式もあるけれど)。提出したコードが間違えていると、普段のコンテストでは5分のペナルティ(同点ならば解答時間順に順位が付くところ、5分遅く提出したのと同じ扱い)。アルゴリズム検定では1分間再提出ができないだけ。検定中に問題に正解すると点数を獲得できます。正解時間は不正解の回数は問いません。検定中に何度でも同じ問題に提出することが出来ますが、同じ問題に1分以内に再提出することはできません。https://atcoder.jp/contests/past-sample「合っているとは思うのだけど、いまいち確信が持てないなぁ」くらいならば、さっさと出してしまったほうが良い。標準入出力を扱えますか?AtCoderのコンテストでは、標準入力から入力を読んで、答えを求めて標準出力に書き出す。world`を標準出力に出力するところから始めると思っていたのだけど、ウェブアプリやスマホアプリをバリバリ書いていても、意外と標準入出力の扱い方を知らない人もいるらしい。dir="ltr">プログラマーに競技プログラミングを勧めたら「標準入出力って何?」みたいな事を言われて、「何言ってんだこの人......」となったけど、ウェブアプリとかから入るとマジで標準入出力は全く触らないままらしい。2017</a></blockquote>コンテスト前に自分の使う言語での標準入出力の使い方は確認しておいたほうが良い。ここに一通り載っている。デバッグ問題に書かれている入出力例と違う結果が出たり、セグフォしたりするならば、普通にがんばってデバッグ。`printf`デバッグが意外と有用。デバッガでループごとに変数の値を確認するくらいなら、全部出力してしまったほうが速いことが多い。入出力例はあっているのに、提出してみると不正解になる場合がやっかい。2個だけ不正解になる場合は境界条件の見落としが多い。`0<=N<=1000`みたいな問題の`N=0`の場合に特別な処理が必要で、それが抜けているとか。半分くらい抜けているときは、まずはオーバーフローを疑う。ある値が32ビットより大きくなりうるのに32ビット変数で扱っているとか。しようもなければ、遅いけど確実なナイーブな解法を実装して、小さなテストケースをランダムに生成して出力を比較。出力が間違えるのではなく解法が分からない場合も、ナイーブな解法を実装して色々な入力に対する出力を見ていると、解法が見えてくることもある。「アルゴリズム」実技検定なので時間計算量は重要。AtCoderの場合、空間計算量の問題になることはあまりない。言語によって差が大きいかららしい。n)$とか)は?」と気にすることがあっても、実時間で何秒かを気にすることはあまりないのではないかと思う。競技プログラミングをやったことがない人に「こんな問題を解いているのか。簡単じゃん?」と言われて、良く聞いてみたら、制限時間に全く間に合わない解法だったということもあった。AtCoderのコンテストはだいたい2秒。問題によってはもうちょっと長い。雑な見積もりとして、C++ならば、オーダーの変数に制約の最大の値を入力してみて、1,000万くらいならだいたいOK。Pythonなら100万くらい。JavaやRubyはその間に入る感じ。これを逆手に取ることもできる。作問者の心情としては想定解法よりも簡単だけど遅いプログラムで通されたくはないので、制約をなるべく大きくする。いうことは、上記の100万から1,000万くらいになるような制約になる。想定解法のオーダーが推測できる。8$なら$O(nn!)$とか。Contestの過去問を解けば良いと思う。最初から解きたくなるところだけど、難易度や問題傾向が違うので、最近の問題から解いたほうが良いと思う。本を買うなら、[プログラミングコンテストチャレンジブック](https://book.mynavi.jp/ec/products/detail/id=22672)(通称「蟻本」)がオススメ。サンプル問題の解説https://atcoder.jp/contests/past-sample/tasks一通り解いてみた。ちなみに、これらの問題は過去のAtCoderの問題そのままなので、問題名か問題のファイル名で検索すれば出題されたときのコンテストが出てきて、そこに公式の解説もある。本番でこれらの問題(や過去のAtCoderの問題)が出ることはないだろうから、これらの問題の解法だけを覚えても役に立たないので、なるべく汎用的な考え方とかを書いてみる。私の解法の言語はPython3かC++。Thttps://atcoder.jp/contests/past-sample/tasks/abc133_a素直に解くだけ。100点問題はループを使わなくても解けるようになっているらしい。Coasterhttps://atcoder.jp/contests/past-sample/tasks/abc142_b200点問題も特に難しいことはない。計算量などを考える必要も無い。Exceededhttps://atcoder.jp/contests/past-sample/tasks/abc112_b`t`が`T`以下で、`c`が最小のものを出力。Unificationhttps://atcoder.jp/contests/past-sample/tasks/abc120_cここから300点。問題の通りに実装するだけでは解けなくなってくる。10^5$なので、キューブの取り方を総当たりすると当然間に合わない。このような「○○な部分を選んで××します。最大何回○○できますか?」というような問題は、「その選ぶことに意味はあるのか?」ということをまず考えると良い。この問題では意味が無い。赤と青のキューブが残っていればどこかが取り除けるのだから、赤か青の多いほうが残るだけである。選び方によって取り除けるキューブの個数が変わることはない。取り除けるキューブをどれでも良いので貪欲に取り除いていけば良い。素直に取り除く処理を実装すると、実装方法によっては、$O(N^2)$になってしまって間に合わない。考えてみると、もうキューブの並びとかどうでも良くて、個数だけ見れば良いことが分かる。青の個数)`回取り除ける。IDhttps://atcoder.jp/contests/past-sample/tasks/abc113_cこういう書式指定文字列が必要になる問題はAtCoderでは珍しい。検定ではこういう問題も出していくぞということだろうか。各市ごとに、自分より早く誕生した市を数えていては間に合わない。年順にソートして、ある県に市が何個あるのかを数えておけば良い。「処理する順番を変えられないか?」という発想が重要。入力の先頭から順番ではダメ。Binhttps://atcoder.jp/contests/past-sample/tasks/abc137_cアナグラムを全て試していては間に合わない。「`A`に何か操作をして`B`になるとき~」のような問題では、`f(A)=f(B)`となるような操作`f`が無いかを考える。アナグラムの場合、`f`は文字のソートである。競技プログラミングの場合、平均的な計算量を小さくすることに意味は無く、最悪ケースの計算量を小さくする必要がある。この問題の最悪ケースは全ての文字列がアナグラムになっている場合。このとき答えは`N*(N-1)/2`。アナグラムになる組み合わせごとに`+1`するような解法では間に合わない。下の解法では自分よりも前に出現した自分のアナグラムを数え上げている。Arrayhttps://atcoder.jp/contests/past-sample/tasks/abc130_dある範囲が`K`以上という条件を満たすならば、その範囲を含む範囲は全て条件を満たす。条件を満たす範囲だけ探していって、それより広い範囲は何個あるかを足し合わせれば良い。「しゃくとり法」を使う。`K`以上ならば範囲の左端を右に動かして狭め、`K`以下ならば範囲の右端を右に動かして広める。各左端`l`に対して右端を探す感じにすると綺麗に書ける。Ticketshttps://atcoder.jp/contests/past-sample/tasks/abc141_d合計金額を最小化しろという問題。各商品に割引券を1枚使うと合計金額をいくら安くできるかを考える。商品の現在の金額の半分なので、なるべく金額が高い商品に使ったほうが得。値を追加と、最大の値の取り出しとが高速にできるデータ構造があれば良い。Pythonの`heapq`は最小の値が出てくるので、符号を反転させて入れている。Lamphttps://atcoder.jp/contests/past-sample/tasks/abc129_d各マスについて、`O(照らすマス)`かかるアルゴリズムでは間に合わない。上下左右に分けて考える。一方向だけならば壁から数えていけば`O(HW)`で計算できる。後は各マスについて上下左右を足し合わせれば良い。いう問題は事前に周囲に壁を作っておくとプログラムを書くのが楽になることがある。Pythonだと間に合わなかった。がんばればたいていの問題はPythonでも通せるらしいけれど、がんばるのが面倒なので私はC++を使います。exceed(TLE、実行時間オーバー)のケースの実行時間は2秒ちょっとだけど、これは2秒を超えると実行が打ち切られるからであって、あと0.2秒高速化すれば間に合うわけではない。Everythinghttps://atcoder.jp/contests/past-sample/tasks/abc142_e500点。`N`の制約の小ささに気が付ければ勝ち。12$なので、$O(2^N)$が間に合う。「後の計算が依存するものは何か」を考える。状態のうち依存しないものはまとめてしまい、状態の数が計算できる範囲に収まれば良し。この問題の場合は、鍵を先頭から順番に使っていくと考え、`何番目までの鍵を考慮したか`と`どの宝箱を開けたか`。これが同じならばどのような鍵の組み合わせて宝箱を開けていたとしても、後の計算には影響しない。`何番目までの鍵を考慮したか`はループ変数として持っているので、`どの宝箱を開けたか`ごとに最小の金額をメモしておけば良い。Impurityhttps://atcoder.jp/contests/past-sample/tasks/abc138_e$10^{100}$に面食らうけれど、これは無限大と思っておけば良い。無限大だと問題をきっちり定義するのが大変なのでしょう。遅くても良いから解ける方法を考え、それから速くする。`t`を先頭から見ていき、`s'`の中から探すという解法が思いつく。この解法は$O\left(\left|s\right|\left|t\right|\right)$。`s`の各場所ごとにある文字`c`が次に出てくるのはどこか?が高速に得られれば良い。これを事前に計算しておく。Leaguehttps://atcoder.jp/contests/past-sample/tasks/abc139_eこれもK問題と同様に、遅い解法をまず考えて高速化する。ある日、選手`x`が選手`y`と、選手`y`が選手`x`と試合をしたがっているとき、`x`と`y`が試合をしない理由はない。貪欲に試合をしたがっている選手の組み合わせを探すのに$O(N)$それを$O(N)$回で間に合うかと思いきや、試合の最大日数は$O(N)$ではなく$O(N^2)$になりうるので間に合わない。最適な試合の日程で、ある日選手`x`と選手`y`が試合をするならば、その前日に`x`もしくは`y`の少なくともどちらか一方は試合をしているということに気が付けば解ける。どちらも試合をしていないならば、`x`と`y`の試合が前日にできるから。いうことで、各日に試合をした選手を覚えておいて、その選手だけ次の日に試合をするかどうかを調べれば良い。Minimahttps://atcoder.jp/contests/past-sample/tasks/abc127_f600点問題。