AtCoder Conference 2025

Transcript

1. ライブ参加で探る - 競プロを長く楽しむヒントと AHCへのアプローチ 診断人(@NICO_SHINDANNIN)
2. 自己紹介 • 診断人(shindannin) ▪ 2008年に競プロをはじめる ▪ ニコ生でライブ放送していた ▪ ゲームプログラマー ▪ AHCを中心に参加 ◦ 焼きなまし法のコツ ◦ 第１回マスターズ選手権 ２位 2
3. 好きなアルゴリズムは？ The Slido app must be installed on every computer you’re presenting from
4. 本日の内容 • １ 競技プログラミングの幅 ▪さまざまなコンテストの歴史 • ２ 競技プログラミングを続けるコツ • ３ 競技プログラミングの深さ ▪AHCレッドコーダーにインタビュー 4
5. １ 競技プログラミングの幅 5
6. https://x.com/yu4u/status/1783470935884136948/photo/1
7. 競技プログラミングの幅 • 一般のイメージ→ABC, ARC系。正解がある。 • いろいろなコンテストがある ▪ 使用するアルゴリズム・技術の違いがある ▪ 競技プログラミングが役に立つことが増える 7
8. 好きなジャンルは？ The Slido app must be installed on every computer you’re presenting from
9. ゲームAI系 • CodinGame 9 https://www.codingame.com/replay/12468653
10. ゲームAI系 • Kaggle – Lux AI 10 https://www.kaggle.com/competitions/lux-ai-2021
11. ゲームAI系 • CodeVS（終了） 11 https://www.youtube.com/watch?v=opaDu3FKfzg
12. 言語が選べない • CODEFORCES – Unknown Language Round ▪ コンテスト開始直前まで、使用言語が明かされない。 12
13. 言語が選べない 13
14. 言語が選べない • Befunge 14
15. 量子コンテスト • CODEFORCES – Microsoft Q# Coding Contest (2018) 15
16. 量子コンテスト • QCoder 16 https://www.qcoder.jp/ja
17. 圧縮・解凍するだけ • AtCoder - Weathernews Programming Competition 17
18. TopCoderのクラウド ▪ 開発アイディアを出すコンテスト ▪ 不具合報告コンテスト 18
19. Google - Distributed Code Jam（終了） • 分散並列計算 ▪ 入力が10^13とかあるが、分散させることができる ▪ 分散版の二分探索など、分散独自のアルゴリズムもい ろいろある。 19
20. Google - Hash Code （終了） • ヒューリスティック＆巨大データ ▪ テストケースが１つ１つが全然違う ▪ 巨大なデータの癖を分析する必要がある。 ◦ データ分析と貪欲法が大事 20
21. GPU/シェーダ言語 • Shader Competition 21 https://shader-competition.saina.jp
22. GPU/シェーダ言語 • 出力が画像 22
23. GPU/シェーダ言語 • 出力が音声 23
24. 24 競技プログラミング の幅 GPU – O(logN)で総和 http://sp16.cs179.org/
25. 競技プログラミングの幅 - まとめ • いろいろなコンテストがある • 新たな発見もあるので、様々なコンテスト に、ぜひチャレンジを！ • 新しいコンテストが現れてほしい 25
26. ２ 競技プログラミングを 続けるコツ 26
27. 競技プログラミングを続けるうえで 困難なこと The Slido app must be installed on every computer you’re presenting from
28. 競プロを続ける難しさ • 時間がない • 練習しないとレートが下がる • 飽きる？ • まわりの人がやらなくなる？ 28
29. 競プロを続ける難しさ • 時間がない ▪ 学業・入試・卒論 ▪ 就職・昇進 ▪ 家庭 29
30. 競プロを続ける難しさ • 練習しないとレートが下がる ▪ モチベーション低下 ▪ レートが下がるのを恐れてコンテストに参加しない 30
31. 競プロを続けるコツ • 参加するコンテストを変えてみる。 ▪ 時間の融通が利かない ◦ AHCなどの長期コンテスト ◦ AtCoder以外もあります（Kaggle, CodinGameなど） ▪ 時間が足りない ◦ ABCなどの短期コンテスト ◦ 練習せずに参加してもOK！ 31
32. 競プロを続けるコツ • どうしても忙しく無理→いったんやめる。 ▪ 忙しさが落ち着いてから、しれっと復帰する。 ▪ 復帰しづらいかもしれないが、気にしない。 ▪ 相対的なレートでは落ちていても その後続ければ、絶対的な実力は上がってるはず 32
33. 競プロを続けるコツ • コミュニティ ▪ SNS - X(twitter)など ▪ YouTubeライブを見てみる。してみる。 ▪ 大学内の合宿系コンテストに参加 ▪ オフ会 33
34. 競プロを続けるコツ • 栄枯盛衰だと思う（気にしない） 34
35. 注意！ • 現在競プロにはまっている状態なら 全時間突っ込んでOKです！ ▪ 一番実力が上がる時期 ▪ 「競プロ以外の大事なこともやらなければ」と思って も、他の事もどうせ手がつかないので無理です。 35
36. ３ 競技プログラミングの深さ 36
37. AHCが攻略されつつある？ • OpenAIが２位 37
38. AHCが攻略されつつある？ • 一方で、 ▪ AIはAHC界隈のアルゴリズムを使用している ▪ コミュニティ内で流行ってない 意外で効果的なアルゴリズムがありそうなのに • 一般問題でもヒューリスティック界隈のアルゴ リズムは強いという結論？ 38
39. そこで • 有識者の方に聞いてみました。 • ついでに、AHCのコツについても聞きまし た。 39
40. ４名のレッドコーダーにインタビュー • saharanさん • montplusaさん • tomerunさん • simanさん 40
41. 貪欲法は簡単そうに見えて最難関 • 貪欲法 ▪ ABCでも、いくらでも難しい問題が作れる ▪ AHCでも、やりかたがいくらでもある。 • 焼きなまし法やビームサーチより重要そう 41
42. 【質問１】 AHCで貪欲法が重要とさ れていますが、攻略の定 型化は難しいと考えてい ます。貪欲法を使用する 際に、意識している点や 工夫している点はありま すか？ 42
43. saharanさんの回答 43 • 「どの要素を簡略化するか」というのが難しく、いつも注意 して考えるようにしていますが、しばしば失敗します。また、 いきなり賢い貪欲法を書こうとせず、まずはすごく単純なも のを書いてみて、ビジュアライザで挙動を観察しながら次は どこに手を付けるとよさそうかというのを考えるようにして います。あとは、「焼けそう！」と思ってももう少し我慢し て貪欲を考える、というのを意識するようにしています。
44. montplusaさんの回答 44 • （ここでは、少なくとも何らかの評価関数が後ろで見え隠れ しているタイプの貪欲法について書いています）最適化問題 を考えたとき、最小化・最大化したい指標に対してまさしく "貪欲に"採用するようなアルゴリズムが一番最初に思いつき ますが、その後に将来的にツケが回ってくるような要素があ ればその分評価を減衰させて評価するというような構造にで きないか考えます。
45. montplusaさんの回答 45 • 例として、「魔法使いがボスとの戦闘を終えるの にかかるターン数を最小化する」みたいな問題を 考えると、1ターンのダメージを最大化したくな りますが、MP消費が激しい魔法では後半でMPが 枯渇して失速してしまうので、制約によってはMP の効率を意識したほうがよかったりします。
46. tomerunさんの回答 46 • 貪欲というと目先の利益だけで動いていく という印象がありますが、そうならないよ う、あくまで理想的な状態を考えてそれに 近付いていけるような方法を考えます。
47. simanさんの回答 47 • 自分は貪欲法が得意とは言えませんが、takapt さんが書かれていた 「確実に前進」という指針は今でも強く意識しています。 「Topcoderマラソンマッチの探索問題で重要なこと」 https://qiita.com/takapt0226/items/b2f6d1d77a034b529e21 • 普段はまず、その盤面から打てる合法手をすべてピックアップし、 その中から「この手を打つと確実にスコアが上がる（もしくは悪化 しない）」ものを探す、という考え方でやっています。ただ、これ はやってみるとかなり難しいです。
48. simanさんの回答 48 • 貪欲法は本質的に「常に良い状態を選び続ける」手法なので「一時 的には盤面が弱く見えるけれど、最終的にはそのほうが良くなる 手」の評価がとても難しくなります。そういうケースでは、1 手進 めたうえで、その評価関数の中でさらに「N 手ぶん簡易シミュレー ションしてみる」といった工夫を入れることもあります。ただし、 このやり方だと 1 手あたりの評価コストが重くなってしまうので、 「もっと軽量な近似評価でうまく代用できないか？」といつも悩ん でいます。
49. simanさんの回答 49 • 自分の中で、貪欲法における基本的な評価関数のイメージは `問題のスコア + 良い特徴量 - 悪い特徴量` という形です。そ して、この「良い特徴量」と「悪い特徴量」にどれだけ気づ けるかが、貪欲の強さを大きく左右すると思っています。と はいえ、何が良くて何が悪いのかを判断するのは簡単ではな く、結局はいつもビジュアライザとにらめっこしながら試行 錯誤しています。
50. simanさんの回答 50 • 盤面状態に関するあらゆる情報を可視化しておき、「どのような状 態になっていれば良いのか」を考察しやすい環境を作ることが大事 だと感じています。AHC は標準のビジュアライザがよくできている ので、それをそのまま使うだけでも十分に考察はできますが、生成 AI がある現在では、独自のビジュアライザを用意しつつ、問題のコ アな部分を理解・抽出するための可視化の重要度が、以前にも増し て高くなっているのではないかと感じています。
51. 【質問３】 AHCで、技術的に未開 拓だと感じる領域や、 現状の手法では攻略し きれていない問題タイ プはありますか？ 51
52. saharanさんの回答 52 • 参加者のレベルがとても高いので、コンテス トで出された問題は概ね制約の範囲内では攻 略されていると感じます。技術的には、SIMD にとどまらずマルチコアを扱うような問題や、 GPU が利用可能な環境での問題が未開拓な領 域だと感じています。
53. saharanさんの回答 53 • あとは、実業務でありがちな、入出力や問題 の制約が最初からは完全に決まっておらず、 様々な要素や要求を考慮して最適化問題に落 とし込んでいくパートなどがありますが、こ れはコンテストとして出題するのは非常に難 しそうです。
54. montplusaさんの回答 54 • AHCは競技性・楽しさの観点から極端に大きなインスタンス の問題は出ない気がしています（アルゴではよくある10^6サ イズなど）。インスタンスが大きくなると焼きなまし相対的 に少し使いにくそうだなあという印象があり、計算資源が圧 倒的に足りない中での最適化みたいなところはあまり知見が 集まっていない気がします。（そもそも貪欲法しかなくなっ てしまうのかもしれませんが）
55. tomerunさんの回答 55 • 多目的最適化：単にスコア関数が複数の要素 を含むのではなく、それら複数の要素間の相 対的な重要度に対応する複数の出力を提案す るような形式 • 対戦相手が存在するようなゲーム
56. simanさんの回答 56 • どうしても時間制約が 2-3secになるので、長時間計算 が必要となりそうな大規模な問題はあまり開拓されて いないのかなと思っています。短時間だとどうしても 「焼きなまし」「ビームサーチ(貪欲)」が強くなる印象 なので、もっと時間制約を緩めることで新たな手法が 有効になってくるのかなと思っています。（例えば機 械学習とか）
57. 競技プログラミングの深さ（まとめ） • AHC攻略方法は徐々に確立しつつある ▪ 問題の条件によっては、まだまだ奥が深くなりそう 57
58. まとめ • １ 競技プログラミングの幅 ▪さまざまなコンテストの歴史 • ２ 競技プログラミングを続けるコツ • ３ 競技プログラミングの深さ ▪AHCレッドコーダーにインタビュー 58
59. Audience Q&A The Slido app must be installed on every computer you’re presenting from
60. ここからおまけ 60
61. 【質問６】 コンテスト終了後は、 どのように復習してい ますか？ 61
62. saharanさんの回答 62 • 流れてきた解法を見たり、上位の人のコー ドを読んで方針を理解するなどをしていま す。
63. saharanさんの回答 63 • 特に「それは思い付かなかった」という重要な考 察が流れてきた場合は ▪ なぜ思いつかなかったのか ▪ どういう思考過程を経ればその方針に辿り着けたか ▪ 賢い解法だが、これは思い付けなくても仕方ないものなのか などを分析します。
64. montplusaさんの回答 64 • コンテスト後にTwitterで大量の情報が飛び交 うので、その時にしっかりと他の解法を見て います。近い点数の人が実は違う解法だった り、あきらめた解法ができている人がいたり するので学びは大きいと感じています。
65. tomerunさんの回答 65 • 復習は特にしていません…（しなくて良い という意味ではないです）復習よりかは、 開催されているコンテストに出たいですか らね
66. simanさんの回答 66 • 基本的には上位入賞者の解法を見ながら復習していま す。昨今は生成AIのお陰でコードを読んでもらって細 かい部分の解説とかも出来るようになっているので便 利です。復習する場合は短期コンの問題をオススメし ます。長期コンに比べると問題もシンプルで解法も比 較的シンプルになりやすいので、そこまで時間をかけ ずに上位のスコアを獲得することが出来ると思います。
67. 【質問６】 コンテスト終了後は、 どのように復習してい ますか？ 67
68. saharanさんの回答 68 • 流れてきた解法を見たり、上位の人のコー ドを読んで方針を理解するなどをしていま す。
69. saharanさんの回答 69 • 特に「それは思い付かなかった」という重要な考 察が流れてきた場合は ▪ なぜ思いつかなかったのか ▪ どういう思考過程を経ればその方針に辿り着けたか ▪ 賢い解法だが、これは思い付けなくても仕方ないものなのか などを分析します。
70. montplusaさんの回答 70 • コンテスト後にTwitterで大量の情報が飛び交 うので、その時にしっかりと他の解法を見て います。近い点数の人が実は違う解法だった り、あきらめた解法ができている人がいたり するので学びは大きいと感じています。
71. tomerunさんの回答 71 • 復習は特にしていません…（しなくて良い という意味ではないです）復習よりかは、 開催されているコンテストに出たいですか らね
72. simanさんの回答 72 • 基本的には上位入賞者の解法を見ながら復習していま す。昨今は生成AIのお陰でコードを読んでもらって細 かい部分の解説とかも出来るようになっているので便 利です。復習する場合は短期コンの問題をオススメし ます。長期コンに比べると問題もシンプルで解法も比 較的シンプルになりやすいので、そこまで時間をかけ ずに上位のスコアを獲得することが出来ると思います。
73. 【質問２】 焼きなまし法・ビーム サーチなどの定番アル ゴリズムで、他の人と は違った工夫をしてい る点はありますか？ 73
74. saharanさんの回答 74 • ビームサーチでは、差分更新ビームサーチ (Euler tour beam search) を使うことで、今考えている問題（保持 すべき状態が大きい）にビームサーチが適用できるよ うにならないかというのを必ず考えるようにしていま す。焼きなまし法では、これといった一般的な工夫は 特にしていません。問題ごとのスコアの差分計算や近 傍の質が全ての鍵を握っている印象です。
75. montplusaさんの回答 75 • ビームサーチでは、高度化する前は必ず評価値計 算ののちにを乗せるようにしています。というの も、次候小さめの乱数成分補の評価値に大きな団 子地帯があると、それにわずかに及ばなかった実 はよい候補が淘汰されてしまい、似たような団子 地帯の候補ばかりが残るという現象が起きます。
76. montplusaさんの回答 76 • 実装初期はこの現象によりビームサーチの効果があま り実感できないことが多く、誤って「方針に見込みが ない」と方針を捨ててしまわないようにしています。 実装を詰めていくといわゆる重複盤面の除去や評価関 数の改善などにより、段階的にタイブレーク+α程度に 影響力を下げていっている記憶があります。
77. tomerunさんの回答 77 • ライブラリ化をしない（極限まで最適化を しようとすると結局全体に手を入れること になるので）（ほとんど整備をサボってい ることの言い訳です…）
78. simanさんの回答 78 • 焼きなまし法はそんなに得意ではないので他の人と異 なる工夫はあまり無いかもしれません。近傍はなるべ く小さく、差分計算が可能なものを考える（イテレー ションの回数を増やすため）ビームサーチはとにかく 「評価関数」と「多様性」が大事だと思っていて、重 複排除のためのハッシュ関数をいい感じに設計したり とかは頑張っているかもしれません。
79. simanさんの回答 79 • 「評価関数」は結局、貪欲の強さみたいなところがあ るので Q1の話と近いところがありますが、とにかくビ ジュアライザを見ながら「良い状態」とはみたいなこ とをずっと考えています。一応木上のビームサーチと かは手元に持っていますがここだけで差がつくみたい なことはあまり無い気がします。
80. 【質問８】 AHCの4時間コンテストで 意識している時間配分・ 進め方はどんなものです か？また、アイディアが 多すぎる場合の優先順位 のつけ方・戦略があれば 教えてください。 80
81. saharanさんの回答 81 • 最初 1 時間くらいは貪欲による方針をじっくり考えて、2 時 間時点で結果を見てその後の方針を決め、残り 2 時間で焼き なまし・ビームサーチ・貪欲を詰める、というのが理想のパ ターンですが、なかなか実現できていません。アイデアが多 すぎるときは、あまりに自明なもの、実装に時間がかかるも のを捨てて、ある程度の非自明さと実装のしやすさのトレー ドオフを考えて実装する方針を選択します。
82. montplusaさんの回答 82 • 4時間でできる範囲を見積もって、それ以上に手を伸ば さないようにしています。1位を狙うのであればちょっ と弱気すぎるかもしれませんが、最近の4時間コンテス トは4時間では詰め切れない複雑さの問題が出てきがち なので、ある程度の割り切りが重要な気がします。最 後の1時間はチューニングに使いたいので、メイン方針 自体は3時間時点で完成していたいです。
83. tomerunさんの回答 83 • 短期コンテストだと、とりあえずの貪欲を書いて様子 を見ようというのをついやってしまいますが、局所最 適に陥って本質的な強い戦略に行きづらくなるように 感じており、やめた方が良さそうだと最近思っていま す。前半2時間くらいは実験と考察に振るくらいで良い かもです。複数のアイディアの中では、実装量と影響 度のコスパが大きそうなものからやります。
84. simanさんの回答 84 • 4時間コンテストは「問題の誤読」が一番怖いので、最初の 30分は 問題理解の時間にしています。自分の経験上早めに解き始めても終 盤の数十分はパラメーター調整を行っていることが多いので、それ なら前半の数十分を問題理解の時間にしようという考えです。ここ 最近は生成AIのお陰で「とりあえず思いついたアイデア」を色々試 せるようになったので、特に優先度はつけていなくてとりあえず実 装してみてスコアを計算する、といった戦略になっています。
85. simanさんの回答 85 • 「評価関数」は結局、貪欲の強さみたいなところがあ るので Q1の話と近いところがありますが、とにかくビ ジュアライザを見ながら「良い状態」とはみたいなこ とをずっと考えています。一応木上のビームサーチと かは手元に持っていますがここだけで差がつくみたい なことはあまり無い気がします。
86. 【質問９】 AHCの10日間コンテス トで、スコアが伸びな い・アイデアが停滞し たとき、どのように打 開していますか？ 86
87. saharanさんの回答 87 • 苦しみます。とにかく考えられる方針を実装しやすいものか らできるだけ多く試していきます。やや hacky ですが、相対 スコアを利用して、どの傾向の問題でスコアが取れていない のかを見て伸びしろを分析します。Psyho のツイート (https://x.com/FakePsyho/status/1605570944537280512) を思い 出します。1 位のスコアから、解がどのような状態になって いる必要があるかを分析します。風呂に入ります。
88. montplusaさんの回答 88 • 基本的には、将来性のある解法を序盤にできるだけ慎 重に考えます。実装中の心づもりとしては、「まだこ の部分は詰め切っていない」という部分を常に持って おき、終盤までは完全に詰まることがないようにして います。なんとなく届かなさそうなときはほかの可能 性を探ってはいますが、そこは降りてくるかの運頼み なところがあります。
89. tomerunさんの回答 89 • そのような状態になってから打開できたこ とはないような気がしますね…
90. simanさんの回答 90 • スコアが伸びない、アイデアが停滞したときにやることですが、地道ですが やはり各テストケースを分析して、スコアが出るケースと出ないケースのビ ジュアライズ結果を比較していくのが大事だと思います。「どういう条件な ら高スコアになるのか」を調べられるように、様々なパラメーター（問題特 有のやつ, ex) フィールドの広さ) を可視化出来るようにして、高スコアを取る ための条件を整理していく感じです。また、制限を無視した場合にどうなる のかを実験したりもします。例えば制限時間が 2secなところを 200secにして 時間をかければ高スコアが取れるのかとか、何か制約を緩くしてみてその条 件なら高スコアが取れるのかとか、とにかく今上位が取っているであろうス コアはどうすれば追いつくことが出来るのかをひたすら考える感じです。
91. simanさんの回答 91 • 「評価関数」は結局、貪欲の強さみたいなところがあ るので Q1の話と近いところがありますが、とにかくビ ジュアライザを見ながら「良い状態」とはみたいなこ とをずっと考えています。一応木上のビームサーチと かは手元に持っていますがここだけで差がつくみたい なことはあまり無い気がします。