milkcoffee Penalty Contest 001 参加記

※※※ネタバレ注意!※※※

milkcoffee さん主催の第一回ペナコンに参加しました.

mojacoder.app

せっかくなので参加記を書きます.
普段とは違って(?)砕けた文体で書いたのでご了承ください.
なお,6/9 (水) 21:30 頃から書き始めているので記憶は新しいです.

18:00 〜 18:30 頃

リモートワークを終えて夕飯を食べながら YouTube を適当に観た.ショウヘイオオタニがまたホームランを打ったらしい.

順位表も時々チェックしていた.しばらくしても 1 問目を数人しか提出していなくて,問題が難しいのか慎重になっているのかどちらかだろうな,などと考えていた.

準備

ローカルに作業フォルダを準備.ランダムテスト用のファイル群もコピー配置して準備万端(結局使わなかったけど…). このとき既に 3 完している人がいたが 3 問目は誰も解いていなかった気がする.

作戦

サンプルケースをローカルに作った上で,自作のテストケースをたくさん作って慎重にやる作戦にした. できれば愚直コードを書いてランダムテストをしたかったけど,愚直を書くタイプの問題ではなかったので, 実際は考察しながら丁寧に丁寧にテストケースを作りまくった. 問題毎に作ったテストケースの数は下記の通り(サンプルケースを除く).

  • 1 問目:12 個
  • 2 問目:18 個
  • 3 問目:14 個
  • 4 問目:18 個

また,提出は 4 問まとめてにしようとしていた. というのも,ペナ数が抑えられれば 30 時間以下の差は気にしなくていいと思ったので. 他の人の提出状況からペナ率の情報も分かるので,最後の最後まで確認してから tourist 出しするのが理に適っていると思った.

1 問目:Under M

 N^{N} の下  M 桁ですか,なるほどこれは難しい,普通の 100 点ではないですね.

Python が楽そうだなと思ったけど,多倍長整数が使えるなら C++ でもいいかなと思い, MojaCoder で boost が使えるかどうかをサンプル問題(A + B)でチェック(許される範囲ですよね…たぶん). 使えたので,多倍長整数を使うことにした.

愚直に  N^{N}多倍長整数で計算して,文字列型に変換して,下  M 桁を解析するだけ( N \leq 100 なのでこれで十分). 罠は何だろうと考えて,とりあえずサンプル 2 のように  M N^{N} の桁数を超えるケースがあった. 他は思い付かないのでテストケースを色々作ってみる. 0 が続くケースとかはちょっと怖いけど, 文字列型に変換したあとに長さが取得できるので解析も対処も割と簡単で他に罠は無さそう. 多倍長整数を使うことでかなり楽が出来た気がする(想定解は何だろう).

2 問目:RGB walking

右と下だけでなく上にも左にも移動できるので自由度が高くて難しそう,というのが第一印象.

まずは Bishop よろしく, \mathrm{min}(H, W) = 1 のケースを考えてみる. まっすぐ移動するしかないので,これは  \mathrm{mod} \, 3 で考えれば簡単. それ以外の法則はすぐ見えないので,とりあえず  (2, 2) 〜 (5, 5) を全て書いてみたら  (2, 2) 以外は全て Yes にできた.

直感的にも,盤面が広ければ調整が効くから Yes にするのは簡単そう. コーナーケースを除いてすべて Yes では? 証明が難しい… 色々お絵かきしていて「 (h, w) の道順を拡張して  (h, w+1) の道順が作れる」という傾向に気がつく. これを基に改めてお絵かきしてみたが,やはり拡張する方法で上手く Yes が作れそうだった.

ここで, (2, x) のケースの盤面が狭くて自信がなかったので  (2, 3) 〜 (2, 7) までお絵かきして問題ないことを確認. これでヨシ!

3 問目:Slice Cube

パ研合宿のあの問題を思い出した(解けてない). めちゃくちゃ苦手なタイプの問題で,最初は解ける自信がなかった.

