Educational Codeforces Round 34 E. Swapping Characters

公式解説をベースにした詳細な解説をします

解説

計算量の考察

最初に計算量についての考察をしておきます.

  •  1 \leq k \leq 2500
  •  2 \leq n \leq 5000
  •  k \cdot n \leq 5000

一見すると  O(kn) しか許されないように見えますが,3 番目の制約を考慮すると  O(k^{2}n) もしくは  O(kn^{2}) が許されることが分かります.

愚直解

素直に全探索することを考えてみます.

ある文字列における任意の文字ペアをスワップして得られる文字列は  n(n+1)/2 個あります.これをオリジナルの文字列  s だと仮定して,残りの文字列とそれぞれ突き合わせて差分を確認することで答えを得られますが,計算量は  O(kn^{3}) となり TLE します.

また,文字列ごとに  n(n+1)/2 個の文字列を列挙して連想配列などで数え上げる方法も考えられますが( k 回出現した文字列が答えとなる),この方法だと MLE します(しました).

想定解

愚直解の前者の計算量を改善することで解くことができます.

面倒ですが,真っ先に文字列の検証を行う必要があります.文字列  s_{1}, ..., s_{k} はオリジナルの文字列  s から 1 回のスワップで得られる文字列であるため,当然ながら文字列を構成する各文字の個数は一致するべきですが,その保証はないので確認する必要があります.それが満たされていなければ  -1 が答えです.サンプル 3 がまさにこのケースとなっています.計算量は  O(kn) です.

異なる文字列ペア  (s_{x}, s_{y}) を探索して 1 つ見つけます.これが見つからなければ全体で文字列は 1 種類しかないということですから,適当に文字ペアをスワップすれば答えになります( k = 1 のときもまとめて処理できるような実装にしておく).計算量は  O(k^{2}n) です.

異なる文字列ペア  (s_{x}, s_{y}) において, s_{x,p} \neq s_{y,p} なるインデックス  p を探索して配列  pos に格納します.例えば, s_{x} = "abcd",  s_{y} = "aacc" のとき  pos = \{1, 3\} です(0-indexted).このとき, pos のサイズ  \mathrm{size}(pos) が 4 を越えていた場合は辻褄が合わなくなるため  -1 が答えです(オリジナルの文字列  s におけるスワップ位置を上手く選んだとしても,2 つの文字列の違いは高々 4 文字にしかなり得ないため).

 diffpos \in pos を順に取り出し, s_{x} における  diffpos 以外の任意の位置とスワップして得られる文字列  t を考えます.このような文字列  t \mathrm{size}(pos) \cdot (n-1) 個あり,その全てが答えの候補となります.よって,ある文字列  t と各文字列  s_{i} (i \neq x) を突き合わせて一つも矛盾が生じなければそのときの文字列  t が答えになり,すべての文字列  t で矛盾が生じたら  -1 が答えになります.計算量は  O(kn^{2}) です.

文字列を突き合わせたときの確認方法ですが,オリジナルの文字列  s から 1 回だけスワップした際,同じ文字同士であれば 0 箇所,違う文字同士であれば 2 箇所の差分が発生します.つまり,文字列  t と各文字列  s_{i} (i \neq x) の差分  diff をそれぞれ数え上げて  0, 2 にならなければ NG です.さらに, diff = 0 のときは「同じ文字同士のスワップ」が必要になるため,ある文字が 2 個以上含まれていることが要請されることに注意してください(どの文字列も各文字の個数が一致することは事前に確認済みなので,適当な一つの文字列においてある文字が 2 個以上含まれていることも事前に確認しておくと効率的です).

愚直解では文字列  t の候補が  n(n+1)/2 個でしたが,配列  pos を持ち出したことで高々  4(n-1) 個となりオーダーが落ちて全体で  O((k+n)kn) に改善されています.これでもギリギリに見えますが,要所で枝刈りが効くので割と余裕があります.

所感

丁寧な考察と実装が必要で,見た目以上に難しい問題でした.
個人的には問題の文字定義が非直感的で実装がやりづらかったです.

解答例

https://codeforces.com/contest/903/submission/112423089

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
 
    ll K, N; cin >> K >> N;
    VS S(K); REP(i,K) cin >> S[i];
 
    // check
    VLL cnt(26,0);
    REP(p,N) cnt[S[0][p] - 'a']++;
    FOR(i,1,K) {
        VLL tmp(26,0);
        REP(p,N) tmp[S[i][p] - 'a']++;
        REP(c,26) if (cnt[c] != tmp[c]) { COUT(-1); return 0; }
    }
 
    bool all_char_diff = true;
    REP(c,26) if (cnt[c] >= 2) all_char_diff = false;
 
    // search s_x != s_y
    ll x = -1, y = -1;
    [&]() -> void {
        REP(i,K-1) FOR(j,i+1,K) {
            if (S[i] != S[j]) { x = i; y = j; return; }
        }
    }();
    if (x == -1) { swap(S[0][0], S[0][1]); COUT(S[0]); return 0; }
 
    VLL pos;
    REP(p,N) if (S[x][p] != S[y][p]) pos.push_back(p);
    if (SZ(pos) > 4) { COUT(-1); return 0; }
 
    string& t = S[x];
    for (ll diffpos : pos) {
        REP(p1,N) if (p1 != diffpos) {
            bool ok = true;
            swap(t[p1], t[diffpos]);
            REP(i,K) if (i != x) {
                ll diff = 0;
                REP(p2,N) if (S[i][p2] != t[p2]) diff++;
                if (diff != 0 && diff != 2) { ok = false; break; }
                if (diff == 0 && all_char_diff) { ok = false; break; }
            }
            if (ok) { COUT(t); return 0; }
            swap(t[p1], t[diffpos]);
        }
    }
    COUT(-1);
 
    return 0;
}

競プロのメンタルについて

 本記事の目的は「現状を正しく認識して必要以上に悩み消耗することを減らす」ことを目指しながら「競プロのメンタルに関する物事を様々な角度から論じる」ことです.できるだけ多くの項目を取り上げて気ままに論じたので,内容が重複している箇所があります.また,見方によっては一貫性に欠ける箇所があるかもしれません.

 競プロのメンタルと書きましたが,技術的なこと以外を雑多にまとめた自己啓発系の記事という方が正しいかもしれません.自己啓発にも色々ありますが,本記事では「黙って量をやれ」ではなく「現実的に考えよう」という立場を主に取っています *1.なるべく一般論的に書きたかったですが,例示などどうしても主観的にならざるを得ないところがある点はご容赦ください.自信を持ってブレークダウンできた項目もあれば,内容が浅くなってしまった項目もあります.

 本記事は下記の読者をメインターゲットとして書いています.

  • AtCoder 灰色〜緑色 (0 〜 1199)
  • レート上昇を目指している *2
  • 社会人
  • 20歳後半〜

 ここで,簡単に自己紹介やバックグラウンドを書きたいと思います.

  • 私は院卒で社会人4年目の28歳です.昨年3月から AtCoder を始めて,最近ついに青色に手が届きました(アカウント).
  • メンタルに関する (?) バックグラウンドとして,私は中学から大学まで個人競技の某球技をやっていました *3.大学はサークルではなく体育会の部活動でした.このスポーツを通して培われたメンタルや自己分析が本記事にも大いに影響しています.
  • これだけだと説得力にやや欠けると思うので,マイナーですがある実績の紹介をします.私は「どうぶつしょうぎウォーズ」というオンラインゲームの月次大会で優勝したことがあります *4.大会の参加人数は約15,000人でした.このときは「絶対に優勝するんだ」という強い気持ち,勝者のメンタルを少し得られたと思っています.

 本記事は項目ごとにおおよそ独立になっているので興味のあるものからお読みいただけますが,基本的には上から順に読むことをオススメします.

