はじめに
AtCoder はじめました。毎週土曜日 21時からの ABC (AtCoder Beginner Contest) に参加して、1か月半で緑になりましたので色変記事というものを。
すでに参加している方に役立つことはあまりないと思います。ABC257-E, ABC256-E 問題のネタバレがあります。
参加のきっかけ
プログラミング歴35年ほどです。会社で若い方から競技プログラミングが楽しいという話を聞いて、アルゴリズムは昔かじったことがあるからまあちょっと参加してみますか、くらいの軽い感じでお邪魔してみました。
参加してみると、これがさっぱり制限時間内にコードを書けない。こうすれば解けるはずというのに気づかなかったり、方針にバグを制限時間内に取り切れなかったりと。いやはや……。
- AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ
- レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 @e869120 さん
このあたりを見て、上位30%の緑色を目標にしようと思いました。
私の現在の ABC 目標時間
| 問題番号 | 時間目安 | 難易度・対応方針 |
|---|---|---|
| A | 5分 | 瞬殺したい。でもたまに文法が分からずタイムロスする。 |
| B | 15分 | 問題を理解して素直に書けば通るはず。下手に工夫しようとするとタイムロスする。 |
| C | 25分 | 基本的なアルゴリズムを使う。緑を狙うなら C までは安定して、D 問題以降の 1問に挑戦したい。 |
| D, E | 45分 | 運が良ければ時間内に解けるものが混ざっている。知らないアルゴリズムを使うこともある。 |
| F, G, H/EX | - | 見なかったことにする。 |
AtCoder Problems を見ると、だいたい ABC 3問までが茶、ABCD か ABCE の4問で緑、ABCDE の5問が取れれば次の水色のようです。
ライト層は毎週更新のパズルゲーとしても楽しめそう
「競技」プログラミングというとガチな感じがします。確かに ABC 5問以上解答を目指そうとすると、アルゴリズム・データ構造を覚えて、ぱっと当てはめられるように過去問を解く…… のようなことが必要そうです。
でも緑くらいなら「短いプログラムを何かの言語で書ける」「問題文を読んでその場で考える」ができれば、あまり多くのアルゴリズムを知らなくても大丈夫です。
たとえば最近の E 問題を 2つ紹介します:
問題例: ABC257 E - Addition and Multiplication 2
ABC256 E - Addition and Multiplication 2
問題文
高橋君は整数 $x$ を持っています。最初 $x=0$ です。
高橋君は以下の操作を好きな回数行えます。
整数 $i (1≤i≤9)$ を選ぶ。 $C_i$ 円払い、$x$ を $10x+i$ で置き換える。
高橋君の予算は N 円です。操作で支払うお金の総和が予算を超過しないように操作を行うとき、最終的に得られる x の最大値を求めてください。入力
$N$
$C_1$ $C_2$ $…$ $C_9$入力例 1
5
5 4 3 3 2 5 3 5 3出力例 1
95入力例 2
20
1 1 1 1 1 1 1 1 1出力例 2
99999999999999999999
$x$ を $10x+i$ で置き換えるというと、1回の操作で 9円が90円+αに、8円が80円+αになるということで、「操作回数が同じなら」最初に大きな数字を引くと絶対に値が逆転しません。一番大きな値を引けば良いです。DP とかいらない。
これは「操作回数が同じなら」であって、「操作回数が多い」のがもっと優先です。99円より111円が強い。
というわけで、最大何桁になるかを調べて、その制約下で大きな数字を順に引いていけば終了。コーディング自体は C 問題より易しいかもくらいです。
(最初問題を見た時には「操作回数が多い」に気づかず、そのまま提出して誤答ペナルティー5分をもらった人がここに。)
問題例: ABC256 E - Takahashi's Anguish
ABC256 E - Takahashi's Anguish
問題文
$1$ から $N$ の番号がついた $N$ 人の人がいます。
高橋君は $1$ から $N$ までの整数を並び替えた列 $P=(P_1, P_2, …, P_N)$ を 1 つ選んで、 人 $P_1$, 人 $P_2$ , …, 人 $P_N$ の順番に 1 人ずつキャンディを配ることにしました。
人 $i$ は人 $X_i$ のことが嫌いなので、高橋君が人 $i$ より先に人 $X_i$ にキャンディを配った場合、人 $i$ に不満度 $C_i$ がたまります。そうでない場合の人 $i$ の不満度は $0$ です。
高橋君が $P$ を自由に選べるとき、全員の不満度の和の最小値はいくつになりますか？入力
$N$
$X_1$ $X_2$ $…$ $X_N$
$C_1$ $C_2$ $…$ $C_N$入力例 1
3
2 3 2
1 10 100出力例 1
10入力例 2
8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45出力例 2
57
問題を文字で見ると難しそうです。でもグラフで図示してみると、
矢印の順番に進んでいれば不満がたまらない、でもループができていると誰か一人は不満が出るから、ループを見つけて一番小さな数字を足し算すれば良い、と。 図を描いて 57=27+30 の探し方が分かればだいたい解けたようなものです。
(この回は C 問題を解けたのが終了 10分前で、この E 問題を 10分で解くのはさすがに無理無理、という感じでした。)
問題例2つを見て
この2問、プログラミングというよりパズルっぽくないです? パズル問題を直接手で解くのではなく、パズルの解き方を PC に指示するメタなパズルゲーと言いますか。
楽しそうだと思ったらほかの問題も覗いてみたり、時間が合えば毎週末の ABC イベントに参加してみるのはいかがでしょうか、と。
今回挙げたようないかにもパズルのような問題のほかにも、アルゴリズムやデータ構造の定石を当てはめる問題、数学を使う問題などいろいろあります。解けるもの、解けそうなものは楽しいです。 (見なかったことにする問題もあります。)
最後に
目標の緑に届きました。次の水色を狙うかどうかは、もう少し続けてみてから考えます。早解き練習のために過去問をたくさん解きましょうとなると、だんだん名前の通り競技っぽくなります。
Rust で競プロに挑んでいます。ほかの方の提出結果を眺めると人気度が "C++ > Python >> その他大勢" のようで、これは実行速度と書きやすさから納得です。でも Rust も選択肢としてアリだと思います。もしかすると次のエントリに続きます。