とりあえずお絵かき.うん,全然わからない.
こういう時は調査でしょう.「立方体 切断面」でググって神サイトを見つける.

www.geogebra.org

みんなこれ使ってそうだな〜などと考えつつ,しばらく遊んでみる.割と楽しい. その結果,六角形は作れなさそうで,三角形・四角形・五角形が登場することがわかった.3 択問題ですね.

適当に  L = 10 で固定して少し自信なさげにテストケースを作る. 三角形の出現ケースに特徴があることに気付く.これは最初に場合分けできそう. 点を動かして確認すると,三角形の出現条件の中で  X = Y = Z = 0 \, \mathrm{or} \, L のときに四角形になることに気がつく.危ね〜.

残りは四角形か五角形.ここからが難しかった.他のサイトも色々読んでみたがよくわからない. しばらくして,「辺 DH を z 軸に重ねたときに,3 点を通る平面と z 軸の交点の z 座標で判別できそう」ということに気が付いた. 点を動かしてみるとこの交点の位置によって四角形と五角形が切り替わるように見えたので.

ということで平面の式の計算方法を調べる(すっかり忘れているので…). 色々あったが,今回は 3 点の座標が分かりやすいので  ax + by + c = z とおいて代入して係数を求めることにした. すんなりキャンセルして係数が求まる.コードを書いてみると WA が大量に出る.  a = \frac{Y - Z}{L} をそのまま計算して使っていたので切り捨てになっていた… うわー.

今知りたいのは  (x, y) = (0, 0) としたときの  z 座標の値なので, a, b を経由せず  c を直接求めるようにしたら,  c = X - Y + Z と綺麗に求まってビックリした.これは面白い. あとはこれが  0 \leq c \leq L なら四角形で外側なら五角形になるはず.

あれ,まだ WA が出る.あー, X = 0 とか  X = L のときに四角形になってやがる. このコーナーケースも潰して実装したところ,手元のテストケースを全てパス. 手応えがあったのでこれにて完了.丁寧に作ったテストケースに救われました.

4 問目:Sqrt Equality

お前,見たことあるぞ.

Sqrt Inequality よろしく,移項と二乗計算を駆使してルートを消した状態で等号判定すればいい. これが 4 問目だなんて,案外楽勝だな(フラグ).

順位表で意外にペナが出ているが,このときはピンと来ていなかった.

値が大きいので,再び多倍長整数を使う.丁寧に式変形をしていく. 途中で片側がルートのみになったので,反対側が負数になっていないかチェックを入れる. これは Sqrt Inequality と全く同じ.特に難しいところはない.

 \sqrt{513 \times 3^{2}} + \sqrt{513 \times 28^{2}} = \sqrt{513 \times 15^{2}} + \sqrt{513 \times 16^{2}} などの テストケースもしっかり作って,全てパスした.やはり,あっさり終わってしまった.

tourist 出し・最後の戦い

何せ初めてだったのでめちゃくちゃ緊張したが,tourist 出しを決行.この時点でノーペナ全完が二人いた.

後ろから出していったが,いきなり 4 問目が WA になるのが見えてつい笑ってしまった. そのあとも WA が続くのか? と思いきや,1 〜 3 問目は耐えてくれて AC.3 問目がノーペナは嬉しかった.

さて,4 問目と最後の戦い.ミスの原因が分からない.式変形の過程を眺める. 二乗計算は 2 回やっていて,2 回目は片側がルートのみになるので負数チェックをしているが, 1 回目は  2 (\sqrt{AB} - \sqrt{CD}) = (C + D) - (A + B) となっていて,気にせずそのまま二乗していた.

…あ〜そういうことかあ… 反例は作れなかったけど,1 回目の二乗計算でも符号確認が必要そうということに気付いた. 他に原因は思い付かなかったので,確信度 70 % くらいでこれが原因だと思い,丁寧にチェックを追加実装.

順位的には 1 ペナに抑えられると結構良さそうな結果になりそうだったので, ここでもかなり緊張したが,エイヤで投げたところ AC を獲得. 20:40 時点で 1 ペナ暫定 3 位につけた.中々上手くやったのではないだろうか.

