夕立進行会報

AtCoderをやっているからには色変記事というものを書きたかったのだが、以前水色に到達したときはすぐに落ちてしまったのでタイミングを逃していた。ようやくまた水色になったので記事にまとめてみる。 レート遷移 こんな感じ。緑にはすぐなれたけど、その後は2年近く停滞していた。 レベル感 職業プログラマーから見た水色までの問題のレベル感。あくまで個人の感想。 灰色 チュートリアル。とりあえず文法を覚えよう。 茶色 初学者なら及第点。仕事でプログラムを書く人には普通に解けてほしい。文字列操作やコレクションの使い分けなど普通にプログラムをバグらせず実装するのに必要になってくる。ただ競技プログラミングでは典型であっても、業務ではあまり使わないものもあるので、初見で解けない問題があってもおかしくはない。 緑色 必要な知識が競技プログラム特有になり、プログラマでもぶっつけでは解けない問題が多いと思われる。Union-FindやSegmentation-Free、ダブリング、座標圧縮、動的計画法など、既存のアルゴリズムを色々と知る必要がある。ただそれらを理解さえすれば解けるので、地道に一通り覚えれば到達できるだろう。 水色 既存のアルゴリズムを組み合わせたり応用が必要になる。もしくは数学要素（漸化式や数列、組み合わせなど高校数学～）の少し複雑な問題が出題される。考察が必要になるため、難易度が高くなる印象。 私は緑にはすぐなれたが水色は時間がかかった。これより上の色は解ける気がしない。 ABCの難易度向上について 近年でABCのレベルが上がっている論がある。下位領域の絶対評価であれば、確かに難しくなっていると言える。特に典型問題のパフォーマンスがガタ落ちしている。これは過去問や解説の充実などにより、典型問題が習得しやすくなったためと思われる。 一方で類題が少なかったり典型から外れた問題は正答率が落ちる。相対評価で言えば参加者のレベルが上がったというよりは、環境が整ったと言う方が正確だろう。 なお仕様変更でUnrated戦略（問題が解けた場合だけ参加する）が使えなくなったため、変に低いレートが出ることは減った。 学習法など シンプルに過去問題を解きながら分からなければ解説を読むのが基本。場合によっては別途アルゴリズムの解説を探す。典型のアルゴリズムなどは、その中身を理解しているかどうかで...

気づけばだいぶほったらかしになっていた。今日は競技プログラミングで出てくる「～で割ったあまりの数」についての覚え書き。 AtCoderでよく出てくる以下の文。 ～を10^9+7で割った余りを求めてください。 競プロ特有の表現なので初見は「なんのこっちゃ？」と思った。要は答えが通常の数値型では表現できない大きな数になるので、1000000007の剰余を答えろということ。 当然割る前の数を求めるとオーバーフローするので、途中途中で剰余をしながら答えを求めるわけだが。 (a + b) % m → (a % m) + (b % m) 各四則演算について上記のような置き換えが可能であることを確かめる。 証明 任意の二つの数x1,x2を以下のように定義する。 x1 = aM + c x2 = bM + d ※Mは除数、a,b,c,dは任意の整数 なお以下では除数Mでxの剰余を取ることを「x mod M」と記載する。 加算 y = x1 + x2 = (aM + c) + (bM + d) = (a + b)M + c + d y mod M = c + d = (x1 mod M)+(x2 mod M) よって (x1+x2) mod M = (x1 mod M)+(x2 mod M) 減算 加算と同じである。ただしプログラムの実装では計算過程で負の値が現れる可能性を考慮し、負値の場合Mを加算する処理を入れる。 乗算 y = x1 * x2 = (aM + c)(bM + d) = abMM + adM + bcM + cd y mod M = cd = (x1 mod M)(x2 mod M) よって (x1 * x2) mod M = (x1 mod M)(x2 mod M) 除算 ここまでは感覚的に理解してる人も多いと思う。除算だけ少し毛色が異なる。実はここが本題。 除算は以下のようにこねくり回してもMの倍数と定数項の形にできない。 y = x1 / x2 = (aM + c) / (bM + d) = aM / (bM + d) + c / (bM + d) つまるところ (x1 / x2) mod M = (x1 mod M) / (x2 mod M) は成り立たない。 ここで フェルマーの小定理 というものがある。その詳細や証明はひとまず置いてお...

空き時間に AtCoder というサービスをやってみたので感想や環境など。 概要 AtCoderは日本企業が運営している競技プログラミングのサイト。毎週主に土曜日の夜に定期コンテストが開かれていて、Webから登録すれば簡単に参加することができる。 コンテストの流れ コンテストは事前に告知された時間にみんなで一斉に行う。 開始時間になるとページに問題が表示されるので、それに沿うようにコーディングを行う。 ソースコードをWeb画面から送信するとサーバでコンパイル、テストケースが実行され成否が判定される。正解した問題数と回答時間で順位が決まるようだ。 プログラミング言語はC++やJavaなどの選択肢から選ぶが、主要なものはほぼ揃っている。COBOLなんかもあるが流石に利用者はほぼ見当たらない。自分はC#でやっている。 所感 プログラミングというよりはアルゴリズムのコンテストといった感じで、数学的な問いをプログラムで実装するようなものが基本。 評価は「インプットに対するアウトプット」「計算時間」「回答時間」でされるので、コーディングのフォーマットやエラー処理なんかは特に問われれない。 難易度 毎週やってるBeginner Contestは難易度準にA～Fまでの問題がある。 ABは初学者教本にあるような基礎。足し引きと分岐・ループができればだいたいOK。 Cは数1Aぐらいまでの内容で、プログラミング的にも再帰やコレクションの使い分け、計算量を想定した実装が必要になってくる。普通のプログラマはこのあたりが及第点だろうか。 Dからは動的計画法や漸化式みたいな考え方が出てくるし、既知のアルゴリズムをベースにしたりする必要があるので、現役理系学生以外は対策しないと厳しい。 実務に活かせるか 内容がアカデミック寄りなので、ほとんどの現場ではあまり直接的な関係はなさそう。実際の業務コーディングではアルゴリズムより機能の切り分けや将来設計、速度より安全な実装と適切なエラー処理などの方が大事になってくる。 検索エンジンやミドルウェアを作るならそういう機会もあるかもしれない。 就職アピールなら評価の対象は問題そのものよりも、プログラミングへの興味の高さや、やっていくうえでの工夫や学習法あたりになるだろうか。 コーディング環境とか 一応Webサイト上にデバッグ環境みたいなのはあるが、すべてそれで...