競技プログラミングはプログラミングで様々な問題を解く競技です。競技プログラミングを知らない数学者が新たに競技プログラミングの勉強をする際に知っておくと便利だと思ったことをまとめてみました。
ただし競技プログラミングが実施される場は複数あり特に国内で有名なのはAtCoderですが、筆者($p$ 進大好きbot)は基本的にyukicoderで活動をしているためyukicoderに限った話かもしれないことにご留意ください。そもそも筆者は記事執筆時点で競技プログラミングの勉強を始めて1年程度しか経っていないため、理解が不正確な可能性もございます。
また具体例として問題を引用しますが、引用元の問題文が変更されることもございます。断りのない限りあくまでこの記事を執筆した時点(2023/10/02現在)での問題文を参照していることにご注意ください。
入力と出力
競技プログラミングは大体の問題は、「入力を受け取り、適切に出力する」関数を実装してそのソースコードを提出させる問題です。この時、
- 入力は実装した関数の引数として与えられるのではなく標準入力(キーボードやファイルから入力を受け取る機能)で与えられる。
- 出力は実装した関数の返り値として与えるのではなく標準出力(画面やファイルへ出力を書き出す機能)へ与える。
ということが暗に想定されていることにご注意ください。例えばmain関数の返り値に出力すべき値を返してしまうと実行時エラーが生じて不正解となる可能性が高いです。これはyukicoderに限らず多くの競技プログラミングサイトで共通の形式だそうです。
参考:
事前準備
競技プログラミングのコンテスト本番において、提出するソースコードはコンテスト開始後に書き始める必要はありません。もちろんコンテスト開始前にはどんな問題が出題されるかが分からないことが主であるため事前に完全な正解となるソースコードを準備することは現実的ではありませんが、多くの問題で共通して記述する部分を予め書いておくことは合理的な戦略となります。
ただし提出できるソースコードにはファイルサイズの制限があり、例えばyukicoderでは64KBが上限と定められています。使い道が何かしらありそうな関数の定義を予め書いてしておくことも大事ですが、書き過ぎるとファイルサイズ上限に容易に達してしまうことに注意しましょう。
また、提出するソースコードに書いておかなくても、提出しないファイル(以下ライブラリ)に様々な関数の定義を予めまとめておくことも1つの戦略です。提出するソースコードに直接書く場合と違って必要な分をいちいちコピー&ペーストするなりエディタの機能を使って移植するなりする必要はありますが、ライブラリに用意しておく分には提出するソースコードのファイルサイズ上限を気にする必要がないので好きなだけ準備することが可能です。
競技プログラミングで用いるアルゴリズムは迷路や数に対するものであっても多くが代数構造や重み付きグラフに抽象化することが可能であり、抽象化の理論的な難易度自体は数学者であればほとんど0に見積もれるくらいシンプルなアルゴリズムが大半です。抽象化しておけば複数の問題に使い回せるので、抽象化のコストが無視できる場合は1回使ったアルゴリズムは抽象化してライブラリに置いておくと良いかもしれません。
検索
数学の試験などでは試験中にインターネットで検索したり書籍を参考にしたりすることが認められないケースが多いですが、競技プログラミングではこれらはルールで認められています。問題を抽象化して検索すれば解法が引っかかることもよくありますし、後で説明するように競技プログラミングが既出の問題をそれなりに出題することからも検索の有効性が分かります。コンテスト中に解法の正当性の証明までは求められないので、検索をすることはいつでも選択肢に入れておきましょう。
一方で禁止されている行為もいくつかあるようです。yukicoderでの禁止事項はどこに書いてあるか分かりませんでしたが、恐らく断りのない限りAtCoderの禁止事項(p.18)と同じなのではないかと推測しています。詳しくはそちらをご確認ください。
解説
ありがたいことに少なくともyukicoderではほぼ全ての問題に日本語の解説が提供されており、しかも大半が非常に丁寧で分かりやすいものです。ごく偶に解説がついていなかったりほとんど何も書いていなかったりしてがっかりすることはありますが、非常に稀なケースです。
また有名なアルゴリズムであれば、やはり競技プログラマーによる非常に丁寧な解説が検索で引っかかることが多いです。解説の書き方は十人十色だとは思いますが、少なくとも数学者向きの解説もかなり多いという印象です。もちろんたまには自分に合わないと思う解説もありますが、そういう場合は他の解説を探すなどしてみましょう。なお個bot的な体験としては競技プログラマーの方々は本当に親切で初心者に優しい方が多く、直接お尋ねすれば色々と教えてくださる人も多かったので、解説が見つからない時はどなたかに助けを求めるのも良いと思います。もちろん、感謝の気持ちを忘れずに。
このように、競技プログラミングは数学者が勉強するための土壌が十分に整備されており、学習における辛さは少ない方だと思います。恐らく普段の勉強よりも気楽に新しいアルゴリズムを学んでいけると思います。大船に乗ったつもりで問題に挑戦し、解説を読み込んでいきましょう。
既出
実は競技プログラミングではほぼ既出の問題(過去に解法が説明されたことのある問題の一部を変更しただけのもの)がそれなりの頻度で出題されます。作問作業はwriterさん(問題を実際に作成する人)とtesterさん(作成された問題が適正なものかを確認する人)の共同作業であり、writerさんが意図せずほぼ既出の問題を作成してしまうこともあります。testerさんがそれに気づけば何かしらの修正が入るかもしれませんが、気づけないこともあると思います。また意図的にほぼ既出である問題を作成することもあり、その場合はオマージュ作品として(問題文には明記せずとも解説などで引用したりしすることで剽窃・盗用を避けた上で)出題することになります。
ただし、そもそも競技プログラミング人口の大半は数学者ではなく、一般の参加者にとっては数学者が感じるほどアルゴリズムの抽象化は容易ではないかもしれず、その場合に数学者にとってはほとんど類題とみなせる問題でも一般の参加者にとってはそうでない可能性もあります。そのため、何をもって既出とみなすかの判断も人によって違いそうですね。
なお既出要素の高い類題が繰り返し出題されることもあり、そのような問題は「典型」と呼ばれています。参加者目線では、典型を学べば必然的に正解できる問題が増えやすいので典型問題の需要はそこそこ高く、それゆえwriterさんにとっても典型問題は安心して出題しやすいという正のスパイラルが生じるかもしれませんね。もちろんwriterさんがどういう気持ちかは知らないのであくまで想像です。
既出問題・オマージュ問題の例
yukicoder contest 402 E問題 - 奇行列式
解説に明記されているようにAdvent Calendar Contest 2022 (yukicoder) I問題 - [Cherry Anniversary 2] 19 Petals of Cherryのオマージュ問題です。
yukicoder contest 362 A問題 - A+B問題
問題文に明記されているようにyukicoder No.1088 A+B Problemのオマージュ問題です。
Japan Alumni Group Summer Camp 2023 Day 2 J問題 - Knight Game
Knight’s tour問題という有名問題の2人プレイヤー版で、検索すると類題がいくつか引っかかります。特にそのうちの1つで2手目から始める問題と完全に一致します。類題も含めれば解説がブログから動画までたくさん出回っているので恐らく意図的なオマージュだと思いますが、解説は記事執筆時点で「後程追記します」と一言書かれているだけで特に引用もなかったので、本当にオマージュなのかたまたま知らなかったのかは分かりません。
AtCoder Regular Contest 165 A問題 - Sum equals LCM
writerさんの日記に明記されているようにyukicoder No.2384 Permutations of Permutationsを元ネタとする問題です。
yukicoder contest 360 G - Concon Substrings (ConVersion)
明記はされていませんがwriterさんのツイートを参考にすると恐らくAtCoder Regular Contest 140 B - Shorten ARCの改題のようです。
yukicoder No.2085 Directed Complete Graph
リアクティブ要素を除けばstackexchangeで解法まで完全に解説されています。検索で上位に引っかかりますが解説などにはオマージュ元として明記されていないので、たまたま既出の問題と被ってしまったのでしょうね。
未定義語や定義通りでない語
競技プログラミングでは数学と比較して未定義語が頻繁に用いられます。というより未定義語を用いているという感覚ではなく、「このように書いた時は定義をしなくてもこういう意味で受け取る」のような慣習がいくつか競技プログラミングにあるようで、そういった慣習を知らない数学者がいざ問題を解こうと思うと未定義語の羅列に見えてしまうという罠です。
それに加えて、記号や用語の説明はそれらが初出の時点では与えられず、ずっと後になって説明されるということも多々あります。従って未定義語に出くわした場合も、そこでフリーズせずに無視して読み進める方がよさそうです。
また、場合によっては定義のある語であってもwriterさんの意図を汲んで別の定義に読み替える必要がある場合もあります。こう書くと数学者の方に心配されるかもしれませんが、基本的には厳密な問題文が大半であることは強調しておきます。
未定義語や定義通りでない語の使用例
(名詞)(変数)
具体例:yukicoder contest 371 (Asakatsu Presents) C - みちらcolor
冒頭に「色$M$」という用語が出てくるので、自然に解釈すれば$M$は色を表す(例えば「白」なりの文字列を値に持つ)変数と考えるわけです。しかしその後で「色$A$と$B$を混ぜる時にできる色は$\lfloor \frac{A+B}{2} \rfloor$とします」という文言が現れ、混乱します。色には四則演算やfloor関数が定義されている……?
そして読み進めていくと問題文より後に不等式$1 \leq M \leq 1000$と「入力は全て整数」という文言に出くわします。この時点でようやく、この問題における色とは日常会話で用いる用語とは別物の整数値である何かのことだったことが明かされるわけです。
一般に、競技プログラミングでは「(名詞)(変数)」の組み合わせが現れたら
- 変数が非負整数値(resp.正)であること。
- (名詞)が非負(resp.正)整数で番号付けられていること。
- 各非負(resp.正)整数$i$に対し「(名詞)$i$」で番号が$i$である(名詞)を表すこと。
が暗に課されていることが多いので気を付けましょう。もっともこの慣習は競技プログラミングに慣れている人でも違和感を持ちうるもののようです。
参考:
(記号)_(添字)
具体例1:yukicoder contest 358 G - Sum of Subset mod 999630629
$A_i$という記号が数式の中に唐突に現れますが、これは頻出の記法なので覚えておくと良いです。数学だと下付き添字は複数の変数などを区別するためによく使われますが、競技プログラミングだと断りのない限り、$A_i$で長さ$N$の数列$A$の第$i$成分(つまり$A$を$N$以下の正整数全体の集合を定義域に持つ写像とみなして$i$を代入した値)を表すようです。
より一般に、例えば$x$と$x_1$が使われている場合、普通の数学のように$x$と$x_1$が$2$つの変数を表すとは限らず、断りのない限り$x$に$1$を代入した値を表すことがあるわけですね。なかなか非自明な記法ですが、競技プログラミングでは頻出です。
具体例2:Convolution (Library Checker)
既に問題文が変更されていますが、元々は$c_i = \sum_{j = 0}^{i} a_j b_{i-j}$という定義でした。$i > N-1$の時に$j > N-1$になりえて$a_j$が未定義になるのですが、恐らく(記号)_(添字)の形の未定義値は断りのない限り$0$として扱うという措置が取られていたのだと推測します。
ただしLibrary Checkerは競技プログラミングサイトではなく、別件に対するyosupoさんのコメントによりますと「競プロをそれなりにやっていてライブラリをベリファイしたい人が、問題文を読んで誤解を招かない」なら問題文として十分だと考えた上で提供されているサービスであるため、このような措置が競技プログラミングで一般的であるという保証はありません。
誤差の侘び寂び
具体例:yukicoder No.3072 Sum of sqrt(x)
問題文冒頭に「~を求めてください。絶対誤差または相対誤差の小さいほうが$10^{-15}$以下のとき正解とみなされます」と明記されているので文字通りに解釈すると、求めるべき正しい値を$x_0$と置いた時に条件
- $\lvert x - x_0 \rvert \leq 10^{-15}$
- $x_0 \neq 0$かつ$\lvert \frac{x}{x_0} - 1 \rvert \leq 10^{-15}$ のいずれかが成り立つ実数$x$が正解とみなされることになります。
一方でこの問題は、上の$2$条件のいずれかが成り立つ実数$x$を出力しても正解となりません。これはおかしいのではないかと思いwriterさんに質問してみたところ、「この問題に限らず小数誤差許容問題では想定解からの誤差が一定以下であることがACの条件となっており、想定解の誤差が許容誤差より十分小さくなるように作問されます。この問題では想定解の誤差は$10^{-17}$以下と見積もられています。」という明瞭なご回答をいただきました。
つまり競技プログラミングの誤差許容問題においては、断りのない限り$x_0$からの誤差ではなく(多くのコンテストでは事前に非公開されていない)想定解で出力される値$x_1$からの誤差をもとに正解か否かが判定され、その結果$x_0$からの誤差が許容範囲であっても不正解になり得るということです。断りがないという点が初学者には罠ですね。
極端な話$x_1$が$x_0$とかけ離れていたとしても、非公開な値である$x_1$を推測してそこからの誤差を見積もらなければ正解できないというなかなか非自明な慣習です。もちろんそのような問題が出題されるとコンテスト参加者は悲しい思いをするので、実際には$x_1$を$x_0$に十分近く設定することがwriterさんには暗に期待されているでしょうね。writerさんの暗黙の意図や非公開の基準値$x_1$、参加者からwriterさんへの期待など、問題文やルールなどの公開領域に書かれていない空気を察する必要がある点で競技プログラミングの慣習の中でもひときわ非自明に感じました。
なお今回は断りのない限り$x_0$ではなく$x_1$を基準にするという話ですが、$x_1$を基準にする旨を明記することも多々あるようです。その場合はあまり好意的でない批判が生じることもあるようなので、明記することのメリット(問題の正解の定義を少しだけ明確にできること)がデメリット(批判を受けること)よち低いと考えられているからかもしれません。明記した方が批判されるというのはなかなか面白い話ですね。
もちろん、明記した上で$x_1$を公開情報にしてしまえば批判される余地はほとんどなさそうですね。例えば$x_1$を$x_0$を用いて厳密に表したり(特に$x_1$を$x_0$そのものにできるならしてしまったり)。そうしないことが多いのは、そうすることのメリット(問題の正解の定義を完全に明確にできること)がデメリット(そのように作問するためには時間がかかる)より低いと考えられているからかもしれません。
参考:
多項式の侘び寂び
具体例:Division of Polynomials (Library Checker)
※以下は多項式が関わる問題一般の話ではなく、この問題固有の話だとお考えください。
問題文では$f$や$g$の係数が明記されていませんが、競技プログラミングではたまに整数であるという旨が省略されることがあり、上でも引用したyosupoさんのコメントによると特にLibrary Checkerではその傾向があるそうです。
というわけで$f$と$g$は整数係数であることを前提に話を進めるのですが、そうすると$1$変数多項式の除算はmonicでない場合に整数係数の範疇では必ずしも定義されないため問題が成立しなくなります。また零多項式の次数も文献次第であり、もし次数$0$と判断すると問題が成立しなくなります。それに関してmapsyさんのコメントによると、問題文を適宜読み替えて定義を変更することで問題が成立する形に解釈する(つまり問題文を厳密に読み解くのではなく作問者が想定した通りに誤読する)ことが本件では期待されているようです。
ただ、このやり取りはあまり意思疎通が正確にできていないかもしれません。というのも上で引用したyosupoさんのコメントでは「競プロをそれなりにやっていてライブラリをベリファイしたい人が、問題文を読んで誤解を招かない」ということが述べられていたのでそれを前提に競技プログラミングに精通している人のこの問題への判断を話題にしていたのですが、一方でmaspyさんのコメントを踏まえるとmaspyさんはどうもその辺のコメントをお読みになっていなかったのか、この問題だけでなく何故か一般の問題についてのお話だとご理解していらっしゃったようで『競プロユーザーも様々なので、あまり何でも「これが競プロで普通」というように理解しない方が良いと思います』とご警告してくださっておりこちらが「競プロでは不備を許容するのが普通であるというような曲解」をしていると思いこんでいらっしゃるようだったからです。
また想定通りに誤読をすることを期待しているかについてのyosupoさんのコメントでは明確にYesとお答えいただいていますがmaspyさんのコメントではNoとお答えいただいているので、この話題の前提である「競プロをそれなりにやっていてライブラリをベリファイしたい人が、問題文を読んで誤解を招かない」こと自体がそもそも誤りのようですね。