体感 diff

体感 diff を書きます.3 問目がめちゃくちゃ難しかったです.4 問目はコーナーケースが難しくて diff が上がっている感覚です.
ところで,全て緑以下想定ってマジですか… 3 問目は人によっては考察しやすいのかな? 自分にとってはかなり辛かった.

  1. 茶 600〜800
  2. 緑 1000〜1200
  3. 青 1800〜2000
  4. 水 1200〜1400

まとめ

面白いコンテストをありがとうございました.早く解説とテストケースが見たいです. 個人的には 2 問目 と 4 問目 が好きで,3 問目はよくこの問題作れるなあ〜と感心しました.

一通り書き終わって誤字脱字等のチェックを済ませ,現在,22:50 頃なので 1 時間 20 分ほど使ってこの参加記は作成されました(もっと早く書き上げたかったけどこんなもんか…).

追記

終結果は 4 位 (1 WA) でした.終了 30 分前くらいに 3 人目のノーペナ全完者が出たようで,残念ながら 3 位から陥落しました.とはいえ,自分は 1 ペナを出していますし,調べたところノーペナ全完者は 3 人とも暖色コーダーだったので納得の結果ではあります.そもそもこんな上位になるとは思っていなかったので良い記念になって嬉しいです.

以上

Educational Codeforces Round 43 E. Well played!

公式解説を理解するのに時間がかかったので日本語の記事を書いておきます.
(現時点で日本語の記事は見つけられませんでした)

解説

便宜上,問題文にある二つの spell を「呪文 A」「呪文 B」と呼ぶことにします.

呪文 A の使い方

公式解説にある背理法の証明は個人的にはやや理解しづらかったですが, 要するに「呪文 A は一体に集中させても損しない」ということです. ここでは「どの一体を選ぶのが最適か」という話まではしていないです. あくまで,「呪文 A を使うなら一体に集中させても損しないので,その方が議論が簡単になる」ということだけ言っています.