メンタルとは

 メンタルという言葉は「精神面」などの意味で知られる言葉ですが,本記事ではメンタルという言葉を以下のような意味で使用しています(何らかの競技経験がある人にはピンとくるでしょう).

  • 競技中の精神面.特に感情コントロール.メンタルが強いとは,どんなことにも動揺せず最後まで気持ちが折れないこと.具体的には,コンテスト中は常に冷静であり最後まで粘って実力を出し切れること.集中力と大いに関係する.技術としてのメンタルとも言える.
  • 競技外の精神面.考え方や心構え.モチベーション,プライド,ポジティブ,growth mindset *5 など.

 競技の文脈においては一般に前者の意味で使うという認識ですが,本記事ではあまり区別せずに使用しています.どちらの意味で使用しているかは文脈で分かると思うので,ご承知おきください.

 また,メンタルというのは非常に複雑であって,一次元的には説明できないものだと思っています.例えば,後述する「他人を気にせず昨日の自分に勝つ」「他人を意識して競争心を持つ」これらは一見矛盾しているようですが,どちらも重要なメンタルだと思っていて,いわゆる二律背反ではないかと思います.

原点と目的

 突然ですが,あなたが競プロを始めたきっかけは何でしょうか? なぜ続けられるのでしょうか? そして,何のために競プロを頑張っているのでしょうか? 競プロに限ったことではないですが,継続して何かに挑戦し続けると初心を忘れることはよくあります.時に苦しくなり「私は何のためにやっているんだ」と思ってしまうこともあるでしょう.競プロの問題を解く楽しさを知ったときの純粋な気持ちを思い出すと,メンタルが回復することがあります.自己成長が実感できて楽しいから続けられているという人も多いでしょう.

 また,目的がハッキリしていれば,一時的に心が弱くなったとしても何だかんだ続けられるものだと個人的には思っています.それでも苦しいとき,無理に続けると精神に支障をきたしたり身体に影響が出てきたりするかもしれません.競プロは義務ではありませんから,競プロを辞めるという選択肢を常に持っておくことで自分自身に逃げ道を作ってあげることも必要なことではないでしょうか.競プロよりも自分自身の人生の幸福度を高めることの方が遥かに優先度が高いはずです.一方で,人生において何かを犠牲にして競プロに取り組む人は強いですが,それは本当に覚悟のある人だけがやりましょう.

年齢と体力

 競プロは制限時間内にアルゴリズム・数学系の問題をたくさん早く解く競技であるため,頭の回転・集中力・発想力など「脳の馬力」のようなものが問われる側面があります.これは明らかに若い人たちが有利です.一方,知識・経験などは年長者に年の功があるでしょう.

 普段の精進でも同様です.若くない人にはその日に使えるエネルギーの総量みたいなものがあると思いますが,若い人はエネルギーに満ち溢れていて上限という概念がほとんどありません.私のようにそれほど若くない人は,エネルギーの総量を意識して,それを何にどれだけ使うか・使ったかを意識することが大事だと思います.
 若い人のエネルギーに勝てないのは自明ですが,近づけることはできます.それには睡眠と健康が重要です.適切な食事と睡眠によってその日のエネルギーの総量は増えてパフォーマンスは向上します.またメンタルの安定にも繋がります.

 エネルギーというのは全般的な表現でしたが,体力については別途気を配る必要があると思います.競プロに限った話ではないですが,歳を取ると疲れが取りにくくなったり集中力が続かなくなったりします.これらは体力向上やケアによっていくらか改善できると思います.適度に運動したりストレッチしたりすることが競プロをするための基礎体力に繋がるでしょう(ここは睡眠効率にも繋がってくるので意外に侮れないです).

社会人と時間

 20歳後半以降は社会人の人がほとんどだと思います.社会人はまとまった時間を仕事に拘束され,残業することもあります.休日を潰されることもあるでしょう.中には家庭を持ち自由な時間が一層取りにくい人もいると思います.一方,学生はどうでしょう *6.中学生・高校生は部活動や受験があるのでむしろ社会人より忙しいかもしれませんが,大学生は比較的時間に余裕があるのではないでしょうか *7

このように,人によって精進に使える時間は全く異なります.限られた時間の中で上手くやりくりできているなら他の人の精進量を見て落ち込む必要はないと思いますが,多くの場合は改善点もあるはずなので自己分析するのはよいと思います.

才能と限界

 残酷ではありますが,才能によって人それぞれに限界があり,成長速度も異なると思います.それは事実として受け止めて認めてしまった方がよいです.例えば「私は半年やって緑色なのに,あの人はすぐ水色になっている.私には才能がないんだ」と言って落ち込んでいる人がいたとします *8.これは正しい認識をするようになれば落ち込み度は低くなると思います.たった一人と比較して自分に才能がないと言うこと自体にほとんど意味はないと思うのですが,その人と比べて相対的に才能がない可能性は残念ながら高いでしょう *9.それだけのことです.極端なことを言えば,自分より背が伸びるのが早い人を見て「私には身長の才能がないんだ」と思うようなものです.

 もしアスリートのように人生をかけて他人を追い抜き頂点を目指すようなメンタリティで競プロに取り組む人がいるとすれば,そこはプライドを持って自分の才能を信じ突き進むべきだと思います.(上記の私も含めて)そうでない人は変にプライドを持たず楽になって,他人と比べることよりも「昨日の自分に勝つ」ことに重点を置くのが良いのではないかと思います.

 ここで,自分がこの話題で最も影響を受けた山高篤行先生の言葉を紹介します *10.誰にでも限界はあると認めた上で,自身の現状の限界に向き合うことの大切さを説得力を持って語られた言葉です.

