AtCoder茶コーダー、AHC030に初挑戦～水パフォ取れました～
AtCoder？競技プログラミング？
将棋のことを書くつもりで始めたNoteなのに、放置して久しぶりの投稿が何の脈絡もないAtCoderの話です。
AtCoderは競技プログラミングで、短時間でアルゴリズムの正否を競うコンテストと、長時間でできるだけ良い得点を競うヒューリスティックコンテストがあります。
難易度は圧倒的にヒューリスティックの方が高いです。
今回はAtCoderのヒューリスティックコンテスト、つまりAHC030に初挑戦した話です。
私のレベル
アルゴリズムの方は2023年の1月に始めて、競プロ歴1年ちょっとです。友達が始めたので自分も始めたんですが、自分が一番ハマってますね。０からのスタートです。（厳密にはHTMLで「Hello World!」したことあるのと、四則演算の×が＊、÷が/ってことは知ってたけど、0.01からのスタートぐらいでしょう）初めからPythonを使っています。今はABCが2完～4完、ARCが0完～1完の茶コーダーです。
去年は入茶して完全に気が緩んでますね笑。今年は決意を新たに入緑目指して頑張ってます。そして昨日のARC、1問目から配点500点という聞いたことない難易度でしたが、1完（B問題）して最高レート更新！レートがハイになって、気分もハイになってしまいました。解ける、今なら解ける。過去問じゃダメだ、熱々の本番問題を持ってこい！ふと目に入るAtCoderトップページの開催中の文字。こんな時間に開催中とな？ほほう、ヒューリスティックか。まあ、行けるやろ。過去問も解いたことないのに参加ボタンを押してました。
問題を見てみて
過去問を解いたことはないんですが、そのうち挑戦したいと思って見たことはあるんです。うわー難しそうだな、今の力じゃ無理だー。そう思って過去問を解くことすらしてなかったんですね。いざ本番問題を見て。ポリオミノ？スコアのつけ方どういうこと？入出力が複雑だ、結局何すればいいの？なんで過去問0問なのに参加してんだー、と思考がぐるぐるぐるぐる数十分間、問題文とにらめっこしてました。
落ち着くためにできること
どんな問題でも、与えられた標準入力を受け取らないと始まりませんよね。まずは与えられた数値を受け取る部分のコードを書きました。ちょっと落ち着きました。そして制限の確認。これもアルゴリズムとやること同じ。実行時間3秒、いつもだいたい2秒だから長いな。島は最大20×20、小さいな。見えてなかったことが見えてきます。いや、待て、島、小さいな！！！
①まずはAC
エヴァンゲリオンに初めて乗ったシンジ君にリツコさんは言いました。「シンジ君、今は歩くことだけ考えて」
AHCは開催中何度でも出し直しができます。初めてのAHC。１回目の提出。「今はACすることだけ考えて」そう自分に言い聞かせました。この問題、島が小さいのが最初のポイントなんですね。出力して質問できるのはエリアか、1マスごと。効率の話は置いておいて、20×20の島なら1マスずつ全部調べても余裕。そう気付いた時、ACは行けるなと確信しました。ABC,ARCで出たとしてもそこまで難しくはない。さて後はどう得点を伸ばしていこうか。そう考えながら初提出。
ところが！WAだと・・・（まさか、暴走！？）
慌ててサンプルコードと見比べました。
（実はもっと早くサンプルコードの存在に気付いてたんですが、「サンプルコードまでついてるんか。しかも自分が使ってるpython！どれどれ、2重ループで1マスずつ全探索。自分で思いついたのと同じか。こちとら茶コーダー、そのぐらい自力で書けらあっ！」って流し読みしてました。）
原因は、埋蔵量＝１で判定してたから。問題文ちゃんと読んでれば、油田が重なって2以上になるってわかるでしょうに。シンジ君ばりにコケた初出撃でした。
判定を埋蔵量！＝０に直して、30分後、AC。
（AHCは誤答ペナ無いけど、次の提出まで30分待つ必要がある）
対話型の問題のとっつきにくさ
この問題みたいに標準入力と標準出力が対話のように繰り返される問題のことをインタラクティブ問題って言うんですね。（さっき調べて知った。）ABC、ARCで慣れてるのは一問一答なので、この形式なだけで難しそうって思っちゃいます。AHC初参加の私も未経験なので、と思いきや実は１回だけ解いてるんです！しかも最近。それはABC337-E。この回は4完できて、初のABC5完あるかと思ってましたが時間切れ。途中まで解けてたこの問題こそインタラクティブ問題でした。コンテスト終了後にAC。１回でも解いたことがあるという経験は心強いです。
やることは標準入力と標準出力を繰り返すだけで、難しそうと思ってたわりに、すんなり行けて拍子抜けしました。
気になるのは問題文にわざわざ赤文字で
”出力の後には改行をし、更に標準出力を flush しなければならない。 そうしない場合、TLEとなる可能性がある。”
って脅し文句？警告文？が書いてあるのですが、いつも通りの標準入出力で通りました。この一文には結構ビビりました。（Pythonだからか、とか今回は良かったけど今後のために改行とflushしなさいとか、有識者の方に教えてもらいたいです。）
②最初に思いついた効率化
全探索ベースでできそうなこととして、まず思いついたのが埋蔵量の総量を先に計算してそこに達したら終わりにするというもの。掘り終わってるのに、何もないところ掘ってるのは無駄ですからね。実装もそんなに難しくない。
まずはACの①から素点を12億も減らすことができました。（今回は素点を低くすればするほど、得点は良い）12億って言ったらアレですよ、直大さんの年収ぐらいじゃないですか？（全く知らないのにテキトーなこと言ってスミマセン）ちょっとした工夫だけでも点数がこれだけ変わるのがAHCの面白さなんですね。
③一つ見つけたらそこから広げる（幅優先）
次に思いついたのは、一か所見つけたらそこから周りに拡げてその油田を掘り切っちゃうという作戦。拡げ方は幅優先探索と同じです。ABC、ARCで幅優先探索使う問題が出てもスタート位置からの距離の管理とかでつまずいて上手くいったためしがないんですが、今回はそういうの無しで訪問した場所の管理と次に探索する場所だけでいいから普段よりだいぶ簡単。①、②に組み合わせて使います。
だいぶ簡単って言っといて、2回実装ミスってるのバレてるって。でも桁が変わったぞ。大きな前進！
④占い（エリア探索）使ってみる
ここまで1マス探索しか使ってないけど、占い使ってみたいし、絶対ちまちま1マスずつやるより、上手くやればエリアで探しちゃった方が効率良いに決まってる！そう思っていろいろ考えたが、いい方法がなかなか思いつかない。たとえば島を4分割するとか、2マスずつ探索するとか……。メリットはそのエリアに油田がないことが分かれば結構いいけど、4分割して島全体にあるって分かっても、メリットにならなそう。結局、横１行を1つのエリアにして占うことにした。もしその範囲に埋蔵量が無かったら、一行すっ飛ばす。
ほんのちょっとだけ改善できてる！
⑤新発明！？市松探索
2マスごとに占うというアイデアはあったが、1マス掘るのも2マスに一回でいいんじゃない？って思えてきた。それを行ごとに互い違いにして市松模様にしていけば、油田の一部がどこかに引っかかる、1か所分かればすでに実装済みの幅優先探索で見つけられる。完璧な作戦だ！
市松模様は、(i+j) % 2 = 1で簡単に判別できます。（(i+j) % 2 = 0でもいいけど、Nが奇数の時は、=1の方が1マス少ないですね）
軽く調べて出てこなかったけど、この手法って確立されてないんですかね？もしなかったら発明です。車輪の再発明だぞって笑われる可能性はかなりあると思ってますが。
めっちゃ伸びた！伸びるとは思ってました。明らかに調べるマス目の数減りますからね。
ところで、この手法一つ不安要素がありました。もし1×1マスの油田が存在した場合、抜け落ちちゃうんですよね。これではザル探索です。ザルも格子状なだけに、ってやかましいわ！
ポリオミノのwikipediaには最少は１×１と書いてあるけど、この問題文では”各油田は 1×1 マスの正方形の辺同士を繋げた連結な ポリオミノ 型”と書いてある。連結なポリオミノ型って記述を見ると1×1は入ってないって解釈でいいのかなという気がしました。（ここ、皆さんの意見もちょうだいしたいところですね）
実際は各油田が1×1じゃないか判定して、無ければ市松探索、含まれていたら全探索という実装にしました。
⑥ランダムで探す
四角い盤面から1マス掘って探して、また1マス掘って探して。こんなことを繰り返してるとあのゲームが頭をよぎります。そうです、マインスイーパです。それで、ふと思いました。マインスイーパは左上から、ちまちまやるより最初に数か所ランダムにポチポチポチって探して、後から細部を詰める方が効率良いよなって。（体感的に。根拠はありません。）ランダム性を足してみるかってことで、どうランダム性を持たせるか。市松模様の座標のリストを作って何回目かカウントしつつ、x = (len(リスト) - cnt) % len(リスト) として次々にリストのx番目をpopしていく。先生が「教科書153ページ、生徒30人で割った余りの出席番号３番読んで」というノリで、似非の擬似乱数（まぎらわしいけど。）を即席で作りました。本当はちゃんと擬似乱数使った方がいいんだろうな、と思いつつも使ったことないので調べるのめんどいなっていうのと、ランダム性意味あるのか？という半信半疑だったので、とりあえず、これで提出してみて考えるかという感じです。AHCはとりあえず試してみる、ができるのがいいところ。
なんと明らかに有意な差が出てます！やってみるもんですね
⑦縦の列でも占ってみる
⑥はノリで試してみましたが、今度は真面目な改善案。横の行ごとに占って埋蔵量が0ならスキップするというのを実装済みですが、同じことを縦の列でもやってみることにします。
嘘！？ここにきて初めての悪化。占いコストがかかってしまっているんですね。
⑧縦横占いを市松部分だけに
よくよく考えると、占った後に市松部分しか掘らないので、市松部分の座標を抜き出して、それを縦横ごとに占うことにします。
なんとなんと再びの悪化。占う集合内の座標数が減ったことによるコスト増が原因だと思います。（広範囲ほどコストが低い）
⑨1行占い意味ある？
縦の占い増やしたらコスト増で悪化してしまったので、横の占いって本当に意味あるのか疑わしくなってきます。いっそ外してみる？試せるのがAHCのいいところ（何回目だこれ）
⑥のコードから横の占い外したのが⑨のコード。改善してる！横の占い意味なかったんかい！
⑩擬似乱数を使う
⑥でランダム性持たせたら良くなったんですが、ちゃんとした擬似乱数使ったわけではありませんでした。少し調べてみると、序盤で右下あたりに偏るようになってます。ここはちゃんとした擬似乱数を使いましょう。（最初からそうしろ）
改善しました。当たり前かもしれません。
最終提出と結果
今回のAHCは市松模様をランダムに探索して、そこから幅優先で油田を掘るという⑩のコードを提出しました。最終的にシンプルなつくりになってます。
結果は……423位！（暫定時428位）
パフォーマンス1356、水パフォでした！
めちゃめちゃ上出来です！
今回できなかったこと
結果は良かったのですが、できなかったこともいろいろあります。まず一つが……ビジュアライザー使ってない！
ここまで一切ビジュアライザー登場してませんね。触りはしました。でも分からなかったんです。ちゃんと調べればわかるような気はしました。でも、ビジュアライザーなくても提出できる→改善案思いつく→試して提出→また改善、みたいなループで使い方調べるタイミングがなかったんですよね。目で見ればまた違ったアイデアも生まれたかもしれません。あと、AHCやってる人ってビジュアライザー走らせてカッケー！っていう憧れは以前から少しあります笑。
解法に関しては、小さい改善と大きい改善がありそうです。
小さい改善はランダム性に頼ってる部分ですね。左上→右下→左下→右上→真ん中、みたいに意図的に分散させて探索できればもう少しは良くなりそうです。
大きい改善は、油田の形を利用することと、占いを利用することです。占い無しでも1マスずつ探索しても途中で油田の形を特定すれば、効率化できそうです。また、占いで油田の位置を特定できるようになればさらに効率的だと思いますが、このあたりのレベルは今の自分の実力には荷が重いかもしれません。
終わりに
AHC030、1位はテリーさんでしたね。競プロ関係でXフォローしてるのはテリーさんだけなので、こっそり応援してました。テリーさん、ならびにロボてりーさん、おめでとうございます！
そしてAtCoderには感謝しかないです。競プロというかプログラミング自体を始めたのはAtCoderのおかげですし、今回ヒューリスティックという新たな世界へと誘ってくれました。本当にありがとうございます。あ、直大さんのXもフォローしてました。
普段の勉強はあさかつとまよこんに参加すること（出たり出なかったりだけど）と、その復習ぐらいです。バチャ大好き人間です。その運営にも感謝してます。ありがとうございます。まよさんのXもフォローしてましたわ。
一番言いたいことは、ヒューリスティックめっちゃ楽しい！そして初心者でも結構やれることある！ってことです。
次も絶対参加したいと思っている自分がいます。
この記事が気に入ったらサポートをしてみませんか？