よって, i 番目の creature に呪文 A を使うと決めたときには  hp^{'}_{i} = hp_{i} \times 2^{a} としてよいです.

呪文 B の使い方

呪文 B を  (n + 1) 回以上使う必要はないので  b = \mathrm{min}(b, n) としておきます.

どの creature に呪文 B を使うべきかを考える必要がありますが, これは「 dmg_{i} の代わりに  hp_{i} を使ったら(=呪文 B を使ったら)どのくらい得をするか」に着目して,  hp_{i} - dmg_{i} の降順ソートをすることでその利得の大きい順に creature を並べることができます(相対評価). 最大  b 体にしか呪文 B は使えないので,上位  b 体にだけ呪文 B を使うことを検討すれば十分です. ただし,この時点では呪文 A を考えていないことに注意してください. また,利得がマイナスの場合は呪文 B を使わない方が得なので呪文 B は使いません (使わずに余った分を後半の creature に回す必要もありません.なぜなら,利得の大きい順にソートしているので,利得マイナスが生じたら,その後もずっと利得マイナスが続くからです).

答えの求め方

方法は色々あると思いますが,ここでは公式解説ベースの説明をします.

まずは呪文 A を使わないで答えを仮計算しておきます. 利得マイナスのときは呪文 B を使うべきではありませんが, 実装上は  \mathrm{max}(hp_{i}, dmg_{i}) で評価してしまうと簡単です.

次に呪文 A の使用を考慮して答えを最適化します. 「呪文 A はどの一体に使うべきか?」を探索なしに特定するのは恐らく不可能であるため 「 i 番目の creature に呪文 A を使った場合は答えがいくつになるか?」を愚直に全探索します. このとき,先ほど行った降順ソートの順で調べていき,上位  b 体かそれ以降かで場合分けします.

  •  1 \leq i \leq b 番目
    •  i 番目の寄与  \mathrm{max}(hp_{i}, dmg_{i}) を一時的に引き算する
    • 代わりに  hp^{'}_{i} = hp_{i} \times 2^{a} を足し算して評価する
  •  b + 1 \leq i \leq n 番目
    •  i 番目には呪文 B が使えないので, b 番目に使っている呪文 B を取りやめて  i 番目に使う
      • 「呪文 B をどこから拝借するか?」は利得が最も小さい creature を選ぶのが最適
    •  b, i 番目に対して一時的な引き算と足し算をした上で評価する(前半の場合と同じ要領)

これで最適解が求まります.

所感

最初は  dp[n][a] の DP を考察していたんですが,「呪文 B を誰に使うか?」が残って上手くいきませんでした. こういう場合には greedy で考察できるようにしていきたいです.

解答例

https://codeforces.com/contest/976/submission/114846390

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll N, A, B; cin >> N >> A >> B;
    VLL h(N),d(N); REP(i,N) cin >> h[i] >> d[i];
 
    ll x = (1LL<<A);
    chmin(B, N);
 
    vector<tuple<ll,ll,ll>> X(N);
    REP(i,N) X[i] = tuple(h[i] - d[i], h[i], d[i]);
    RSORT(X);
 
    // b のみで仮計算
    ll tmp = 0;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp += max(hh, dd);
        } else {
            tmp += dd;
        }
    }
 
    // b が 0 なら
    if (B == 0) {
        COUT(tmp); return 0;
    }
 
    // a を考慮して最適化
    ll ans = tmp;
    REP(i,N) {
        auto [_, hh, dd] = X[i];
        if (i < B) {
            tmp = (tmp - max(hh, dd) + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + max(hh, dd) - hh*x);
        } else {
            // b 番目に使っていた b を取りやめて i 番目に使用 & a を使用
            auto [_, hh2, dd2] = X[B-1];
            tmp = (tmp - max(hh2, dd2) + dd2);
            tmp = (tmp - dd + hh*x);
            chmax(ans, tmp);
            tmp = (tmp + dd - hh*x);
            tmp = (tmp + max(hh2, dd2) - dd2);
        }
    }
    COUT(ans);
 
    return 0;
}

Educational Codeforces Round 40 F. Runner's Problem

実装でハマった箇所があったので念のため書いておきます…
(僕と同じミスをした人の助けになれば幸いです)

解説

結論から書きます.問題文にひっそり書いてあるこの文章.

Some cells may be blocked by multiple obstacles.

これに対応したコードを書かないと死にます.以上.

…もう少し書きます.

僕の場合,障害物による行列の変更にイベントソートを使ったのですが, 障害物の区間が終わるタイミングで「セルを解放する(禁止を解除する)」と実装すると, 区間が重なっていた場合に勝手な解放を許してしまうことになり答えが合わなくなります *1

よって,例えば「いま  i 行目には禁止区間がいくつ重なっているか?」を管理して,この値が  1 以上の時に行列要素を  0 にすればよいです.

所感

問題文に書いてある意味深な文章には注意しよう.

解答例

https://codeforces.com/contest/954/submission/114687102

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

    ll N, M; cin >> N >> M;

    // イベントソート
    map<ll,VP> mp;
    REP(_,N) {
        ll a, l, r; cin >> a >> l >> r;
        a--; l--; r--;
        mp[l  ].push_back(P(+1,a));  // 禁止区間の追加
        mp[r+1].push_back(P(-1,a));  // 禁止区間の削除
    }
    mp[M].push_back(P(0,0));

    VVM B = {{1, 0, 0},
             {0, 1, 0},
             {0, 0, 1}};

    VVM A = {{1, 1, 0},
             {1, 1, 1},
             {0, 1, 1}};

    ll pos = 0;
    VLL X(3,0);  // 禁止カウント (>0 のとき禁止)
    for (auto& [x, E] : mp) {
        ll n = x-1 - pos;
        B = mat_mul(mat_exp(A, n), B);
        pos = x-1;

        for (auto [q, y] : E) {
            if (q == -1) {
                X[y]--;
                if (X[0] == 0) A[0] = {1, 1, 0};
                if (X[1] == 0) A[1] = {1, 1, 1};
                if (X[2] == 0) A[2] = {0, 1, 1};
            } else if (q == 1) {
                X[y]++;
                if (X[0] > 0) A[0] = {0, 0, 0};
                if (X[1] > 0) A[1] = {0, 0, 0};
                if (X[2] > 0) A[2] = {0, 0, 0};
            }
        }
    }

    mint ans = B[1][1];
    COUT(ans);

    return 0;
}