「限界?誰だってありますよ。絶対あると思う。でも、だんだんと準備していくうちに、その限界が低くなっていくんだよね。そうやって近づいていくとその限界が限界じゃなくなる。限界は超えていくものだと思いますよ」
(引用元:https://www.nhk.or.jp/professional/2016/0201/index.html

才能と精進量

 強い人が異常精進をしている姿を見かけて「自分は精進が足らない」「才能以前に精進で負けてはダメだ」などと考えてしまう人はいると思いますが,このように自分に100%問題があると考えるのは半分くらい間違った認識だと思います.なぜなら,強い人には才能があり理解力・体力があるので短期間でたくさんの問題を解くことができますが,そうでない人が同じペースで精進することはできず公平ではないからです.つまり,精進量は時間だけでなく才能にも依存します

 精進に使う時間を増やしたりコンディションを整えたりすることで差を縮めることはできますが,才能ある人が努力も本気でしたら,基本的に勝てなくなるのは仕方のないことなので割り切りましょう.それを踏まえた上で,自分の精進に見直す点があったのであれば,それは自分に非があるということで改善するのは良いことだと思います.「半分くらい間違った認識」という表現をしたのはこのためです.どこまで自分に原因があり,どこからがどうしようもないことなのかを考えることで,必要以上に悩まなくなるのではないかと思います.

レートとの付き合い方

 AtCoder のレートが相対評価であることを正しく認識することが重要だと思います.イロレーティングをベースとした AtCoder のレーティングは,誰かのレートが増えればその分だけ他の誰かのレートが減少するようになっています(要出典).ですので,自分のレートが上がり続けるというのは割と都合の良い話であって,下がることはよくあるということを認識しておく方が良いと思います *11

 相対評価であることによって「実力は上がっているのにレートは下がる」という現象が理論上あり得ることになります.これは他人の方が成長速度が早いために自身の相対的な位置が後退してしまうことがあり得るからです.今の界隈には若くて才能のある人がどんどん参入してきている印象があり,特に茶色や緑色のレベルは以前と比べてかなり上がっていると思います.気休めにしかならないかもしれませんが,「レートが上がらない=成長できていない」とは限らないので必要以上に落ち込まないようにしましょう.レートではなく過去問の AC 数を成長の評価指標とする話はよく見かけます.

 AtCoder のレートは失敗に優しいと言われますが,これには数学的な裏付けがあります.高パフォーマンスを重み付けする関数がレート計算式に組み込まれているからです(非公式解説公式情報).このことを認識していればそれほど怖がらずに参加できるのではないでしょうか.また,AtCoder Rating Simulator を利用して事前にパフォーマンスとレート変動のシミュレーションをすることで心構えができるのでオススメです.

メンタルと精進のバランス

 ある人は言いました「レートを上げる秘訣は競プロを辞めないことです」*12 *13.では,どうすれば辞めずに続けられるのでしょうか? その答えは「メンタルを安定させる」ことだと思います.

 メンタルというのは「心が弱いもう一人の自分」くらいに考えるといいかもしれません.彼/彼女が弱っているときにはいたわってあげましょう.レートが下がってしまったり精進が思うようにいかなかったりしたときなどに,さらに自分自身を追い込んでまた落ち込む…という負の連鎖に陥ってしまうと自暴自棄になり競プロを辞めることになりかねません.
 私の場合,コンテスト中に解けなかった問題の復習は翌日以降へ後回しにしたり,いくら考えても解けないときにふて寝したり,解説を読んで理解できなかったときにその問題を放棄したりすることがあります.これらは精進の効率を考えると改善すべきことですが,メンタルの安定も考慮に入れるとある程度は仕方のないこと,むしろ必要なこととさえ考えています.自分を必要以上に追い込まず,楽しく精進できるラインを保っていけるように,理想 (≒精進) と現実 (≒メンタル) に上手く折り合いを付けていくことが大切だと思います.

 また,精進には「低diff埋め」「高diff埋め」があります.それぞれパフォーマンスの下限/上限の向上に繋がるということは各所で言われていて信憑性の高い話だと思います.しかし,機械的にどちらか選択できるというような話でもないと思っています.後者は難しい問題への挑戦であるため,1問こなすだけで相当のエネルギーが必要になるからです.エネルギーやモチベーションに満ち溢れている人は後者にどんどん挑戦していけると思いますが,そうでない人にとっては辛い作業だと思います.
 私の場合,メンタルが充実していてコンディションも整っているときに高diff埋めをやり,それ以外は基本的に低diff埋めをやるようにしています *14.私にとってこの精進方法はメンタルに優しくて続けやすいです.私にも「高diff埋めを毎日3問やるぞ」と決めてしばらく続けていた時期があるのですが,途中で挫折してしまいました.定量的な目標設定は非常に有効だと思いますが,メンタルを安定させ続けることは簡単なことではないため,計画を立てるにしてもそれを考慮に入れるのがよいと思います(受験勉強で計画を立てる時に頓挫しないよう予備日を組み込むことと似ていると思います).

 レートを上げる秘訣としての「競プロを辞めない」を最初に紹介しましたが,もう一つ上の段階があると思います.それは「精進を辞めない」です.コンテストに参加するだけではレートはほとんど上がらないでしょう.なぜなら,ほとんどの人は精進もしており,かつレートは相対評価だからです.競プロを辞めなかったとしても,無理な精進をして耐え切れず一時離脱ということを繰り返していては精進が中途半端になってしまいます.メンタルが壊れないように気を遣いながら無理なく精進をしていくのがベターだと思います.

コンテスト中のメンタル

 私は ABC が主戦場の人と ARC/AGC が主戦場の人とではコンテスト中のメンタル要素が少し違うのではないかと思っています *15.よって,ここでは私が分かる ABC についてのみ書きます(強い人に ARC/AGC でのメンタルの話を聞いてみたいです).

 ABC 中のメンタル要素として,下記があると思います.

  • 緊張と失敗する怖さ.これは特にレートが100〜200を越えたあたりから顕著に現れてくると思います.最初はレートは基本的に上がるだけなので失うものは何もなく割と気楽に参加できると思うのですが,レートが積み上がっていくにつれてレートが下がる確率も当然高くなっていきます.2完,3完,4完と,レートを上げるための条件は自身のレート上昇に伴ってますます厳しくなっていき,「成功したい」という気持ちと同時に「失敗したくない」という気持ちも生じて,それが緊張にも繋がってくると思います.私も毎回のように ABC で緊張しているのですが,「成功/失敗よりも実力を出し切ることが大事」「AtCoder は失敗に優しい」「ABC は毎週のようにあるから失敗してもすぐ取り返せる」などと自分に言い聞かせて緊張を和らげるようにしています.他に良い対処法があれば是非教えてください.

  • 諦めない気持ち.コンテスト終了まで諦めずに最後まで粘るというのは非常に重要です.大抵は徒労に終わってしまいますが,ギリギリ間に合って AC できることはたまにあります.これはマグレではなく実力による結果です *16.期待値をイメージすると分かると思いますが,最後までしっかり粘るようにするだけでレートは少し上がると思います.また,これは訓練によって鍛えることができると思っていて,例えばあさかつ・くじかつなどで最後まで粘る癖をつけたり普段の精進でタイマーを使ったりすることで自然と意識付けされていき,ひいては集中力も向上すると思います.

  • 外的要因に対する平常心.いくら事前準備したとしても,コンテスト中に想定外の事は発生します.例えば,急に家族に話しかけられたり,外で大きな音がしたり,コンテスト前のルーティーンを一部忘れていることに気が付いたときなど.このとき誰しも動揺すると思いますが,その動揺を最小限に抑えて心を乱すことなく適切に対処してコンテストに戻ることが理想的です.起こってしまったことは仕方のないことなので,諸々の対応はコンテスト後にやるとして,その場はサッと凌げるとよいです.言うは易く行うは難しだとは思いますが,イメージトレーニングでいくらか改善できると思います *17

ここで,自分が好きな漫画のセリフを紹介します.『ヒカルの碁』より,楊海 (ヤンハイ) さんが伊角さんに言ったセリフです.

「いら立ち あせり 不安 力み 緊張 プレッシャー…… つきまとう感情に振り回されるなっ キミにとって1番大切なことだ 石だけを見ろっ これは自覚と訓練でできるっ 元々の性格なんて関係ない 習得できる技術さこんなもん」
「習得できる―――技術!? そんなふうに考えたことはなかった 感情のコントロールが?」
(『ヒカルの碁』より引用)

弱さと向き合うメンタル

 何かを上達させるために絶対に避けられないこととして「苦手分野を克服する」「自分の行いを反省する」があります.自分自身の悪いところと向き合うというのはかなりのエネルギーが必要な作業であり,人によっては苦痛を伴うと思います.
 これは私の最大の課題でもあるので大したことは言えませんが,実践していて効果があったことを一つ書きます.それは「コンテストで解けなかった問題を1週間以内に復習する」です.本当はコンテスト終了後や翌日に復習するのが最も学習効果が高いと思うのですが,私の場合は負の感情が湧き上がってしまい問題と素直に向き合えないという難儀な性格をしています *18.そこで,やや甘い期限設定にすることで妥協をして,気持ちが落ち着いた頃に復習するようにしています.これは精進の効率よりもメンタルの安定を優先しているということです.他にもっと良い対処法をお持ちの方は是非教えてほしいです.

 別の話として,レートが停滞したり下がったりした時に「私はなんて弱いんだ」と自身の実力に対して悲観的になることがあると思います.AtCoder のレーティング信頼性は高い方だと思いますが,それでも問題との相性や当日のコンディションなど様々な要因によって下振れのパフォーマンスになることは十分にあり得ます.問題はそれが一時的でない場合ですが,大抵は原因がはっきりしている現象だと思うので, それを特定した上で改善していけばよいです(前述した苦手克服・反省パートへ進む). 例えば,私がレート1400あたりで停滞したのは DP と数学系の問題が続いたときに全く対応できなかったからです.レート1150あたりで停滞したのは ABC-E が全く解けなくて即ちここにレート上の壁があったからです.
 また,レートは相対評価であるため,自分以外の参加者の成長が相対的に早ければレートはジワジワ下がってしまうと思います.このとき「昨日の自分に勝つ」ができているならあまり気に病む必要はないのではと思いますが,レートを上げたいのであれば他の参加者たちの精進に追いつき追い越さなければいけません.

メンタルを強くする

 本記事はメンタルに関して保守的な記述が多いですが,ここではメンタル自体を強くする方法について書いてみたいと思います.

 最も重要だと思うのは,睡眠と健康です.睡眠不足に陥っているとパフォーマンスが低下するだけでなく,些細なことで心を乱すことが増えます(典型的にはキレやすくなる).健康状態が悪かったり何かの病気を患っていたりすると常に不安がつきまとい,痛みが伴うと実害となります *19.一心同体という言葉があるように,身体が弱っていると心も弱ってきます.身体のコンディションを整えることで,メンタルもまた同時に整います.逆もまた然りです.

 競技中のメンタルについて,技術的な要素でもあるため訓練や試行錯誤によって改善できると思います.例えば,諦めない気持ちはバチャによる訓練によって改善できると思います.コンテスト中に小休憩を入れて気持ちをリフレッシュしてみるのもいいでしょう *20

 競技外のメンタルについて,特にモチベーションで確実に1つ言えることがあります.それは「習慣の力によるメンタルの補強」です.例えば,私はあさかつに参加するために一念発起して生活習慣を改め,早寝早起きをするようにしました.最初は苦痛でしたが2週間くらいすると慣れていき,1ヶ月も経つ頃にはすっかり習慣になって当たり前になっていました.「7:25 に起きる」から「あさかつに参加する」までが習慣化したということです.そこでは意志の力 *21 はほとんど必要ありません.皆さんが ABC にほぼ毎回参加するのも,ある意味で習慣化された生活の一部といえるかもしれません.

モチベーション

 これはメンタルという言葉でひと括りにする必要のないよく知られた概念でしょう.モチベーションの維持は精進をする上で絶対に欠かせないポイントです.本記事では,モチベーション維持について直接的に扱うことはあえてしません.先人たちの色変記事に多種多様のヒントがありますので,そちらを参考にされるのがよいでしょう(本記事にも断片的には含まれています).

競争心

 競技プログラミングは何も誰かと競い合わなくとも一人で過去問を解いて楽しむことはできます.しかし,レートを上げたいなら話は別です.コンテストに出て他人と競い合って勝つ必要があります.勝ち負けが発生する競技でもっと勝てるようになりたいのであれば,競争心は絶対に必要です *22

 絶対に必要と書きましたが,常に競争心を出す必要はありません.適切な場面で競争心を引き出すことで大きなエネルギーを発揮できると私は考えており,それができない人は少し損をしているとすら思っています.

 私の競争心が役に立っている場面を2つ紹介します.

  • コンテスト中に(お気に入りのみ表示の)順位表を見ながら「この人には負けられない」「この人に勝ちたい」などと考えて集中力を高めることがあります.順位表は気にしすぎると気が散って逆効果なので塩梅は難しいところです.

  • 普段の精進で特定の人をライバル視して相手の精進量を見たり相手が埋めている問題を埋めたりすることがあります.特に呼び名は聞いたことありませんが,「ライバル駆動精進」なんてどうでしょうか.

Twitter

 競プロをやっている人は Twitter もやっている人が多いと思いますが,やりすぎないことをオススメします.これには大きく2つの理由があります.

  • 勉強や読書などの作業をするときに視界に携帯が入っている人の集中力が低くなったという割と自明な研究結果があります(要出典).精進している時は「視界に携帯を入れない」「PC 上で Twitter を見ない」ことで集中力が阻害されないようにするべきで,可能であれば通知を切りましょう *23
  • 強い人を観測しすぎてモチベーションを下げる原因になる可能性があります.逆にモチベーションが上がる人もいると思うので,ここは意見が分かれるところかもしれません.少なくとも,メンタルが弱っている時には見ないほうが良いでしょう.

 精進で分からなかったことを質問したりモチベーションを保ったりするなどのメリットもありますが,のめり込みすぎるとデメリットの方が大きくなると思うので,自分の時間を大切にしながら上手に利用するのがいいでしょう.

NoSub

※定常的に NoSub 戦略をしている人は本節を読まないことをオススメします※

 NoSub については色んな意見があると思います.私は NoSub を一度もしたことがなく,一時期かなり嫌っていましたが,今では自身の成長に集中するために考え方・メンタルを見直しました.

 まず NoSub には2種類あると思います.意図的か否かという違いですが,その境界は曖昧かもしれません.

  • NoSub 戦略(レートが上がりそうな時だけ提出する戦略)
  • NoSub (問題が1問も解けず意図せずそうなってしまった)

 前者はどのレート帯にも一定数存在するでしょう.後者は灰色〜茶色あたりで顕著だと思います.ここで,虐殺回となってしまった ARC111 に着目すると,灰色〜緑色の参加人数が激減していることがわかります(ここのデータを参考にしています).あまり良い言い方ではないですが,下の人たちがごっそり減った回は普段得られたはずのパフォーマンスが有意に減少するはずです.これは問題の難易度に原因があったこともさることながら,そもそも NoSub が存在するシステム上の問題だと言えます.一方で,NoSub 戦略をしている人は少なからずいると思いますが,先のインパクトを考えるとこちらはそれほど大きな影響はないと考えられます *24.よって,無害とまでは言いませんが NoSub 戦略する人たちの影響は気にせず自身の成長に集中した方が健全だと思います *25

 NoSub については,新 admin の maroonrk さんが撤廃することを検討されているようです(詳細).

さいごに

 記事作成を進めるにつれて「公開していい内容だろうか」「語る資格はあるのだろうか」という迷いが出てくるほど,本記事の内容はセンシティブだと思います.私の思いとしては「(1) 下の人の痛みが分かる」「(2) 説得力のある実力を持っている」という条件をバランスよく満たす人が本記事のような内容を語るのが理想的だと考えており,その条件を最も満たしているタイミング・節目がちょうど今だと思って書きました *26.(1) については,私は客観的に見ると大きな挫折をしていないためギリギリのライン,むしろアウトで語る資格は本来ないのかもしれません.(2) については青色に手が届いたので良いだろうと考えました.

 私の知る限り,競プロにおけるメンタル周りの話をここまで書き連ねた記事は見たことがありません *27.正直,新規参入者をもっと増やしたいであろう界隈にとって,ある意味タブーの話題だったかもしれません.しかし,界隈には「精進すればレートは上がる,もっと頑張ろう」というような空気感があり非常に良いなと思う一方で,努力の押し付けになっているような印象も少なからずあるので,こういう記事があっても良いんじゃないかと思いました.物凄い量の精進をしている強い人を見ると自己嫌悪に陥ってしまう人は多いと思いますが,他人は他人・自分は自分と認めることができれば,それほど気にならなくなるはずです.本記事が,自分のペースで等身大の目標に向かって楽しく精進するための励みになれば幸いです.

 そして,本記事は未完成です.網羅性はそれなりに確保できたものの内容があまり深堀できていなかったり私個人の考えが多かったりする項目もあります.競プロの技術以上にメンタルは意見が分かれるところかもしれません.あなたの手で完成させてください.追加・補完・修正などをして,あなたのメンタルに最も合う表現・解釈を見つけていき,あなた自身の「競プロのメンタル」を追究していってください.偉そうなことを言っていますが,私もまだまだ発展途上です.本記事をキッカケとして様々な意見が聞けることを期待しています.

謝辞

 本記事の大部分は先人たちの色変記事や一般論などを集約したものです.集約したことに新奇性があると信じていますが,私個人の力では到底成し得ないことでした.この場を借りて御礼申し上げます.また,本記事は公開前に知り合いの橙コーダーにレビューしていただきました.大変感謝しています.

*1:もちろん,前者のような情熱系メンタルも重要ですが本記事ではあまり取り扱いません

*2:本記事での重要な前提条件です

*3:大して強くないです

*4:後退解析によって後手必勝であることが判明した後の時代,いわゆる後手ゲーの時代でした.ですので,上級者は手順を覚えて後手必勝をほぼ実現しており,優勝争いの本質は「負けない相手といかにマッチングするか」「いかに先手番で誤魔化せるか」であり,盤外の戦略要素も多分に含んだゲームと化していました.あんなに可愛い絵柄なのに,大会では熾烈な争いが水面下で繰り広げられていました

*5:ある本の受け売りです

*6:批判する意図はないです

*7:もちろん,アルバイトや研究室で忙しい方もいると思います

*8:昔の私のことです

*9:細かいことを言えば,中級者になるのが早いタイプもいれば大器晩成タイプもいると思うので比較自体が難しいことだとは思います

*10:山高先生の「高」は正式にははしごだかです

*11:私が言うと説得力がないかもしれませんが…

*12:https://twitter.com/shiro537/status/1305162923472384001

*13:あくまで必要条件に過ぎないことに注意が必要です

*14:自分と同じ色か1色下くらい

*15:例えば,ARC/AGC は立ち回りが重要な戦略要素だと思うのですが,そこにはメンタルも密接に関係しているのではと思っています

*16:私が青色になれたのもこれのお陰です.ARC112 で終了3分前に D 問題を AC できました

*17:コンテスト開始直後に atcoder-cli で acc new を実行したときにログインが切れていたことがありました.初めてのことで完全に想定外だったので頭が真っ白になりましたが,直前まで「実力を出し切るぞ」と自分に言い聞かせていたのですぐに落ち着きを取り戻すことができ「1分あれば対処できるだろう」と考えて被害者意識を持たず冷静に対応できました.実はこのコンテストは終了3分前に D 問題を AC して青色になった ARC112 だったので,この序盤対応を間違えて心を乱していたら最後は間に合っていなかったかもしれません

*18:本質的に負けず嫌いでプライドが邪魔をしているんだと思います

*19:私は一時期虫歯の痛みに悩まされていたことがあり,さっさと歯医者へ行けばよかったと後悔しています

*20:私は ABC だと3完〜4完したタイミングでよく小休憩を入れています

*21:いわゆるウィルパワーというやつ

*22:メンタル Lv.99 の仏みたいな人がいたら競争心は不要かもしれません

*23:上手に切り替えられる人もいると思いますが,ダラダラやる癖はなくした方が健全な生活を送る上でも大切だと思います

*24:NoSub 戦略を正当化する気はありません

*25:ここに本音を書きます.私は NoSub 戦略をする人は別ゲーをやっていると認識しており,レートは -200 して眺めることにしています

*26:こういう内容を書いてみたいという思いは以前から持っていました

*27:あったら是非教えてください

AtCoder 青色になりました

AtCoder Regular Contest 112」で青コーダーになりました.

f:id:mts1104:20210214105937p:plain

本記事はいわゆる色変記事です.あまり自慢にならないようになるべく客観的に書いたつもりです. 半分くらいは自分のために書いていますが,本記事が誰かの役に立てば幸いです.

水色達成時の記事に自己紹介を載せているので興味ある方はどうぞ.

精進

精進量

精進量はかなり多い方だと思います.下埋め優先なのでAC数が多いです.精進グラフは既に橙色です.

f:id:mts1104:20210214112229p:plain f:id:mts1104:20210214112232p:plain f:id:mts1104:20210214112238p:plain f:id:mts1104:20210214112235p:plain f:id:mts1104:20210214143453p:plain f:id:mts1104:20210214112257p:plain f:id:mts1104:20210214112254p:plain f:id:mts1104:20210214112252p:plain:h200

実力向上を実感した精進

水色〜青色の期間も過去問をひたすら解く方法で精進していましたが,その中でも実力向上を実感した精進を紹介します.個人差があると思いますので参考までに.

  • 過去問精選 100 問

    • 特に DP と累積和の問題セットが豊富で実力が付いたと思います.あくまで自分の印象ですが AtCoder でこのレベルの DP の問題はやや少ないと思うので,AOJ & JOI など他所の問題を利用して特定分野を補強することは重要だと思います.しかし,これだけでは青色コーダーを目指すレベルとしては不十分で,後述する EDPC・JOI などで更に補う必要があると思います
    • 記事中に「100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います」とありますが,これは約1年前に書かれた記述なので注意が必要です.今の界隈レベルではこれで青色コーダーというのは明らかに実力不足だと思いますが,水色コーダー相当の実力が養われることは間違いないと思います *1 *2
    • ここに自作のチェックリストを置いているので,よろしければお使いください
  • 令和ABC

    • 青色コーダーになるために「ABC 5完」は明らかに必要条件なので,特に ABC-E の過去問を解いて精進することはごく自然な発想だと思います.それだけでなく,ABC は典型問題がバランスよく出題されているので学習効果・網羅性ともに高く,やらない理由がないです
    • 年末にはこんなバチャを立てて ABC-E を総復習しました.確実に効果があったと思います *3
  • EDPC

    • なるべく早く埋めた方が良いです *4
    • 基本的に初見殺しなので解説 AC して1問ずつしっかり勉強する,という取り組み方で良いと思います.自分は現時点で W まで埋めています
    • 推定難易度についてはこのツイートが参考になります
    • EDPC に加えて TDPC も存在します(こちらはやや難しめ)
  • あさかつ・くじかつ

    • 早解き・復習・実装効率化・ライブラリ整理などを目的として参加していました
    • あさかつは制限時間が60分に削られてるので良い訓練になりました
    • 問題を解くことと同様に早解きにも「(1) 考察パート速度」「(2) 実装パート速度」があると思っていて,さらに後者には「(2-1) 考察結果を実装に落とし込む速度」「(2-2) タイピング速度 (+ライブラリ充実度)」「(2-3) デバッグ速度」があると思っています *5.このような区別を付けて自身の課題を明確に認識した上で参加すると効果が高くなるのではないかと思います *6
  • AOJ Courses Library

    • ライブラリ作成の機会になるような典型問題がたくさん用意されています
    • DSLGPL・DPL がオススメです.DSL ではセグ木・遅延セグ木の問題セットがあります
  • JOI

    • ABC-E 相当の問題数確保・DP 練習などを目的として取り組んでいました
    • 具体的には難易度 5〜7 あたりを埋めていました.ここにも言及があります
    • ABC-F 相当の練習として 7〜9 も埋めていく予定です
  • 蟻本

    • 蟻本の良さは散々語り尽されていますが,1点挙げるとすれば網羅性の高さだと思っています
    • 教養としてじっくり読むような感じで,気が向いた時に読み返していました
    • 誤植が結構あるので注意が必要です.ある意味で読解力も鍛えられます *7
    • 4-3・4-5・4-7・GCJ の節以外は一通り読んだと思います *8
  • 螺旋本

    • 蟻本より簡単で誤植も少ないので気軽に読めます
    • 本書を読みながら幾何ライブラリを整備していますが,AtCoder で幾何が滅多に出ないことは周知の事実であり,残念ながら本番で役立ったことは現時点で一度もないです *9

メンタルについて

精進について長々と前述しましたが,結局メンタルが一番重要だと自分は思っています.別記事に書く予定です.
(2021/2/17 22:50 追記)
競プロのメンタルについて記事を書きました.

mts1104.hatenablog.com

小ネタ

  • 緑時代に Python ---> C++ に乗り換えてから,月1回くらいは int 型のオーバーフローで痛い目に遭うようになりました.嫌な気持ちになるので,自分のテンプレート・ライブラリのほとんどの int 型を一掃して long long 型に変更しました.これによって「制約を確認して int 型か long long 型か決める」という作業も必要なくなりました *10

今後について

「2021年内に黄色になる」を目標に引き続き精進します.まずは青パフォ以上を安定させたいです.

*1:もちろん,多くの問題を答えを見ずに解ける状態になったらの話です

*2:しれっと青diffと黄diffも入っているので全問制覇するのは大変です

*3:青diff以上の問題は解説ACが多かったので,何回か解き直さないと身に付かなかったです

*4:自分は ABC183-E・ABC184-D・ABC185-E・ABC187-E と立て続けに DP を落としたため,必要に迫られて EDPC を埋め始めました

*5:厳密には独立ではないです.例えば (2-1) が上手いと (2-2) の作業量自体が少なくなります

*6:自分は (2-2) > (2-3) >>> (1) > (2-1) という感じなので,あさかつ・くじかつ参加が (1) (2-1) の底上げに繋がったと実感しています

*7:自分の蟻本は赤字の書き込みで一杯です

*8:身に付いたとは言っていない

*9:ABC191-D は幾何というより誤差対処の問題だと思っています.許容誤差もないですし…

*10:AtCoder はメモリ制限が 1024 MB もありますし,int 型でないと TLE するケースにも遭遇したことはないです

AtCoder 水色になりました

AtCoder Beginner Contest 179」で水コーダーになりました.

f:id:mts1104:20200924002344p:plain

本記事はいわゆる色変記事ですが,「水色になるためにやったこと」などと偉そうに語るつもりはありません.自分は性格的に「再現性」「効率性」を重視して物事に取り組むところがあり,そういう観点で今まで取り組んできたことを一度しっかりまとめたいと思ったので,本記事の作成に至りました.

経験上,効率を最適化するとモチベーションが追いつかずに物事を辞めてしまう可能性が高くなるので,モチベーション維持にも配慮しながらコスパの良いやり方を日々模索しています.ですので,本記事の内容には堅実なところもあれば緩いところもあります.

半分くらいは自分のために書いていますが,本記事が誰かの役に立てば幸いです.

※本記事を短時間で読みたい方は「精進方法」だけを読むのがオススメです.

自己紹介

本記事を作成するにあたり,「再現性」という意味でも前提をしっかり示すべきだと思い,あまり本意ではなかったのですが競プロの実力に関係しそうな項目をできるだけ挙げました.

  • 社会人4年目(IT中小企業)
  • 名古屋大学大学院修士卒(物理)*1
  • プログラミング経験
    • 学生時代は研究で Fortran を最低限
    • 新人研修で2ヶ月間の基礎勉強
    • 社会人2年目から業務で Python *2
  • 数学*3
  • タイピング*6
    • 寿司打 10,000 円コース:14,600 円分お得
    • タイピング速度測定:打鍵数 287
  • ゲーム得意*7

競プロを始めたきっかけ

ここは備忘録も兼ねて詳細に書きます.

もともとは Kaggle をやろうと思い,情報収集も兼ねて Twitter を始めたのですが,残業が多くて肝心の Kaggle には本格的に手を出せずにいました(半分くらい言い訳です).そんなとき,一部の Kaggler が競プロ(≒AtCoder)をやっている姿を見かけて,競プロなら自分にも取り組みやすいのではないかと思い興味を持つようになりました.

2020年3月頃,新型コロナの影響で残業が減少傾向にあったため,時間的余裕が生まれました.Kaggle をやることをまず考えたのですが,興味が少し薄れていたこと,自分のスキルバランス的に競プロをやった方がいいと判断したこと *8 ,そして弊社の後輩(AtCoder 橙)*9 に影響されたこと,などによって競プロを始めることにしました.

高校生の時,楽しくて数学の問題ばかり解いていたことを思い出します.それくらい競プロは楽しいです.それゆえ「こんなに遊んでていいのか?」という謎の罪悪感をたまに感じます.

精進

精進量

精進量は多い方だと思います.今思えば,もう少し水〜青 diff に挑戦してもよかったなあと思います.精進グラフは既に青色です.

f:id:mts1104:20200925010249p:plain f:id:mts1104:20200925010300p:plain f:id:mts1104:20200925010310p:plain f:id:mts1104:20200925010359p:plain:h200

精進方法

基本的には過去問をひたすら解く方法で精進していました.

  • 基本方針

    • 過去問を解いて知らない知識は都度勉強
      • 参考書で勉強して過去問で演習,という教科書的なやり方はあまりやっていないです
    • 網羅性については量を確保することで対応
      • この記事を参考にしてバランスが悪くならないようには注意していました
    • 過去問の選び方は気分で決める
      • ここは割と自由にやっていました
      • 低 diff をたくさん解きたい日,高 diff をじっくり解きたい日,色々あると思います
      • 水 diff を1日1問解く,ということは少し意識していましたが,厳密には守れていません
    • 再現性を意識する
      • 過去問が解けず解説を見た場合「似た問題が出たとき解けるか?」を考えていました
      • 上手くいけば「典型的な考察過程」のようなものが抽象化できて自分のものにできます
      • 何も見えなかった場合,解説記事をたくさん読んで,何かヒントがないか探します
      • それでもピンとこなければ,とりあえず復習リストに入れて未来の自分に丸投げします
    • 効率性を意識する
      • 過去問が自力で解けた場合でも,解説は必ずチェックして無駄がなかったか確認します
      • もし無駄があったり想定解でなかったりした場合はなるべく解き直します
      • 他の人の実装をいくつか眺めて,盗めるものがあれば盗みます *10
  • AtCoder Problems

    • いつもお世話になっております
    • スポンサーになっていません,ごめんなさい
    • Virtual Contests
      • まとまった時間があるとき,気分転換したいときなどにオススメです
      • 自分の場合は早解きに自信があるので,コンテスト形式の練習は基本やらないです
    • Boot camp for Beginners
      • 全部埋めました
      • AGC-A などの diff 詐欺には注意が必要です *11
    • Recommendation (Moderate)
      • Boot camp を埋めてからはよく利用しています
  • AOJ

    • 螺旋本と合わせて勉強に使っています
    • いろいろなコースがあるので,気が向いたときにちまちま埋めています
  • 螺旋本

    • AtCoder を始めた当初に購入しました
    • AOJ と連携して学習でき,難しすぎることもないため,かなりオススメです
    • 通読はせずに興味のある章をつまみ食いしています(少し反省)
  • 蟻本

    • 緑コーダーになってから購入しましたが,全体的に難しいです
    • POJ が古いため,この記事などを参考に過去問を解いて練習します
    • 多くの競プロ er が蟻本で勉強しているので,遅れを取らないよう少しずつ読んでいます
  • ABC (AtCoder Beginner Contest)

    • 毎回参加することを徹底しており,ABC158 から1回も欠かさず参加し続けています
    • 解説放送
      • 自分はコンテスト後は相当疲れているので,解説放送を見ないで寝ます
      • 翌日以降に 1.25 倍速で見るのがオススメです
      • snuke さんが親切に色々教えてくれる絶好の機会なので,頑張って吸収します
      • C++ に移行してからは実装の時間にも注目するようになりました *12
  • 過去問精選 100 問

    • この記事のことです
    • ちゃんと100問解こうと思って最近取り組んでいます
    • ここに自作のチェックリストを置いているので,よろしければお使いください
  • 興味はあるが手を出していないこと

    • Codeforces, yukicoder
    • あさかつ・よるかつ
    • コンテスト前に「ぞい」とつぶやく

モチベーション維持

コンテストで大きく失敗したときだけだったと思いますが,競プロを辞めようと思ったことが過去に3回くらいありました.そのときに辞めずに続けられたのはなぜか,そもそも半年間ずっと続けられたのはなぜか,振り返ってみると自分の場合は下記が重要であると気が付きました.一応,重要度の高い順に書いています.

  • AtCoder 水色になりたいという強い気持ち
    • 結局これなのかなという気がします
    • 競プロを始めたときから,目標は茶色でも緑色でもなく「水色になること」でした
    • 「水色になれたらいいな」ではなく「水色になる」という気概で取り組んできました
  • Rated コンテストに毎回参加する
    • 一見矛盾しているようですが,今までの積み重ねが諦めない気持ちを支えてくれます
    • 「実力評価を受ける機会を定期的に設ける」ことは競プロに限らず勝負の世界では重要です
  • 仕事で残業しない
    • 割と重要だと思っているのですが,自分でコントロールすることは難しいです
  • 競争相手を見つける
    • 気になる人を見つけては AtCoder アカウントのお気に入り登録をしてます *13
    • 順位表を見て「この人に追いつきたい」「この人に負けたくない」と日々思ってます
  • 適切な睡眠を取る
    • 睡眠不足のとき,ちょっとしたことで心が揺れ動きやすいので,冷静さがやや失われます
    • 日々のパフォーマンスは精進の質ひいてはコンテスト結果に繋がるので気をつけたいものです

取り組み紹介

テンプレート・ライブラリ作成(Python

最初の頃は真っ白な状態から実装していましたが,入出力は何度も書いているうちに覚えてしまったので,割と初期の段階でテンプレートを作って効率化するようになりました.

Python のテンプレートは下記を使っていました.必要な入出力だけ残してあとはすべて消すという使い方です.

import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()
    N, M = map(int, input().split())
    A = list(map(int, input().split()))



    print(" ".join(map(str, ans)))
    print(ans)


if __name__ == "__main__":
    main()

ライブラリについても精進の過程で少しずつ整備していきました. 他人のライブラリのコピペはせず,すべて自分で書いたものを使いたいと思っていたので, コツコツと整備していきました.ここはゲームで言えばやりこみ要素だと思います.

github.com

自作のめぐる式二分探索 Numba 実装は汎用的でオススメなのでよろしければ是非お使いください.ちなみに Numba 実装にしている理由は,めぐる式二分探索は関数呼び出しの都合上,Python でそのまま書くとかなり遅くなってしまうからです.

AtCoder 向け User Script の利用

界隈には ac-predictor などよく知られた User Script がたくさんあります.コンテスト中の立ち回りや日々の精進などで非常に活躍します.特にお世話になっているものを挙げたいと思います.順番は適当です.

  • AtCoderPerformanceColorizer
  • AtCoder Submission User Colorizer
  • AtCoderStandingsAnalysis
  • AtCoder Submission Status
  • AutoSubmissionsSettings.js
  • AtCoderResultNotifier
  • ac-predictor
  • AtCoder TestCase Extension

Python + Numba という選択

言語アップデートによって Python では Numba が使えるようになり,JIT で割と気軽に高速化できるようになりました.これは大変ありがたかったです.しかし,Numba は発展途上でできることは限られており,ある程度の勉強も必要です.「PyPy に頼らずに Python 一本でいくんだ」という強い気持ちがある方以外は PyPy を覚えるか C++ などの高速な言語への移行をオススメします.

自分は結構 Python固執愛着があったので Numba で対応する方向で頑張っていました.この記事や Numba リファレンスを繰り返し読んで使い方を身に着けていきました *14 .AOT には手を出していないです. *15

Numba に関する注意点はここに少しまとめているので,よろしければ参考にしてください(ほとんど悪口しか書いていませんが…).

ここからは Numba の話になりますが,個人的に嫌気が差していたのは,隣接リストがスマートに利用できずダイクストラ法の Numba 実装が上手くまとまらなかったことです.AtCoder で使えるバージョンの Numba では TypedList が実験的に導入されている一方で,普段 Python で使っている listreflected list として扱われ,reflected list のネスト(隣接リストなど)を関数に渡すと怒られます(関数内部では構成できる仕様です).かといって,Typed List のネストは配列アクセスが遅いらしく[要出典*16] ,割と詰んでいます.試行錯誤の末に,関数の外側で辺の情報を numpy.ndarray 形式で準備して関数に渡し,内部で隣接リストを作成するという苦肉の策を思いついて「何やってんだろうな」と思いながらも FIX としました.一応ここに成果物がありますが,こんなことをするなら PyPy を使ったほうが楽そうです.

この話題は下記記事に詳細があるので,詳しく知りたい方はそちらを参考にしてください.

ikatakos.com

online-judge-tools + atcoder-cli 導入

効率に拘るところがありながら「専用ツールに頼らず実力でレートを上げたい」という中途半端な美学によって導入を渋っていました.しかし,目の前にチャンスがぶら下がれば入念に準備したくなるのが人間というもの.自分のレートが 1195 で水色目前だったとき,ダメ押しのつもりで *17 導入しました.

導入後のコンテストは計4回(ABC176〜ABC179),結果を見る限り有意な変化は確認できませんが,テスト自動化の恩恵が大きく体感的にはトータルで5分くらい速くなっている気がします(パフォーマンス換算すると10〜20くらい?).自作テストケース追加が簡単なところも嬉しいです.submit は自分でコピペ提出した方が圧倒的に早いので使っていないです.

明らかにアドバンテージがあるので,特に理由がなければ導入することをオススメします.速度向上だけでなく,体力温存,ヒューマンエラー防止 *18 などの恩恵もありますし,日々の精進の効率も若干上がります.

Python から C++

8月22日,ABC176 の直後に Python を捨てて C++ を始めました.約1ヶ月前のことです.

レート 1195 で水色目前というときに D 問題「Wizard in Maze」で TLE に苦しみ,自分の実力不足も当然ありましたが Python (PyPy) の不利さも明確に感じました.かなりショックだったのでコンテスト後に今後について色々考えました.使用言語というのは,いわば競プロの問題と闘うためのパートナーのようなものだと思っていて,ポケモンで言えば最初に選んだ一匹みたいなものだと思っています.葛藤がありましたが,「水色になる」という目標を最優先するため,Python を捨てて C++ でやっていくことを決心しました.言い訳できないようにしたかったという思いもあります.

しばらくはレートが下がる可能性が高そうだったので怖かったですが,一心不乱に C++ を身に着けていきました.環境構築から始まり,APG4b やライブラリ整備などをやりつつ簡単な過去問を大量に解いて一気に慣らしていきました.ここは我ながらよく頑張ったと思います.

テンプレート・ライブラリ作成(C++

C++ のテンプレートは現在下記を使っています.なるべく Python と同じような感覚で使えるように,という思いを持って日々メンテしていたら,いつのまにか30行近くになっていました.入力のところで,変数宣言と cin を一行で書くのがお気に入りの書き方です.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
#define FOR(i,l,r) for (int i = (l); i < (r); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0)
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((int)(c).size())
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<int,int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
static const double EPS = 1e-10;
static const double PI  = acos(-1.0);
static const ll MOD = 1000000007;
// static const ll MOD = 998244353;
static const int INF = 1 << 30;
// static const ll INF = 1LL << 62;
// --------------------------------------------------------


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    int N, M; cin >> N >> M;
    string S; cin >> S;
    VI A(N); REP(i,N) cin >> A[i];

    int ans = 0;
    cout << ans << '\n';

    return 0;
}

ライブラリは Python で作ったものを移植して作っていきました.あと最近に modint を理解しながら実装しました.今後も ACL は使用せず自分で実装したコードを使っていきたいと考えています.

github.com

今後について

「2021年3月までに青色になる」を目標に引き続き精進します.まずは水パフォ以上を安定させたいです.

*1:情報系の講義はほとんど受けていませんでした

*2:社会人1年目は無をしていました

*3:整数問題が苦手なのでトータルで少し有利,くらいの自己評価です

*4:本番は1ミスでした

*5:二次試験で大問丸々落としました…

*6:このレベルなら結構役に立ってると思います

*7:関係ないかもしれませんが…

*8:結果的にこの判断は正しく,競プロで培った高速化ノウハウが業務で役立ちました

*9:なぜ弊社に橙がいるのでしょう…笑

*10:Python では定数倍高速化のためによくやっていましたが,C++ ではほぼやっていないです

*11:激ムズの灰 diff とかあります

*12:最近は Python で解説されることもありますね

*13:現在,62アカウントをお気に入り登録しています.アクティブユーザは10〜20人くらいです.

*14:Numba は業務でも役に立ったので良かったです

*15:そこまでするなら PyPy で書いたほうがスマートかなと思っていました

*16:Numba GitHub Issues のどこかに書いてあったと思います

*17:残念ながら結果は奮いませんでしたが…

*18:過去にサンプルの出力を見間違えて WA を食らった経験があります…