Trineutronです。AtCoderで黄色上位になりました。
本記事では、これまでにやったこと、現在気を付けていることをできる限り紹介していきます。
対象読者
- AtCoderに参加してある程度たっている人全員
- メインは水色～黄色タッチ
- 最近不調な人向けの記述多め
履歴
一般的な色変記事のメインはこのセクションですが、覚えていないことが多いので飛ばし気味です。
競プロを始める前
親の影響で中学生からプログラミングを始めました。最初に学んだ言語はOctaveです。その後、Fortran、C言語、Haskell、Pythonを触っていきました。
ITmediaのあなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定の問題をHaskellで解きました。当時は5時間弱かかりました。
初コンテスト前
practice contestのA問題とAtCoder Beginners Selectionを解きました。practice contestのB問題に挑戦し200点を得ました。
初コンテスト
初コンテストはTenka1 Programmer Beginner Contest 2019^old ABCでした。3完でパフォーマンス1600を取り、茶色になりました。D問題のThree ColorsはWAでした。
初コンテスト後
practice contestのB問題で満点を取りました1。翌日Three ColorsでACを取りました。
黄色タッチまで
無理なく参加できるコンテストには参加しました。
いろはちゃんコンテストに参加し、C++入門 AtCoder Programming Guide for beginners (APG4b)を埋めました。
けんちょんさんのAtCoder 版！蟻本 (初級編)で紹介されている問題を解き進めていったり、過去問を埋めたりしました。
yukicoderで作問し、コンテストを2回 (yukicoder contest 224、yukicoder contest 256) 開きました。その他単発問題やオムニバス回の出題もしました。
AtCoder Beginner Contest 161で黄色に到達しました。
青～黄エレベーター
ABC埋めなどをやりましたがレートは思うように上がりませんでした。7月から9月までは精進量自体もかなり少なくなりました。
不調
実力の停滞に加え外れの回が続いたことでHighestから200以上レートを落としました。実力はレートほどは落ちていないと思っていましたが、停滞しているのは確かなので精進の方法を見直しました。低難度埋めに偏っていると感じたため、ARC埋めで適正難易度の問題に触れる機会を増やすことにしました。
好調
10月から適正難易度の問題を解いて考察をしっかりすることが功を奏したのか、レートを一気に回復しました。AtCoder Regular Contest 109で15位のパフォ3154を取りレート2200台に到達しました。
コンテストに出る
競プロのレートと実力を上げるために最も重要なのはコンテストに出ることです。コンテスト中やコンテスト前後にすべきことを書いていきます。
コンテスト前
コンテスト参加判断
5分以下の遅刻なら参加することも考えます。それ以上の遅刻、あるいはスマホコーディング2せざるを得ない場合はさすがにやめておきましょう。
参加を見送った場合は後でバーチャル参加しましょう。
コンテスト準備
考察用紙と筆記用具を用意し、エディタを立ち上げましょう。online-judge-toolsをいつでも使えるように用意しておきます。
コンテスト中の立ち回り
問題を見るタイミング
5分ぐらいで解けそうなら解いてしまいます。そうでなければ次の問題を見て同時に考えます。数分ロスする可能性はありますが、高難度の問題を解く確率が上がることで十分カバーできます。ABCの場合はE問題やF問題を見て、A問題から解き始めます。
初回提出判断
コンテスト序盤で1問でも解けたら提出します。30分経っても1問も解けない場合に初めてNoSubを考えます。
初手CE提出はしていません。
考察方針
アルゴリズムに問題を合わせるのではなく、あくまで問題から解法を考えます。制約は問題文を読み終わった段階で見ます。制約まで含めて問題です。制約から解法の当たりを付けることもありますが、罠が仕掛けられていることもあるので頼りすぎに注意しましょう。
難問は部分問題の積み重ねです。問題を言い換えても損しなさそうなら言い換えます。対称性を利用して問題をまとめたり、場合分けで別々に処理したり、何らかの追加の仮定をおいて考えたりすることもあります。小さいケースで実験することでいい性質が見つかることも多いです。
実装方針
まずは以下の記事を読んで基本的な事項を確認しましょう。
高速かつ確実に実装できるならすぐに実装します。少しでも不安があるなら安全な実装を選びます。競プロでも書く時間より読む時間のほうが長くなりやすいです。可読性は常に意識しておきましょう。
変数名は出来る限り一目で意味が分かるようにしましょう[^too long]。特に1文字変数を乱用するとデバッグが非常に難しくなるので、あらかじめ決めておいた用法3以外では使わないのが無難です4。
処理が複雑な場合は、一部を関数に切り出すことを考えます。最長不倒関数[^Never Ending Function]は競プロでもアンチパターンです。考察から実装に移行する段階で関数化を考えることもあります。
言語機能は有効に使いましょう。C++ならSTL、ラムダ式、構造化束縛が有効です。Pythonならスライス、pow関数の第3引数、itertoolsモジュールが強力です。
競プロで使えるC++の言語機能を知りたいなら以下の記事を読みましょう。
再代入される変数はスコープを短くします。グローバル変数への再代入は可能な限り避けます。そうしておくとデバッグ時に調べる範囲を狭められます。
集中力が切れた場合
最高の集中力を2時間も保ち続けるのは難しいので、数分休憩する作戦は悪くありません。問題を頭に入れておいて、部屋を1分ぐらい散歩したりするといいアイデアが浮かぶこともあります。
順位表観戦やTwitterは集中力の回復を阻害するのでやめましょう。
順位表の使い方
どの問題を考えるか判断するときに使います。通している人数や、似たタイプの人が通している問題を見ます。
全完していないなら観戦までしないように注意しましょう。
コンテスト後
考察を開始できた問題
解説を見てACまで取ります。解説は読むだけでは十分に身に付きません。実装することで解法に付随する実装テクニックも身に付けることができます。
知らない知識があった場合
一通り調べてできる限り身に付けます。その知識がコンテストに出る確率は低いかもしれませんが、知らなかった場合のダメージは大きいです。先ほど難問は部分問題の積み重ねと書きましたが、知識が欠けていると部分問題が解けなくなったり、大幅にタイムロスしたりします。
精進
競プロの実力を大きく伸ばすためには精進は欠かせません。おすすめの精進方法や注意点を書きます。
知識を増やす
けんちょんさんのAtCoder 版！蟻本シリーズ（初級編、中級編、上級編、発展的トピック編）がおすすめです。使うアルゴリズムが分かっている状態で解くことで、効率よくアルゴリズムを習得できます。蟻本を手元に置いてどんどん解いていきましょう。
考察力をつける
簡単すぎない問題をどんどん解くのが基本です。
作問するのもよいでしょう。作問では難易度を比較的自由に調整でき、考える時間を取りやすいので考察力を上げるのに有効です。
低難度だけ解いて満足しない
高難度の問題は低難度の問題だけ解いていても解けるようにはなりません。低難度埋めは部分問題のスピードと確実性を上げるのには有効ですが、考察力にはあまり効果がないと感じました。適正難易度の問題もちゃんと解きましょう。
作問
yukicoderで十数問作問しました。主に以下の2つの方法で作っています。
- 生活の中で問題になりそうなことを見つけて、設定や制約を改造する
- 数学的な話題を問題にする
作問の全体的な流れについては以下の記事を参考にしてください。
作問は考察力を上げるのに有効で、何より楽しいので、ぜひやってみましょう！
言語について
C++とPythonを併用しています。欲しい機能があるほうを問題ごとに選択しています。
C++と他言語の比較、およびその他の言語の特徴をまとめます。
C言語 vs C++
Better CでもいいのでC++を使うことをお勧めします。STLが強力です。競プロで使う範囲ではC++のダークサイドは気にならないです。APG4bはC言語からC++に乗り換えるのにも使えます。
C++ vs Python
ABC-DまではC++よりPythonの方がやや有利だと思っています。書きやすい上に読みやすく、デフォルトで多倍長整数が使えるため特にABCの序盤では非常に強いです。
C++の最大の利点は高速なことです。Pythonで通らない問題は少ないですが、C++ではlogを余計につけても通ることがあります。
std::setやACLが使いたい場合はC++を使います。
Haskell
純粋関数型言語の1つで、表現力が異常に高い言語です。
競プロのアルゴリズム分野では利点を生かしづらいと思っています。計算量オーダーが悪化する罠が多く、運用は難しいです。
Fortran
数値計算に最適化された言語です。配列演算は全言語の中でも最強の部類に入ります。行列累乗が短く書けることがあります。
巷で言われるほど悪い言語ではありませんが、配列演算以外のアルゴリズムのサポートが弱い（ソートすらない）のがかなり痛いです。
Octave
初期に使っていただけであまり詳しくないです…
C++の競プロ方言について
競プロではコード長が短く、書く人も1人なので「良いコード」が業務と少しだけ異なります。競プロ特有のテクニックはいろいろありますが、頻出の4つについて意見を書いておきます。
以下の記事も参考にしてください。
#include <bits/stdc++.h>
競プロでは基本的に使ってもいいです。（ただしClangでは使用不可）
人に見せるコードを書く場合は非推奨です。libstdc++以外ではコンパイルが通りません。
using namespace std;
競プロでは基本的に使ってもいいです。コード長が関数数個程度で収まるので名前空間の汚染はあまり気になりません[^global variable]。時々衝突することがありますが、衝突してしまっても同じ動作かコンパイルエラーになることがほとんどで、ペナルティがつく確率は非常に低いです。
人に見せるコードを書く場合でも競プロの文脈なら使って大丈夫だと思います。競プロ以外ではグローバルスコープに置かないのが無難です。
当然ですが、ヘッダファイルにこれを置くのはやめましょう。
#define int long long
未定義動作なので、やめておきましょう。マクロを悪用するのでなしに、エディタの機能を使いましょう。人に見せるコードに使うと、コードを見せる気がないと思われます。
repマクロ
使ってないのでよくわかりません。使うべきなんでしょうか…
不調への対応
コンテストに出てもどんどんレートが下がっていき、Highest-200まで落ちた…そんなときはどうすればいいのでしょうか。答えは1つです。
気にせず精進して、いつも通りコンテストに出ましょう。
レートシステム上、-200ぐらいの不調は誰にでも起こりえます。そして実力を上げること以外に回避する方法はありません。実力を上げることに集中しましょう。
どうしても不調から抜け出したい！
精進&コンテスト後
精進に問題がないかこの機会にチェックしましょう。
精進を怠っていませんか？
問題に集中して向き合っていますか？
低難度埋めだけで満足していませんか？
コンテスト後は解説を読むだけでなくACまでしていますか？
思い当たる点があるなら修正しましょう。
コンテスト中
コンテストに出る前に「どうせ冷えるんだろうなー」と思っていませんか？
不調で一番怖いのはコンテスト中の集中力が下がることです。以下の記事では、いつもの集中力を保てなくなる怖さについて書かれています。
- AtCoderで青になりました (asdf1さん)
レートを気にせず、問題を解くことに集中することで不調から脱出できるかもしれません。
それでも競プロが辛くなったら…
辛くなったらいったん距離を置いて、戻りたくなったときに戻りましょう。プロ競プロ選手でもなければ無理に続ける必要はありません。
以下の記事は麻雀の話になりますが、競プロにも通じるものがあると思います。
- 麻雀との向き合い方 (zeRoさん)
その他重要なこと
冷えそうなとき
コンテストに出ていると冷えそうになることがあると思います。そんな時は簡単に諦めずに、「自分は冷えない！」と思いましょう。体感3割ぐらいの確率でうまくいきます。
冷えたとき
当たり回と外れ回でパフォーマンスは600ぐらい差が出るものです。急速に実力を伸ばしているのでない限り、冷えるときは冷えます。冷えたときは引きずらずに、解説を見てACを取るなど次につながることをしましょう。冷えたときは新しい知識を身に付けるチャンスでもあります！
むやみに他人と比較しない！
競プロは個人差がかなり大きいため、むやみに他人と比較するとモチベーションが下がる原因になります（特にレート差が大きい場合）。chokudaiさんのツイートでも触れられています。
【競プロの各色に対する認識オススメ】
— chokudai(高橋 直大)🍆 (@chokudai) June 29, 2020
・２色上は人外だと思うのが大切！比較しちゃだめ！１色上に追いついたところで人間に戻してあげよう！
・１色上は強い人！目標にするのは良いけど勝てなくて当たり前！いつかは追いつけたらいいなくらいに思おう！
・同色でも成長がヤバいやつはやっぱり人外！
他人と比較するのは「他の人が頑張ってるから自分も頑張ろう」と思えるときだけにしましょう。
まとめ
競プロで感じていることを一通り書きました。レッドコーダーから見ると分かってないことだらけだと思いますが、自分なりに考えたことをまとめてみました。この記事が誰かの役に立てば嬉しいです。
-
強引な場合分け。3か月後、よりシンプルな解法で解き直し。 ↩
-
唯一の茶パフォはスマホコーディングで参加した回です。
[^Never Ending Function]: 最長不倒関数の元祖
[^too long]: 長すぎる変数名を使うと逆に可読性が下がることがあるので、短くしても意味が通じるなら適度な長さに抑えましょう。 ↩ -
i, jはループカウンタ、問題文と同じ文字は入力そのもの、など。ただしループカウンタに意味がある場合2文字以上にすることもあります。 ↩
-
よく考えずに1文字変数を使って、「このsは何だっけ？」となってデバッグに時間を取られたことが何度もあります。
[^global variable]: グローバル変数を乱用すると危険性が上がりますが、それでも気にならないことが多いようです。 ↩