*1:僕の場合は test 3 ケースで WA になりました

AtCoder Regular Contest 008 D - タコヤキオイシクナール

(2021/04/30 追記) 考え方としてはイベントソートが近いのかなと思います.

座標圧縮を使わずに解いたので一応書きます.

解説

ソースコードを見た方が恐らく話が早いです(最下部にあります)

写像の合成などは既存解法と同じなので省略します.

ACL の遅延セグ木を使います. ACL の遅延セグメント木を使った区間アフィン変換 (Range Affine) はこの問題がそのままです.

モノイドの定義を次のようにします(すべてのクエリを処理した後にこうなる,という定義です).

  • seg( i) :=  i 番目の変更後に出来上がったたこ焼きの美味しさ

素数 (M + 1) 個を確保します( \because サンプル  3).このように定義することで,「各タイミングのたこ焼きの美味しさを,遅延セグメント木の上で区間アフィン変換をしながら同時に計算する」ということをやります.区間操作の順序はボックスの順序を優先すべきことに注意が必要で,それを実現するために map を使います(座標圧縮と対応するポイントです).map を使うことで,変更クエリをボックスごとに集計しつつ,その集計結果はボックスの番号の昇順になります.

集計が終わったらボックスごとに集計結果をオープンします. このうち,変更タイミングが最も遅いクエリ  i_{last} はそのクエリ適用後から最後まで, つまり  [i_{last}, M+1)区間で変更が反映されるべきです. その次に遅いクエリ  i_{last2} [i_{last2}, i_{last})区間で変更が反映されるべきです. この要領で遅い方から順に区間アフィン変換を実行していけばよいです.

すべてのクエリを処理した後, (M + 1) 個のモノイドにはそれぞれ「 i 番目の変更後に出来上がったたこ焼きの美味しさ」が入っているので,一つひとつ取り出して最小値と最大値をそれぞれ計算すれば OK です.

遅延セグメント木の上で最大値/最小値の計算も行いたい場合,モノイドを工夫して設計しないといけないことに注意が必要です *1.min/max の二項演算をナイーブに実装するだけではダメです *2

所感

試験管とはいえこれが橙 diff の時代があったんですね(90 分コンテストの D 問題ということもかなり影響してはいそうです).今なら ABC-F で出て青 diff 上位くらいでしょうか.

座標圧縮を使わずに解きましたが,それはあえてそうしたのではなく残念ながら思い付けなかったからです.座標圧縮してボックスをそのままセグメント木に載せる解法の方が直感的で分かりやすいと思います.

解答例

https://atcoder.jp/contests/arc008/submissions/22155530

#include <atcoder/lazysegtree>
using namespace atcoder;
 
// 区間アフィン・1点取得
using S = double;
struct F { double a, b; };
S op([[maybe_unused]] S a, [[maybe_unused]] S b) { return 0; }
S e() { return 1; }
S mapping(F f, S x) { return f.a * x + f.b; }
F composition(F f, F g) { return F{f.a * g.a, f.a * g.b + f.b}; }
F id() { return F{1, 0}; }
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll N, M; cin >> N >> M;
    map<ll,vector<tuple<ll,double,double>>> mp;
    FOR(i,1,M+1) {
        ll p; double a, b; cin >> p >> a >> b;
        mp[p].push_back({i,a,b});
    }
 
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(M+1);
    for (auto& [_, T] : mp) {
        reverse(ALL(T));
        ll r = M+1;  // 右半開区間
        for (auto [l, a, b] : T) {
            seg.apply(l, r, F{a, b});
            r = l;
        }
    }
    double min_v = +INF;
    double max_v = -INF;
    REP(i,M+1) {
        double v = seg.get(i);
        chmin(min_v, v);
        chmax(max_v, v);
    }
    COUT(min_v);
    COUT(max_v);
 
    return 0;
}

*1:そもそも可能なんでしょうか…? 総和の場合は前述した問題の通り可能です

*2:供養します:https://atcoder.jp/contests/arc008/submissions/22151781

AtCoder Beginner Contest 172 F - Unfair Nim

公式解説の行間をほぼ埋めました

公式解説の行間埋め

1. 「 a + (a \oplus X) = S

まず XOR の性質を列挙しておきます.任意の非負整数  a, b, c について下記が成立します *1


\begin{aligned}
a \oplus 0 &= a \\
a \oplus a &= 0 \\
a \oplus (b \oplus c) &= (a \oplus b) \oplus c \\
\end{aligned}

早速これらを利用します. a \oplus b = X の両辺に  a \oplus を掛けると


\begin{aligned}
a \oplus (a \oplus b) &= a \oplus X \\
(a \oplus a) \oplus b &= a \oplus X \\
0 \oplus b &= a \oplus X \\
b &= a \oplus X \\
\end{aligned}

と式変形することができ, a + (a \oplus X) = S が成り立つことがわかります.

2. 「動的計画法により実質的に  a の値の全探索を行う」

すみません,よく分かりません…

3. 「 a + b = (a \oplus b) + 2 \times (a \, & \, b)

公式解説に書いてある通り「繰り上がりを無視した足し算」であることを考えて,具体的な整数を使って手を動かせば大体は分かると思いますが,ここでは補足的な解釈を書きます.

 + \oplus を同一視することを考えます.任意の非負整数  a, b を二進表記したときの  d 桁目を  a_{d}, b_{d} とおくと, (a_{d}, b_{d}) = (0, 0), (0, 1), (1, 0) の場合は  a + b = a \oplus b が成立しますが, (a_{d}, b_{d}) = (1, 1) の場合は成立しません.なぜなら, d 桁目は両者とも  0 となり一致しますが  + の場合のみ繰り上がりが発生して  (d + 1) 桁目が  1 増えるという違いがあるからです(逆に言えば, \oplus が「繰り上がりを無視した足し算」であると言えます).よって, + \oplus を同一視することはできません.

しかし, a + b = (a \oplus b) + x が成立するような調整項  x が存在しないか考えてみると,なんと  x = a \, & \, b とすれば成立します. (a_{d}, b_{d}) = (1, 1) であるような全ての  d について「繰り上がりの有無の違い」が発生しますが,裏を返せばそのような位置は  a \, & \, b によって過不足なく拾うことができます.これが理解できれば後は簡単で,繰り上がりが必要なので  2 倍すれば  a \oplus b で無視されていた部分がピッタリ補えるということです(二進表記だから  2 倍).

4. 「 D が非負整数でない場合」

 a + b = (a \oplus b) + 2 \times (a \, & \, b) が成立することから次のことが言えます.


a + b \geq a \oplus b

一か所でも繰り上がりが発生する桁があれば  a + b の方が大きくなり,そうでなければ等号が成立します.(公式解説の記号を使えば)これは  S \lt X のときに成立せず,「 D非負でない」と同値です.

なお, D = \frac{S - X}{2} であるため, S - X 2 で割り切れるか確認する必要もあります.好意的に解釈すると,公式解説ではこのことを含意して「 D非負整数でない」と書いているのだと思われます.

5. 「 D X で共通して立っているビットが一か所でもある場合」

つまり, D \, & \, X = 0 が成立する必要があるということですが,これは具体例を見た方が早いです.


\begin{aligned}
                     a &= 0101100 \\
                     b &= 0111010 \\
S = a + b         &= 1100110 \\
X = a \oplus b &= 0010110 \\
D = a \, & \, b &= 0101000 \\
\end{aligned}

これを観察すると, D X で共通して立っているビットが存在していないことが分かります.そして,これは任意の非負整数  a, b について成立します.正確に言うと「一方でビットが立っている場合,もう一方のビットは必ず立たない」となります.これは  (a_{d}, b_{d}) = (0, 0), (0, 1), (1, 0), (1, 1) 4 通りで場合分けして  a_{d} \oplus b_{d} a_{d} \, & \, b_{d} をそれぞれ計算すれば確認できます(一応,先の具体例にはこの  4 通りが全て含まれています). \oplus & はビットごとに独立に考えられるところがポイントです.

6. 「 X で立っているビットの集合を二分割して得られる整数  Y, Z

例えば下記のように二分割できます.


\begin{aligned}
X &= 0010110 \\
Y &= 0010010 \\
Z &= 0000100 \\
\end{aligned}

つまり, X で立っているビットの集合から二者でビットを一つずつ取り合うことで得られる二つの整数が  Y, Z ということです.「二分割」「一つずつ取り合う」というのを形式的に書くと  Y \, & \, Z = 0, Y \oplus Z = X となります(公式解説に書いてある通りです).

7-1. 「 a = D \oplus Y, b = D \oplus Z というペアは残りの条件を満たします」

「どうやったら  a = D \oplus Y を思いつくか?」という議論は後述します.

まず「残りの条件」が何を指しているかですが,文脈的に下記だと思われます(枠で囲まれた問題文の条件の一つ「 a \leq A_{1}」に言及があるため).


\begin{aligned}
a + b &= S \\
a \oplus b &= X \\
\end{aligned}

ここで, a = D \oplus Y を深堀しておきます. 「 D X で共通して立っているビットが一か所もない」ということはこれまでの議論で保証されており( D \, & \, X = 0),同じことが  Y, Z についても言えます(そのように選んでいるため).よって,実は下記が成り立っています.


\begin{aligned}
a = D \oplus Y &= D + Y \\
b = D \oplus Z &= D + Z \\
Y \oplus Z &= Y + Z \\
\end{aligned}

これを踏まえて,「残りの条件」が成り立っていることは下記のように確認できます(実戦的には具体的にビットを並べれば十分確かめられると思います).


\begin{aligned}
a + b &= (D \oplus Y) + (D \oplus Z) \\
         &= (D + Y) + (D + Z) \\
         &= (Y + Z) + 2 \times D \\
         &= (Y \oplus Z) + 2 \times \frac{S - X}{2} \\
         &= X + (S - X) \\
         &= S \\

a \oplus b &= (D \oplus Y) \oplus (D \oplus Z) \\
                 &= Y \oplus (D \oplus D) \oplus Z \\
                 &= Y \oplus 0 \oplus Z \\
                 &= Y \oplus Z \\
                 &= X \\
\end{aligned}

7-2. どうやったら  a = D \oplus Y を思いつくか?

今やりたいことは「 a + b = S, a \oplus b = X, a \leq A_{1} であるような非負整数ペア  (a, b) のうち, a が取り得る最大の値を求める」です(枠で囲まれた問題文).そのためには少なくとも  a + b = S, a \oplus b = X が満たされるように  (a, b) を上手く決めてやる必要があります. ここで, S S = X + 2 \times D と表現でき,かつ  D \, & \, X = 0 が成り立つことを思い出すと,「 X, D を利用してビットたちを  (a, b) に上手く割り振れないか?( a + b = S, a \oplus b = X を満たせないか?)」ということを考えることができます *2.分かりやすさのため,(先ほどと同じ)具体例を出しておきます.


\begin{aligned}
                     a &= 0101100 \, (※一例) \\
                     b &= 0111010 \, (※一例) \\
S = a + b         &= 1100110 \\
X = a \oplus b &= 0010110 \\
D = a \, & \, b &= 0101000 \\
\end{aligned}

まず  X = a \oplus b を考えると下記が要請されることが分かります.

  •  X_{d} = 1 であるような全ての  d (a_{d}, b_{d}) = (0, 1), (1, 0)
  •  X_{d} = 0 であるような全ての  d (a_{d}, b_{d}) = (0, 0), (1, 1)

意外と自由度がないということが分かりますが,この範囲内で  2 \times D の分のビットたちもカバーして  a + b = S を満たすように  (a, b) を決める必要があります. そしてそれは  (a, b) D を一つずつ配分することでピッタリ満たすことができます.なぜなら, D に相当するビットたちは  a + b では  2 \times D の寄与になる一方, a \oplus b では  D \oplus D = 0 により綺麗にキャンセルするからです( \because D \, & \, X = 0).

以上により,下記のような非負整数ペア  (a, b) a + b = S, a \oplus b = X を満たすことが分かります.そして,これ以外の  (a, b) では条件を満たせないことも同時に分かります( D を一つずつ配分しないと  a \oplus b のときに  X_{d} = 0 が満たせない  d が必ず生じてしまうからです).


\begin{aligned}
a = D + Y = D \oplus Y \\
b = D + Z = D \oplus Z \\
\end{aligned}

8. 「任意の桁は、それより下のすべての桁を合わせたものより重要」

9 節より後に登場する文章ですが,都合により先に取り扱います.

これは十進表記で考えれば,例えば「 1000 > 999〜001 」ということです.二進表記では下位から  d 桁目のビットに着目したとき,それより下位のビットの総和は  2^{d-1} より必ず小さくなる,ということになります.

9. 「まず  Y = 0 として(中略)という貪欲な戦略が最適」

 X で立っているビットを一つずつ降順に取り上げ」というのは,上位のビットから順に見ていくということです.気持ちとしては,ある十進表記の非負整数を二進表記に手計算で変換するとき,上位のビットから順に見て貪欲にビットを立てていくと思いますが,それと似ていると思います.厳密な証明は筆者のレベルを越えそうなので省略します.

所感

Nim とは一体何だったのか… と思うほど,言い換え後の問題文で必要となる考察ステップが多くて非常に難易度の高い問題でした.しかし,一つひとつ整理していけば,これらのほとんどは典型考察であることが分かります.公式解説のように最善手を指し続けるのは難しいので,実戦的には途中で DP や二分探索が入ることはありそうです(そういう解き方も見かけました).

余談ですが,はてなブログの仕様らしく tex でアンド記号が上手く使えなくてストレスが溜まりました(pre タグを使う方法は不格好なので辞めました).試行錯誤した結果,大文字を使うことでそれっぽい見た目になったのでこれで良しとします.「a \, & \, b」のように間隔調整も入れて書いてます.

解答例

https://atcoder.jp/contests/abc172/submissions/22078103

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

    ll N; cin >> N;
    VLL A(N); REP(i,N) cin >> A[i];

    ll S = A[0] + A[1];
    ll X = 0; FOR(i,2,N) X ^= A[i];
    ll D = (S - X) / 2;

    // validation
    if ((S - X) % 2 == 1) { COUT(-1); return 0; }
    if (D < 0) { COUT(-1); return 0; }
    if ((D & X) > 0) { COUT(-1); return 0; }
    if (D > A[0]) { COUT(-1); return 0; }

    ll a = D;
    ll L = bitlen(X);
    RREP(i,L) if (BIT(X,i)) {
        if ((a ^ (1LL<<i)) <= A[0]) a ^= (1LL<<i);
    }

    ll ans = A[0] - a;
    if (ans == A[0]) { COUT(-1); return 0; }  // A_1 個未満しか移せない
    COUT(ans);

    return 0;
}

謝辞

ある未定義動作を引き起こして困っていたところをすのーさんに助けていただきました.ありがとうございます.
https://twitter.com/mts1104_ml/status/1386347717220134913

*1:Unfair Nim を解くようなレベルの人たちがこれらを知らないということは滅多にないとは思います

*2:「こうできたらいいな」みたいな「気持ち」的な考察過程でしょうか…

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:あったら是非教えてください