CODINGAME FALL CHALLENGE 2020
CodinGameのコンテストに参加しました。
2020/11/13~11/23の期間に開かれたCodinGame Fall Challenge 2020に参加しました。
コンテストの内容については例によってツカモさんのブログをどうぞ。
結果は世界626位/7011で、日本103位/320でシルバーでした。
今回はいつにもまして日本人参加者が多く、Twitterなどでも解法等の情報交換が活発にされていて、お祭りみたいな感じで非常に楽しかったです。
できればゴールドにも昇格したかったんですが、自分のプロフィールを見直してみたらゴールドに行けたコンテストはCrystal RushとCoders Strike Backだけだったのでまあまあそんなものかなという気もしています。ただ、開催期間の前半にハル研のプロコンが重なっていたのは少し痛かったです。本腰を入れてこちらに参加できたのが終了の三日前くらいだったので。
やったこと
基本的にはビームサーチをしました。ただ今回、構造体を使ってガチガチに書くぞと思ってやったら、処理がすごく重い(ノードに盤面の情報が全部乗っている)ものができてしまって、ビーム幅10で5,6ターンしか読めないような感じになってしまいました。日本人TOPだったichyoさんなんかはビーム幅1000の20ターン読みとかだったそうなので、全然ダメだとわかります(もちろん、ichyoさんのこれはTOP勢からしてもすごい読みらしいけど)。
時間について、盤面による差が激し過ぎたので、時間を計測しながら探索深度を増やして行って、途中で時間切れになったらそこまでの深度で打ち切るというのをしました。時間ギリギリまで回すビームサーチとしてはchokudaiサーチの方が一般的なのかもしれませんが、そこまでの実装はできませんでした。
盤面の評価関数は、自分のインベントリと自分の呪文、それから作ったポーションについてそれぞれ評価した和にしていました。各要素の評価は次のような感じ。
1.自分のインベントリ
各素材に1,2,3,4点を割り振ってその点数の合計。
素材が多過ぎても少な過ぎても嬉しくないので、それぞれの素材についてabs(5-数)。
種類が複数あると嬉しいので、それぞれの素材数の積をいい感じにしたもの。
これらの線形の結合。
2.自分の呪文
呪文自体の点数増加を計算。繰り返し使えるものは可能回数*0.7くらいで補正(書いていて気付きましたが、呪文の内容は固定なのでこれは前計算しておけばよかったですね……)。
持っている呪文の平均的なスコアを算出。
想定終了ターン数を40ターンくらいにしておいて、現在ターンから終了までのおおよそのターン数の目安を計算。それを上の呪文の平均点数にかけることで今持っている呪文で大体どれくらいの点数が得られるのかを算出。
3.作ったポーション
上記二つだけだと全然ポーションを作ってくれなかったので、ポーションを作るとスコアの増加に加えて5点分の価値を持たせた。
あとは、ポーションを5つ集めてリーチになったときは評価関数を変更して、勝利できるか否かだけを見ていました。この最後のところ以外は相手のことは少しも考慮しませんでした。
やりたかったこと
Twitterでも度々話題に上がっていましたけれど、インベントリのありうる状態数が14C4=1001(入試でよくある仕切りの位置を動かす組み合わせ)だったり、呪文の種類が50個以下、ポーションの種類が40個以下だったりしたので、手元の環境で全探索をバリバリ回して、その結果を埋め込むとか考えていました。
ときどきよくわからないところでTimeOutして負けるみたいなことがあって辛かったので、その辺をどうにか解消したかったです。自分のプログラムのバグなのか、でも、他の人も変なところでTimeOutすると言っている人がいるし……で正直よくわかりません。コドゲの時間周り難しい。
やるべきだったこと
ビームサーチという大まかな方針は決して間違ってはいなかったと思いますが(上位勢もわりとビーム撃っていたらしいので)、やっぱりあまりにも探索範囲が狭過ぎた。探索ノードについて必要最低限の情報を持たせながら探索するということが大切だなと思いました。この辺はビームサーチに慣れていなかったのもあるのかなーなんて思います。
よかったこと
多分初めてビームを撃った気がします。今までのマラソンマッチは大体焼きなましを使っていた気がするので。
今回ビームサーチを初めて書くにあたって、ツカモさんの以下のブログを大いに参考にさせてもらいました。先人の知恵は本当にありがたい。
次に向けて
今回の結果を受けて、ビームサーチやりたいなーと思っていたら、さんだーさんがこんなことを言ってらっしゃいました。
今回のコドゲで「やべぇぇ、ビームサーチやchokudaiサーチ勉強しなきゃ！」って思ったそこのあなた！ビーム系アルゴリズムのうってつけのゲーム、HyperSonicをやろう！題材もボンバーマンで、日本人になじみが深いぞ！https://t.co/34FUnr1B3u
— thunder≦4 (@thun_c) 2020年11月23日
やります。
やっています。
ICPC 2019 Asia Yokohama Regional参加記
2019年11月18日に横浜産貿ホールで開かれたICPC 2019 Asia Yokoama Regional 大会に、ziroppeくんとspiderさんとチームchoKOdaiとして参加しました。
結果はABの2完で、54/65位でした。予選最下位通過だったことを考えると健闘したと思います。ただ、もうあと一問くらい、Hは通したかった……。
準備
予選でABあたりの早解きを頑張って突破できた感じがあったので、それくらいの問題を一時間で解くみたいなバチャを立ててペアプロの練習をしたりしていました。チーム全員で集まって5時間フルの練習をするみたいなのは予定が合わず直前期にはできませんでしたが、9月中旬にあったJAGの夏合宿に参加させてもらって、むずかしーと言いながらも5時間コンの練習ができたのはよかったです。
1日目 11/16(土)
1日目はコンテストのリハーサルとチーム紹介などがありました。
昼頃にチームで集まって、会場に向かいます。会場の前にはコーチの堀先生が待ってくださっていて、お話ししたり写真を撮ってもらったりしました。会場に入ると、入り口で生徒証を見せたりするのですが、そのあたりのやり取りは全部英語で、わーアジア大会に来たんだという気分になります。ただ、今年は慶應がホスト校なので、スタッフの中にアルバイトで来ている同級生の知り合いとかがいたりして、割とリラックスできました。
クロークに荷物を預けて進むと、スナックエリアがあります。割と豪華に色々置いてあって、これを全部自由に取っていいとは太っ腹です。ペットボトルもあって、お茶やジュース、コーラなどもありました。朝コンビニで買ってきた手元のコーラを見て悲しくなりました。仕方がないのでチョコレートだけ頂いていきます。
指定された席に座って、荷物を広げたり、あたりをキョロキョロしてJAG合宿で会った方だー！ とか、牛の着ぐるみ被っている人がいるー！ とかしていると、そのうちに英語で諸々の説明が始まります。大事な諸注意とか色々。
その中でコンテストのシステムの説明が割と秀逸だったと思っていて、実際に前でスタッフの方が簡単な問題を解いて提出して見せたんですが、それがWAになって、Clerを投げて、testcaseをダウンロードして試してみたらコーナーケースで、直して提出してACという流れが、自然な流れで全部の機能を説明していてちょっと感動しました。
説明をそれなりに聞いて、それなりに聞き流していると、リハーサルのコンテストが始まります。 コンテストのシステムに慣れるためのものなので、気楽にやります。
問題内容は忘れましたがA,Bは割とやるだけだった気がしてすぐにAC。Cを見ると、前の木曜に学内の集まりでやった問題そのものだったので楽勝楽勝と思いました。チームメイト二人はそれに出ていなかったので、これは見かけはO(16!)で無理なんですが、実はそうではなくて、全探索でいけるんですよ、bitで集合を管理してDPをしてですね、と得意げに説明するんですが、解説を聞いただけで自分でちゃんと実装していなかったので、実はちゃんとわかっていなかった部分があったりして、バグが取れませんよ？ をやっていました。一度見た問題は、自分で実装できるところまでちゃんと理解しましょうね。
続いてチーム紹介が始まりました。競技に使っていたパソコンに各チームが用意してきたスライドが表示されるとともに、各チーム前に立って英語で色々とコメントしていきます。ネタに走ったスライドやチーム紹介が多く、終始楽しく見ていました。
僕たちのチームは、chokudaiさんが自己紹介時にハンドスプリングをするというのにあやかって、僕が側方宙返りをするというパフォーマンスをしました。僕らのチーム名はchoKOdaiなのでね。そこそこウケたのでよかったです。無理を言ってやらせてくれたチームメイトには感謝です。
ABC145
夜にAtCoderでABCがありました。レートが水色と青色の境目付近で青になれずに彷徨っていたので、今日こそ青に変色してICPC本番を迎えたいと意気込んで臨みましたが、ABCDの4完、レート-20で無事に冷えました。EもFもDPであることはわかっていたんですが、細かいところが詰められずに悲しかったです。ただ、DPだってのはわかったので実質全完だと言い聞かせて平静を保ちました。
ABC後に11:30くらいからcodeforcesのdiv2もあったのですが、さすがに次の日が朝早いので出ませんでした。
2日目 11/17(日)
無事に起床に成功したので、日本大通りに向かいます。電車でziroppeくんと合流し、駅でspiderさんとも合流。コンビニで適当にラムネとかを買って、会場に向かいます。あらゆる電子端末(腕時計含む)が持ち込み禁止なので、スマホとかを全部バックに詰め込んでクロークに預け、スナックエリアへ。コーラを手に入れます。今日はちゃんとコンビニで買わなかったのでね。
トイレへ行ったりライブラリの確認をしたりして時間を過ごしていると、前で説明があったりして、九時二十五分、コンテストが始まりました。
Aを見ます。パッと見てなんとなく3進数表現すると良さそう。二人にそのことを伝えて、入力を三進数表現に直すプログラムを適当に書きます。ziroppeくんはBを見にいきます。プログラムはできますが、単に三進数にしただけではダメ。考察していたspiderさんが、テープの速さを速くした後、戻す時に同じ速さをもう一回は繰り返さないといけないので、1桁目以外にビットが1以下の部分があってはいけないということに気づき、僕とspiderさんで書き上げます。ここまで40分くらい。提出してみると見事AC。
ziroppeくんにBの概要を聞きます。各定点が全ての各点にありうる値の範囲を与えるので、独立に処理して普通にいけそう。いけるねと言って、ziroppeくんと一緒にプログラムを書き始める。spiderさんには次に解くべき問題を探してもらう。ABは簡単だと明示されているけれど、それ以降はランダムな順なので。ただ、順位表を見るとHが解かれていて、それを重点的に見てもらう。
Bは各定点からDFSで波及させようとして、BFSじゃーん。いや、そんなことしなくてもマンハッタン距離じゃん……。という紆余曲折を経ながらもそれっぽいコードが出来上がる。ziroppeくんはきちんと隣り合う不定点同士が連続になるかが不安だったようで、僕も証明できませんでしたが、大丈夫大丈夫うまくいくよといって提出。ACしたので証明終了です。(あとからよく考えてみると、これあんまり良くないですね。ちゃんとある程度証明できる確信を持ってから出しましょう)
ここで順位表を確認してみると、40位くらいだった気がして、それなりにいい感じじゃないかなと思っていました。この勢いで3完しようと、spiderさんにHの様子を聞きます。どうやら構文解析みたいな問題のようです。
開き括弧と閉じ括弧でできた文字列がうまく整合が取れているかみたいなのを数え上げる問題で、これだけなら適当に残っている開き括弧の数とかを持っておけば前から順に処理できるんですが、面倒くさいのは'-'という文字があって、これがあると文字列が一文字消えるというので、これを処理するために、括弧での処理を適当なスタックに持たせてそれをpopさせながらロールバックするみたいなことを考えます。
なんとなくそれっぽいコードはできていきますが、spagetinizedされたなかなか見辛いコードを生成してしまいます。サンプルが合わないので三人でバグを洗い出していきます。だいぶ時間をかけますが、だんだんとわかってきて、サンプルケースも、適当に手元で作ったテストケースも全部通るようになります。いける！ とサブミット。WA。三人で頭を悩ましていると、ziroppeくんが、入力値ってint型じゃたりなくない？ と気づく。その通りで、long long に変えてサブミット。けどWA。
その後も色々と考えますが、結局WAが消えることはなく時間切れ。
三問考えていただけで、あっという間に5時間が過ぎていました。
終了後虚脱していると、色々と話があったりして、隣の会場へと誘導されました。そこでは、スポンサーの方のお話や、英語による問題解説などがありましたが、コンテストの疲れで完全に寝落ちしてしまっていました。
目が醒めると順位発表でした。ICPCの順位は、コンテスト中も順位表で確認できるのですが、終了30分前くらいに凍結して、更新されなくなります。その30分間で提出されたものの結果をYes/Noと言われる読み上げ形式で発表していって、最終順位が確定するというパフォーマンスがあるのですが、それで大いに盛り上がりました。一位のチームが、最後のところで誰も通していない問題を通していたりしてかっこよかったです。
それが終わると、元の会場に戻って写真撮影をして、懇親会が始まりました。企業賞の発表が前であったのですが、その間に企業ブースを回るという裏技を使って、Tシャツやステッカー、ファイルなど色々なノベルティを獲得していました。
乾杯をして立食パーティーが始まります。JAGで同室だった、こるとんさんやニクローさん、xxxkiritoxxxさん。今度行く予定のマニラ大会に同じく参加される東工大のチームmickythetaの方達。スタッフとして働いていた同級生。など色々な人たちと話せました。
あと、企業ブースでボンバーマンみたいなゲームをしたり、ボードゲームのガイスターをしたり、数独にチャレンジしようとしたり、なかなかに楽しみました。
最後の方で、Googleのブースに行って、入力と出力が与えられるので問題を推測しろという問題に取り組みました。この入出力のセットがいっぱいあって、人によって与えられるものが違うので、いっぱい会場を歩いて情報を交換しながら解こう！ という交流に向いたいい問題に思えました。入力は明らかに入力が有向グラフな上、会場の机に放置されている問題用紙にも有向グラフがことごとく書かれていたので、まあそういう感じの問題なんだろうなと、何人かで集まって解いていたのですが、全然わかりません。ウンウン悩んでいると、一人のすでに解いた方が現れて耳元で「それはひどい問題だよ」と呟きました。それを聞いて一人が何かに気づいたようで、その解法でみんなの入出力セットを確認すると、それでした。
Googleブースに行って答えを言うと、おめでとうと言われました。ひどい問題です。
後ろの方に強い方がいてその方もこの問題を解いていたのですが、全然わからないようで、すでに解けている人たちがオラクルをやってあげては、えー意味がわからない、と言うみたいなことをやっていて、上位のコーダーの人たちも人間なんだなと思いながら見ていました。
そんな感じでワイワイと交流を満喫しているとおひらきになりました。
皆に別れを告げて、ゆっくりと電車に揺られながら、次の日の中間テストの教科書を開きました。ICPCに集中していたので何一つ勉強していなかったので、１ページ目からスタートです……。
終わって
ICPC終わってしまいました。実はまだマニラ大会に行くつもりなのであれですが、予選通れるかどうかと言う感じで始まって、ここまで来れたのはよかったなと思います。
来年もこの場に来て、今度は今年以上の成績を残せたらいいなと漠然と思います。
まとまりのない文章ですが、そんな感じで楽しい二日間でした。
3日目 11/18(月)
ICPC三日目は、実は企業見学があります。でも平日月曜なのでね、授業はありますよ。中間テストもありましたよ。さすがに行けませんでした。ziroppeくんは月曜に授業があんまりないらしく企業見学参加したらしいです。水族館行きたかったな。
第4回 Asprova プログラミングコンテスト
2019/08/23~08/30にAtCoder上で開催されたマラソン型のプログラミングコンテスト『第4回Asprovaプログラミングコンテスト』に参加しました。
焼きなまし法が初めて成功して嬉しかったのと、ツカモさんにこう言われたので、記事を書いてみることにしました。
恐縮です…。
— ツカモ (@tsukammo) August 30, 2019
さぁ、ろいさんもブログ記事を書いて競プロ後継者erの糧となるのです！
ということで、この記事は、自分(Roy_R)がコンテスト期間中にやったことを時系列にまとめて、他の人の役に立つといいなっていうのとともに、マラソンマッチ楽しい！ と主張するものです。(あと、自分の復習のため)
やったことを簡潔に列挙するのが本当はいいのかもしれませんが、このブログのタイトルは『競プロ日記』ですし、僕は日記調の文章しか書けないので、日記的な感じで考えたこととかやったことを書いていきます。読み物として読んでください。
(一応、やったことを適当にまとめたものを一番下に書いたので、それだけ読みたい方は一番下へ) すみません、暇な時に追記します。
ちなみに僕のマラソンマッチの経験は、2nd Asprovaと第三回日本橋ハーフマラソンの二回だと思います。どちらも乱択解以上の点数を出せずに終わった初心者です。
(マラソンマッチ自体の説明は、ツカモさんの以下の記事とかを見るといいと思います)
また想定読者は、競プロはやっているけれど、マラソンマッチはやったことないという人になるのかなーと思います。
問題概要
まずは問題のリンクを以下に貼ります。
ただ、問題文が非常に長いので、概要を述べます。
『工場の良い生産スケジュールを作成してください。具体的には、M台の機械が与えられ、R個の生産オーダ(注文)が与えられます。オーダには品目、数量、最早開始時刻、納期、粗利金額、納期遅れ許容時間などのパラメータがあり、また、各機械である品目を生産しようとした時の生産速度などのパラメータをまとめたBOMという情報が与えられます。ある機械で生産する品目を取り替える時、段取り時間が発生し、同時に段取り時間ペナルティ金額が発生すること、また、納期に遅れるたびに納期遅れペナルティ金額が発生することに注意しながら、得られる利益を最大化してください』
だいたいこんな感じです。
いわゆるスケジューリング問題ってやつですね。
具体的には下に貼った画像を見てもらうと少しわかりやすいかもしれないです。(これは後で紹介するヴィジュアライザで生成されたものです)
(このコンテストの主催企業であるAsprovaさんはこういった生産スケジュールを解決する生産スケジューラを製作している企業だそうです)
ところで突然ですが、僕はこの問題文を自動車教習所の寮で見ました。
そうです。今、自動車免許合宿に来ているところなのです。なので空き時間が有り余っており、長時間コンテストに参加するにはうってつけです。さらに、前々回の2ndAsprovaコンテストに参加していたのですが、その時の問題と割と問題設定が似通っていて、とっつきやすい感じがしました。よって、読んですぐにフルで参加しようと決めました。
情報収拾
現代戦では情報を制するものが戦いを制します。多分、孫子か誰かもそんな感じのことを言っているはずです。なのでとりあえず周辺情報を集めました。
まず先に述べた通り、今回のコンテストは前々回のコンテストと良く似通っています。少し得点の与え方や納期遅れに対する扱いなどが違いますが、ほとんど同じです。多分。最大の違いは、一つのオーダが一工程で終わるか否かですかね。今回のは全部一工程で終わります。つまりは、前々回の問題の制約が緩和されたバージョンに見えました。よって、前々回の解答を参考にするのはある程度有益でしょう。
色々調べてみると、6位のkojimaさんの以下の記事や、
表彰式を見に行ったnekomimimiさんによる上位の人の解説(以下参照)や、
1位の人が、Greedyの後に作業を割り付ける順序を一点入れ替えてGreedyをし直して山登りする話をしてたがかなり状態が変化するようで、近傍が大きければ山登りでも谷を乗り越えられると言うことで、なるほどと思った pic.twitter.com/Sd2boJl4nA
— ねこみみみ (@nekomimimi) January 11, 2019
1位だったts_さんのtwitterでの以下のような発言を見つけました。
Asprova 2nd コンテストは運良く1位
— ts (@ts_77777) January 15, 2019
やったことは（公開承諾済み）
1. orderを納期順にソートしてorderの優先順位付け
2. 段取り終了時刻t2が一番早いoperationを探索して逐次割り当て解を構築（複数候補がある場合は優先順位順）
↓
以上を総合すると山登り法か焼きなまし法(マラソンマッチにおける超有名アルゴリズム)かなという感じです。
型にはめてとらえるのは良くないと、chokudaiさんもおっしゃっている(以下記事参照)ので、あまり固執しないように、でもこれらの解法を念頭に置いておきます。
また、ある制約下においてはスケジューリング問題は厳密に解けます。
下はABC131DのMegalomaniaという問題です。このような問題の場合、納期が早いものから順に仕事をこなすのが、全体の終了時間を最も早くします。
この知識も重要な気がしたので確認しました。
また、下のようなthereecourseさんのマラソンマッチについての有益なリンクなどを見つけたりしました。
とりあえず提出
ありがたいことに、今回の問題にはいくつかのおまけがついています。サンプルコード、ヴィジュアライザ、テストケースジェネレータ、得点チェッカーなどです。
問題に出てくる変数が非常に多くて、読み込んだり解答を出力したりするのが面倒なのですが、サンプルコードを使えばその辺りをよしなにしてくれて嬉しいです。
サンプルコードのやっていることを読みます。全てのオーダを最早開始時刻でsortして、機械番号が若いものにどんどんと詰め込んでいく貪欲解法でした。とりあえずそのままのコードを提出してみます。172204165516点が得られます。普段のAtCoderのコンテストではまず得られないほどの大量得点に喜びます。わーい！
(桁数が多くて読みづらいので、以降は1722億点という形で切り捨てて表します)
さて、サンプルコードの解答は本当にサンプルという感じで、いくらでも改善できそうです。とりあえず、最早開始時刻によるsortではなく、納期によるsortに変えてみましょう。上の厳密に解く方法を利用してみたのです。しかし、得られた得点は1698億点で下がってしまいました。出鼻をくじかれてしまいましたが、これは考えてみれば当然で、上の解析的なスケジューリングの解は、開始時刻の制限がないときのものでした。今回には必ずしも適用できません。
この方針はとりあえずおいておいて、次に考えたのは他の機械も使うことです。サンプルではほとんど一つの機械しか使っていません。これではダメなのは自明です。負担は分散させるべきです。よって、最早開始時刻でsortした後に、どの機械に割りつけるといいかも調べて貪欲に割り付けていくことを考えました。これで提出してみると2882億点が得られました。1000億点も増えました。嬉しいです。
次に、sortの部分をちょっといじってみることを再び考えました。ここで納期でsortしてみたり、納期+納期遅れ許容時間でsortしてみたり色々試してみたところ、納期+納期遅れ許容時間でsortするのが2910億点が得られていい感じでした。
実験する
さて、こうやって色々な要素を動かしてあれこれ試していたわけですが、AtCoderの提出欄に提出すると、提出制限でそれから一時間は提出できなくなってしまいます。つまり、試行錯誤が一時間に一回しかできないのです。これは不便です。
ここで考えるのが、手元に実行環境を作ることです。幸いにも、サンプルコードと一緒にテストケースジェネレータも付いています。これで大量の入力データを作ってプログラムを走らせれば、手元でどれくらい改善されたかがわかります。
しかし、当然それを手動でやっていては時間ばかりかかり、それこそ意味がありません。自動化させましょう。シェルスクリプトです。僕の環境はMacBook Airのターミナルなので、シェルスクリプトを上手く使えば、色々上手くできるはずです。全然シェルスクリプトなんて触ったことありませんでしたが、これを機にちょっとやってみました。
この辺りは、以下のhama_duさんの記事の『テストする』の項を参考にさせていただきました。
以下の記事でコルンさんがおっしゃっているように、手元の入力データに対する過剰な最適化に陥らないために、テストケースは十分多くとる必要があります。(1000件くらいいるっぽい？)
けれど、一つのテストケースに10秒かけているので、それを1000件もテストしていては、素早く結果を得ることはできません。どうやら、頑張る人は最近話題のAWSとかクラウド上の並列計算のサービスに投げてこれをササっと計算させたりするらしいですが、僕は流石にそこまではできないので、30件のテストケースだけで全部を評価しちゃうことにしました。ある程度有意に点数が上昇していればいいでしょ、と雑に考えました。正確さよりも素早いフィードバックが欲しかった、なんて言うとなんだかそれっぽいコメントです。
順位表を見る
さて、手元にある程度のテスト環境が構築できたところで、順位表を少し眺めてみます。これです。
この時点で1位の人の得点は3001億2000万点くらいで、2位の人も3001億点くらいでした。現在の自分の得点が2910億点なので、また100億点も上昇すれば1位です！ でも、それは難しいでしょう。強い人は本当に強いので。それに上位が3001億あたりにまとまっているなら、そのあたりに上限があると言うことなので。つまり、ここから得られる情報は、この先の改善は100億点のオーダではなく、10億点とか上がったら十分よい改善だったのだなと言うことでしょう。このように順位表を見ても色々と情報を得られます。
あと、単純に順位表を見ると楽しいです。この時の自分の順位が21位くらいで、順位表を見ていると、上に行ってやるぞ！ というモチベーションが湧きました。
過去を参考にする
やっぱり今回の問題は2nd Asprovaのコンテストに良く似通っています。その時の解法が一部流用できるのではないでしょうか。そのままは使えなくとも、ある程度は参考になるのでは？ そう思って、上に載せたts_さんの解法を考察しました。
焼きなまし法の部分はおいておいて、初期解を構築する部分だけをまずは考えて、それを実際に今回の問題で実装してみました。手元のテストでいい感じの点が出ました。提出してみると、2981億点が出ました。70億点もの改善です。喜びます。
でも、なんで上手く行ったのでしょう。考えてみると当然で、今までは割り付けるオーダーを決めてから、一番上手くいく機械を選ぶ貪欲でしたが、今回は、どのオーダーをどの機械でやると一番上手くいくかを考える貪欲になっていて、貪欲で見る解の候補が増えているのです。
さらに微妙なマイナーチェンジを手元でいくつか試して、上手く行ったのを提出してみると2988億点まで伸びます。着々と改善していっている感じがあって非常に楽しいです。
この改善は、自分でも気づけかったわけではないと思いますが、なんらかの前例があるならそれを参考にしてみることで、自分の考察を強化できてよいと僕は思います。たとえば強い人は、その問題に関係する実際の論文などに目を通したりすることもあるらしいです。
ところで、ここで一つ問題が生じます。
実はこの次の日、合宿免許の仮免試験があったのです。しかしマラソンマッチにかまけていて、学科の勉強にあまり手がつけられていませんでした。ネット上で運転免許の学科試験は論理的におかしかったりして、解くのが難しいみたいな話を聞いたことがあったので、夕方を過ぎた頃に流石に慌てて過去問題集を開きました。ただ数年分解いてみると意外と簡単で、ちょっと独特な感じはありますが、慣れたらなんてことはない感じでした。過去問を解くのは大事だなと思いました。
この節のまとめは過去を参考にするのは大切だなと言うことです。
逐次評価する
さて、仮免試験当日です。まずは実技試験。バスに乗せられて練習コースの横にある待合室に通されます。しばらくすると名前を呼ばれて車に乗り込みました。後ろに次の試験の人も乗り込んで来ます。緊張します。けれど、何度も練習したコースをいつも通りに進むだけです。後方に車が来ていないことを確認しウィンカーを出して走り出します。
緊張で肩が上がりながらも、いつも通り進みます。だんだんとリラックスできた頃、S字に差し掛かりました。難関と言われる箇所ですが、練習ではスムーズに行けていたので、何も考えずに進みます。途中まで非常にスムーズに曲がれます。と、後輪に衝撃がありました。よく見ると、いつもよりもカーブの内側に寄ってしまっていました。内輪差で内側の縁石にぶつかってしまったのです。教官に言われたことを思い出します。S字などでは、しっかりと曲がるところを見て、適切な距離が取れているかを逐次確認しながら、カーブに沿うように細かくハンドル操作するべきなのです。
そうです。闇雲にこちらの方が正しそうだからと思い込みで突き進んでいてはいけません。逆に、今どんな状況であるかを逐次確認しながらであれば、前に進んでいけるのです。プログラムもきっと同じです。解答の一部を変えてみて、それで得点が良くなるかを見ていけば、よりよい方向に進んでいけるはずなのです。なので、今現在の得られる得点(利益)が幾つなのかをプログラム内で調べられる関数があると嬉しいです。
そしてこれは実は簡単に実装できます。なんと得点チェッカーのソースコードがダウンロードしたファイルについているので、それをちょちょちょっと弄ってやって適当にコピペすると、あっという間に完成です。
仮免試験は実技で上記のような危ない部分がありましたが、問題なく合格できたので、昼食後にこの得点をチェックする関数をパパッと完成させます。そして、隣接する二つの注文の順番をランダムに入れ替えてみては、上手く行けばその入れ替えを採用するというようなことを行いました。カーブを曲がりながら、しっかり目視で偏りを確認してハンドルを修正するようなものです。このように、少しづつ要素を変更しながら(『近傍を見る』みたいにも言う)、点数が改善すればその変更を採用する、ということを時間いっぱい繰り返す方法を一般に山登り法といいます。山の頂上を目指して、一歩づつ高い方向に向かって動いていこうとするイメージです。
この山登り法のコードを提出してみると、2988億点でした。
……あれ？
いや、山登り法をしないときと比べると800万点くらいは改善しているのですが、正直言って微妙です。
asprova、3000億点目指したいな
— ろい (@Roy_R_) 2019年8月26日
この調子では3000億点には届きそうにないですよ。
ヴィジュアライザ
さて、何が良くないのでしょうか。改善する方向に動き続ければ、必ずより良いスケジュールが出来上がるはずです。そこで、ダウンロードしたファイルに入っていたヴィジュアライザを使って自分の解答を見てみます。
(緑色の部分が段取り時間で、その他の色の部分が個々のオーダ(注文)です。またビックリマークが上に付いているのは納期に間に合っていないオーダです)
なるほど。綺麗に視覚化されていて楽しいですね。いくつも試してみて、それを見ているだけで飽きないです。でも、なんとなく改善できそうなところがあることに気づきます。例えば先頭の方で、オレンジの品目の塊、黄色の品目の塊、オレンジの品目の塊、と品目が交互に生産されていますが、これは品目を入れ替えるための段取り時間が発生して無駄です。
こういう感じで、品目をまとめてやると良いような気がします。
けれど、今の方法ではこういった変化はほとんど起きません。
理由は簡単です。
『橙橙橙黄黄黄橙橙橙』
から
『橙橙橙橙橙橙黄黄黄』
に変えるためには、オレンジと黄色がより入り混じった状況
『橙橙橙黄黄橙黄橙橙』など
を経由せねばならず、そのような状態は概して点数が悪くなります(製品を入れ替えるたびに段取り時間が発生するので)。つまりより大きな山に登るために一度谷に降りなければいけないのです。
焼きなまし法
では、発想を転換し、その谷(点数が悪くなる方向)にも進んでみてはどうでしょうか。高い方にばかり行くのではなく、一時的には悪くなりますが、いずれ良いところに行けると信じて低い方にも確率的に移動してみるのです。これがいわゆる焼きなまし法の基本的な考え方です。
実際には低い方向に行く確率を、温度と言われるパラメータで管理して、徐々に点数が低い方向にはいかないようにしたりします。これが鉄を精錬する時に、だんだん冷えて動かなくなっていくところに似ているので、焼きなまし法と呼ばれるわけです。
マラソンマッチではよくこの焼きなまし法が使われ、chokudaiさんによれば、アルゴリズム部門におけるDPみたいな存在だそうです。(多分そういう意味ですよね)
「マラソンって大体焼きなましだよね」と「AtCoderって大体DPだよね」はほぼ等価
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) February 11, 2019
前回、前々回のマラソンマッチ参加時にもこれを実装しようとして、結局できなかった苦い思い出があります。けれど、焼きなましができなければこれから戦っていけないでしょう。そう思って色々と先人の方達の焼きなまし法についての記事を読み漁りました。
中でも、以下の診断人さんの記事が実装面についてもわかりやすく、記事内のコードを参考にさせてもらいつつ焼きなまし法を実装しました。
すると、前回までが嘘みたいに上手く実装ができました。手元のテストでも改善されていることを確認して、提出です。一気に2993億点まで伸びました。5億点の改善です。焼きなまし法が初めて成功し、ガッツポーズをしました。すごく嬉しかったです。
ところで、焼きなまし法はできる限りループを繰り返した方が点数が伸びるので、ある程度、高速化をするのが有効らしいですが、関数に対してvectorを渡す時に、 (vector<int>& x)の参照渡しか (vector<int> x)の渡し方かでは、後者が122986回程度に対して 前者が182401回程度のループ回数と有意に速度差が出てきたりとか、rand()関数は遅いだとか、C++に関するいろいろなことが知れて、へーと思いました。いつも競プロをする時はbetterCとして適当にしか使っていないのですが、こう言う時は、C++の別の側面を見られるなーなどと思いました。
寝ながら焼く
焼きなまし法が完成しましたが、2993億点で、3000億点には届きませんでした。焼きなましは、いっぱいループを回すとより良い解ができるはずです。10秒という実行時間の制限があるから3000億点に届かなかったのでしょうか。もしそうなら、どうにかしてプログラム自体を高速化してやる必要があります。でも本当に高速化が必要なのでしょうか？ わかりません。
なら、実際にいっぱいループを回してみましょう。具体的には寝ている間、7時間くらい。ということで、時間制限を7時間くらいに再設定してプログラムを走らせました。このとき、得点の遷移も知りたいので、その時々の点数をエラー出力するようにしておきます。
音を上げながら計算をするMacBook Airを横目にベットに入りました。寝ている間にコンピュータに仕事をさせておくと言うのは、なんだかIT技術を使いこなしている感じがして楽しいです。7時間ですよ。いったいどれだけすごい点数が出るでしょうか。ワクワクしながら眠りました。
ルンルン気分で目を覚まして、結果を見ようとパソコンを開きます。エラー出力を書き出したファイルを開こうとすると、しかし、vimで開こうとしたにも関わらず、ひどく重くて、vimを強制終了せざるを得ませんでした。仕方がないので、大学の春の授業で使ったgnuplotで間引きながら点数変化の推移をプロットしてもらいました。それが以下です。
また、その時点での最高点をプロットしたものが以下です。
こういうグラフは見ているだけで非常にワクワクするのですが、これから読み取れるのは、ループのはじめの方でほとんど点数は頭打ちになってしまっていると言うことです。色々考えてみると、実際の制限時間の10秒以内にはほとんど最大のところまで得点が上昇していることがわかります。
残念です。
このように頭打ちになってしまっては、どんなに計算を高速化してループを繰り返しても3000億点には辿り着けません。
では、なぜ頭打ちになってしまったのでしょうか。
探索空間と解空間
焼きなまし法では、小さな変更をいっぱい加えてどんどんと新しい解を作っていくことを繰り返します。こうやって操作を繰り返して構成され得る解の候補の集合を探索空間と言ったりします。焼きなまし法や山登り法では、この探索空間の中を彷徨って、一番良い点数となる場所を探すようなイメージです。
また、問題の答えとしてあり得るすべての解の集合を解空間と言います。今回の問題で言えば、どの機械でどの順番にオーダ(注文)を処理していくかの組み合わせがそれに当たります。この組み合わせは、例えば機械が一つだけでオーダが200個だけだとしても、200!=10^370くらいになって、とても広大です。だからこそ、厳密な最適解が求められずに、焼きなまし法や山登り法といったいわゆるヒューリスティックな解法を使って、より良い解を求めようとするわけです。
さて、この探索空間と解空間なんですが、よく考えると今のままでは二つが乖離していることがわかります。隣り合う二つのオーダを入れ替えるだけでは、あるオーダについて他の機械で生産するという可能性を無視しているのです。
これでは、限定された探索空間における良い解が求められるだけで、必ずしも実際の解空間の中においての良い解は求められません。
もちろん、探索空間が解空間の中でも優秀な部分集合であれば、そのような探索空間だけを見るだけでもいいと思いますが、今回はあるオーダに対して機械を固定化することにメリットは何もありません。
これを無理やり自動車学校でたとえるなら、教習コースという探索空間をぐるぐると回っている間は、S字が一番難しいところだと思っていたけれど、より広い公道という実際の解空間に出ていったら、もっと難しいところはいっぱいあるよね、みたいな感じですかね。すごく無理やり感あるたとえですけど。(ということで、仮免許が発行されたのでこの頃から公道を走る練習が始まっていました。いきなり公道走ってくださいとなったので、結構ドギマギしながらやっていました)
さて、このことに気づいたので、すぐに焼きなましの、『要素を少し変更する(近傍を見る)』部分に新しく『ランダムに選んだオーダを別のランダムな機械に割り当て直す』といったものを追加しました。
途中、vectorのiteratorのミスで配列外参照してしまっていたり酷いバグに悩まされますが、
— ろい (@Roy_R_) August 27, 2019
寮の消灯時間までになんとか実装ができました。手元の環境で実行しても良さそうな結果が得られたので、実際に提出してみると、2995億点が出ました。2億点の改善です。いいですね！ 着実に3000億点に向かっています！ ですが、まだ何かが足りないようです。
より良い探索空間
『橙橙橙黄黄黄橙橙橙』
から
『橙橙橙橙橙橙黄黄黄』
に変わってくれると嬉しいよね、という話を思い出します。
これを、隣接する二つを入れ替える近傍(小さな変更)を使って達成するには、得点が低くなってしまう
『橙橙橙黄黄橙黄橙橙』など
の状態を経由しなければならなくて、だから焼きなまし法を使ったのでした。
けれど、別にこのような得点が低い状態を経由しないで、直接変化させればいいんじゃないですか？ というのを思いつきます。
つまり、同じ品目のオーダ(注文)をまとめて移動させるのです。
『橙橙橙黄黄黄橙橙橙』
から
『黄黄黄』
を検出して、
『橙橙橙橙橙橙黄黄黄』
になるよう移動させるのを近傍とするということです。
これは下のツカモさんの記事でいう状態空間(探索空間)をなだらかにするということに相当すると思います。
ツカモさんの記事内の図を参考に、頑張って図にしてみるとこんな感じです。
これが元々の探索空間です。左の山から一番右の良いところに行くためには、一度真ん中の谷を経由します。
そして、新しい探索空間は次の図です。谷の部分をカットしました。
左の山と右の山が、近傍としてくっついてくれました。これなら山登り法でも右に遷移することができます(図が下手なのでちょっと谷ができていますが、気にしないでください)。このように良い近傍を取ることによって、探索がしやすい探索空間を構築できるのです。
考えてみれば、元々の解空間には近傍(近い解)なんていう概念は存在していません。図中の『状態』なんていう軸は存在していないのです。そこに人間が、この状態とこの状態は似通っていて、こっちの状態が良いなら、この変換をした状態も同じくらい良いだろうと、そういった問題固有の考察を与えてやることによって、探索可能な探索空間ができあがるのです。
(たとえ隣接二点swapとか一点ランダム変化みたいな自明っぽい近傍でも、それは人間が導入した概念であるということは念頭におくべきなのかなって思います)
今回の場合で言えば、
『橙橙橙黄黄黄橙橙橙』
と
『橙橙橙橙橙橙黄黄黄』
の良さは、そんなに変わらないけれど、黄色が後ろに行った分だけ段取り時間が少し減って、ちょっといいだろう。だからこの二つは近傍とみなせるだろうということです。
なぜか朝5時に目が覚めてしまったので、朝食までにこの3つ目の近傍をカリカリと実装していきます。同じ品目の連続を判定したりするところがまた配列外参照を起こしたりしてバグまみれになりますが、なんとかデバッグをすませると、完成したのは8時10分くらいでした。朝食が8時半までなので、AtCoderに提出だけ済ませると、慌てて食堂に行きました。
バイキング形式の朝食を美味しくいただくと、食後のお茶を飲みながらスマホでさっき提出したコードの結果を見ます。
3000億！ pic.twitter.com/xpdVih5iZz
— ろい (@Roy_R_) August 27, 2019
ついに、3000億点を突破しました！！！ やりましたよ！！
山を登っていく
この日は、3000億点を出した後、自動車学校の学科の授業がたくさん入っていたので、あまり本格的な改良はできません。けれど、せっかく一時間に一度AtCoderに提出できるのです。休み時間中に、近傍の確率や焼きなましの温度を色々といじって提出してみました。
はじめの温度をもっと高くした方が良さそうだ、とか。そうやってマイナーチェンジを施しながら、点数が改善されたらその変更を採用するということをやっていきます。やりながら、これはまさに山登り法と一緒だなと思いました。焼きなまし法や山登り法と行ったヒューリスティックな解法は、人間が実際の問題に対して試行錯誤しながら解決していく様に非常によく似ていて、そこがマラソンマッチの一つの楽しみかもしれないな、などと考えます。
時には、変更を加えてみた結果、悪い結果に行き着く時もありますが、
コードが肥大化するとバグが増えて辛い。書き直すか？
— ろい (@Roy_R_) August 28, 2019
そのような谷を抜けた先により良い結果が待っていたりして、これは焼きなまし法みたいですね。
起きて少ししたらバグが取れたので睡眠は大事
— ろい (@Roy_R_) August 29, 2019
さて、いつの間にか、8月29日です。路上教習も慣れてきて、法定速度に合わせてしっかりと運転できるようになってきました。そして、Asprovaコンテストも残すところあと24時間くらいになりました。8月30日までと言っても、朝10時までなので、実質今日が最終日です。
さて、asprovaもラストスパートだ。3001億台に乗りたいな。
— ろい (@Roy_R_) August 29, 2019
3001億点を目標に据えて最後まで頑張っていきます。
こういったヴィジュアライザの結果を眺めたりして、例えばこの一番上の機械真ん中あたりの黄緑色のオーダ(注文)はその一つ下の機械の黄緑色のオーダと合わせた方が良くないか？ などと考えて、別の機械にオーダを動かす近傍を、同じ品目のオーダをめがけて動かす確率が高くなるようにしたり、同じ品目をまとめて別の機械に動かしたり、あるいは、同じ品目が並んでいるところで、納期を使ってsortしたり(これは冒頭の方で述べた厳密な解を作るアルゴリズムを参考にした)とか、いろいろなことを試してみました。
あまりにも色々な要素を追加しすぎたために、どれの影響で点数が上がっているのかはわからなくなってしまっていましたが、それでも着実に点数が上がっていました。
けれど、3001億点にはもう少しで届きません。本当は良くないのですが徹夜することに決めてしまいました。
深夜テンションで色々なことを試してみました。コードをみると保守性も何もあったもんじゃなく、まるでハウルの動く城みたいな継ぎ接ぎだらけの見栄えが悪いものですが、だんだんと点数が上がっていきました。
近傍が6つもできていた頃には5時を回り、点数は3000億9000万点くらいになっていました。しかし、それからがなかなか上がりません。
もう一度ヴィジュアライザで自分の解答を見てみます。
気になる部分がありました。上の画像の部分の一番右の青いオーダは明らかにもう一つ下の機械の一番後ろにつけるのが良さそうです。よくみると、他にもこのような状態になっている場所がいくつかありました。多分、移動するのを選択する時にvectorの最後の要素を見てなかったのでしょう。こういったバグにも気づけるのでヴィジュアライザはありがたいです。ただ、どこでそれが発生しているのかわからなかったので、これを解消できるようにと、他の機械の一番後ろにオーダを移動させるといった近傍を用意したりしてしまいました。
他にも色々な、良さそうな改良を付け加えていると、いつの間にか朝日は昇り、8時を過ぎていました。これから朝ごはんを食べたら、すぐに複数人の路上運転実習があります。これが最後の提出になるでしょう。
祈りながら提出すると、部屋を後にし、食堂に向かいました。
今日も美味しい朝ごはんをいただき、食後のお茶を飲みます。そして、おもむろにスマホを取り出すと、AtCoderのサイトにアクセスします。スマホなので、得点部分が見切れていて、何点取れているかわかりません。
徐々に左にスライドさせていきます。
300...
3001億点！！！ pic.twitter.com/jGQo5F2BBc
— ろい (@Roy_R_) August 29, 2019
やりました！ ついに3001億点を超えました！！！
喜びのまま複数人での路上教習に挑みます。
二時間かけて、山に登って降ります。途中でつづら折りがあったり、霧が出ていたりして、なかなか簡単にはいかない道のりでしたが、三人で運転を交代しながら、ついには目的地としていた道の駅にたどり着きました。
そこで、同じの車に乗っていた他の二人と一緒にソフトクリームを買って食べました。何かをやり遂げた後の感慨深さというか、なんというかで、非常に美味しく感じられました。
(ちなみに、この道の駅でスマホからちょっとパラメータを弄って10時5分前くらいにえいやっと投げてみたら、3000億9000万点くらいで、そっか……となりました)
まとめとか感想的な何か
運転免許合宿で暇な時間を非常に有意義なことに使わせてもらえて、Asprovaコンテストには感謝しています。また、この一週間で色々なことが学べた上、色々な一喜一憂ができて、非常に楽しかったです。このような楽しいマラソンマッチという競技を他の方達もぜひ知ってもらって、みんなやってくれるといいなーと思います。
僕は、乱択解くらいしかできなかったマラソンマッチ初心者でしたが、色々な先人の方の知恵をお借りすることで、なんとか焼きなまし法を理解し、使うことができるようになりました(Asprovaコンテスト終了の次の日に突然現れたchokudai contest 004という2時間のマラソンマッチにおいて、焼きなまし法を使うことができたのがその証拠です)。本当にありがとうございます。そして、この記事が他のマラソンマッチを始めてみようかな、と思っている方の一助になれば幸いに思います。
あと……
そういえばまだ、運転免許取れてないです。まだ合宿中です。明後日くらいに卒業試験があるので、そちらも頑張っていきます。
ICPC2019国内予選 参加記
ICPC国内予選にチームchoKOdaiで参加しました。
3完(7897)で全体85位、学内3位でした。
これは普通だと予選突破できないのですが、慶應義塾大学は今年の†ホスト校†だったので、チーム選抜ルールの手順2が適用されて予選突破になりました。
チームについて
去年のICPCと同じメンバーで、ziroppeくんとspiderさんと僕の三人のチームです。atcoderの色は参加時点では緑緑水でした。
チーム名について
去年のICPCアジア横浜大会中継動画(ACM-ICPC 2018 アジア地区横浜大会 中継 - YouTube)の4:52:40頃にchokudaiさんが慶應からもchokudaiという名前のチームが出てきたらいいのにとおっしゃっていたのを聞いて、去年の冬くらいから温めていた名前です。チーム名決めのときに案として出してみたら概ね好評だったので決まりました。
(ところで、chokudaiさん本人に気づいて応援していただけました。わーい！)
ICPCはとりあえずこのチームを応援します pic.twitter.com/l5P0aveGjJ
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年6月28日
作戦
目的を国内予選突破に定め、そのための目標として、3完早解き、そして4問目をなんとか解く、ということを掲げました。ともかく3つを素早く通すためにチームで早解きの練習を何回か繰り返しました。spiderさんは忙しくて練習に合流できないこともあったので、僕とziroppeくんで早解きの部分をやって後ろの問題をspiderさんに見てもらうという形がだんだん固まっていきました。
本番前のいろいろ
模擬国内出ました。ABC3完で、Dのレーベンシュタイン解きたかったです。
キーボードの使い分けが禁止なことに気づきました。ziroppeくんがUSキーボードで他二人がJISだったので困りました。色々相談した結果、JISを使うことになり、ziroppeくんはJISでプログラミングをする練習をしてくれました。ありがたい。
本番前日
学内で模擬コンテストがありました。本番と同じ会場でプリンタなどの機械の使い方含めてリハーサルをしました。
問題は上のリンクで、これのC、Unordered Operators(構文解析の問題)が解けなかったので22時くらいまで学内に残ってチームで解いていました。その後なんとか二通りの方法でACできたので、みんなでハマトラに行ってラーメンを食べ、帰り際、駅前で本番の流れや、残りの時間でできることを話し合いました。今までチームで書いたプログラムで使えそうなのを印刷しておこうとか。いろいろ話していると流石に遅くなったので解散。家に帰ると0時くらいで、そこからネットを漁って使えそうなライブラリを印刷する作業をしましたが、途中で前日の徹夜がたたって眠くなって、寝てしまいました。
本番当日
以下、当日の終了後、深夜3時過ぎに書きなぐった駄文をそのままコピペします。
目が覚めたら8時で、朝ごはんもそこそこに急いで大学に向かった。1,2限は化学の実験で、銅イオンの溶液を振っていた。昼食を取った後に矢上キャンパスに向かって、ziroppeくんと合流。互いに前日夜に用意してきたライブラリについて互いに報告しあって、そのあとリハーサルの問題を解く。4問目の幾何はリハーサルにしては難しいなと思いながらも、方針は立って、あとはziroppeくんの持ってきた螺旋本の幾何の部分を使えばなんとかなりそうだなという感じで、その頃には4限の授業が始まる時刻が迫っていたので、別れて授業へ。ziroppeくんは授業がないらしくてメディアへC++の辞書的なのを借りに行ってくれていた。4限はプログラミングの授業。演習やるだけの日だったので、課題として与えられた4問を適当に40分くらいで解いて早退。gcdとlcmを求めろみたいなのがあったりして、競プロやっててよかったと思った。
会場に向かうと、コンピュータの設定をやったり、他のチームの子達と雑談したり幾何についてziroppeくんと話したりしながらソワソワと過ごした。16時過ぎくらいにはspiderさんもやってきて、チーム全員が揃った。再びライブラリについて報告したり、初動の確認などをした。問題の印刷について、1問ずつ印刷するのはコンピュータを占有しすぎると考えて、全部まとまったページの方を印刷することにした。ziroppeくんがホッチキスを持ってきていて、spiderさんがハサミを持っていたので、それで問題ごとに切ってまとめようという話をした。色々そういう作業をしていると、3秒前くらいに「あ、はじまるね」みたいな感じでぬるっと本番が開始した。
まずは、ziroppeくんに印刷の処理をしてもらい、spiderさんにプリンタに向かってもらう。すぐにパソコンでA問題を見る。やるだけ。ziroppeくんに横で見てもらいながらプログラムを書き始める。サンプルが通る。提出する。AC。spiderさんも帰ってきていて、問題を切ってホッチキスしてもらって、そのままC以降の問題を見てもらっていた。
僕とziroppeくんでBを見る。マンハッタン距離を愚直に見ていけば良さそう。とりあえず書き始める。ある文字に対して座標を対応させれば良さそう。map使えばいいか。あれ？ サンプル見ると、同じ文字がいっぱい埋まってる？ いや、アンダーバーは文字でない場所。でも、複数の場所に文字があったら、めんどくさそうだぞ。BFSか？ でもB問題なら同一文字は複数ないという条件がありそう。二人で問題文を睨む。問題文中に記述があって、その場合は考えなくて良いとわかったので、プログラムを完成させる。サンプルが通る。提出する。通る。やったー。ここまで20分。
spiderさんに他の問題の大体の感じを聞く。Cは行けそうということなので、コンピュータの前を譲って、spiderさんがプログラムを書き始める。僕が横でそれを見る。ziroppeくんはD問題を見に行く。とりあえずCは、dfsで(3^10)通りの手持ちの分銅でできる重さは求められるねーとspiderさんが実装していく。けれど、そこから先が詰まる。悩む。
横でziroppeくんがDについて考察しているのが気になって、内容を聞きにいく。聞いてちょっと考えて、左から見ていけば行けそうと思って「行けます」とspiderさんに報告。まだCが詰まっていたようなので、代わってもらってDを書き始める。ちょっと迷いつつもziroppeくんに見てもらいながら書き終わる。サンプルを試す。値が違います。え？ コードを見るけどどこも間違ってなさそう。悩む。
「Cわかった」と横から聞こえてきたので、Dのコードを印刷して、spiderさんにコンピュータを渡す。ziroppeくんとspiderさんでCの実装を始める。僕はちょっと離れて印刷したコードを見ながらうんうん唸る。5分くらい見て、iと0を書き間違えていることに気づく。コンピュータ貸してもらって、書き換えてコンパイル。実行。値が違います。はい、もう一度考えます。
コンピュータをspiderさんたちに返す。僕はさらにうんうん唸る。バグじゃなくて何か間違ってるかもと思って、問題文にもう一度目を通す。あ……誤読。全然違う問題を考えていたことに気づく。一回の操作でできる行為を、『隣接する一連のカウンタを押す』ではなく、『隣接する3つのカウンタを押す』という感じに間違えていた。辛い。でも、気づけてよかったと思いながら、正しい問題について考える。え、これ難しい。
ちょっとCの様子を見にいくとバグっているみたい。とりあえずCを通さねばと思い、方針を教えてもらう。コードの内容を教えてもらいつつ考える。みんなでワイワイとやっているとみるみるバグが洗い出されていった。(この辺り、すごくチーム戦で楽しかった)サンプル通る。みんなで提出。通る。やったーと盛り上がる。ここまで大体1時間50分。
残りの問題を机に並べる。「どれいきましょう？」と考える。順位表を見てみると、D,Eあたりが通ってる。Eはこれやるだけだよなー、と。でも、E以降通しているチームは基本的にDは通してる。ならDをやるべきだろうとなって、みんなで考え始める。二人づつで話したり、一人で考えたり、蟻本開いてみたり、順位表見て学内でD解けてる人まだいないねと確認したり、みんなで顔を突き合わせたりしながら色々なことを考える。AtCoderでこんな感じのあったなーとか(https://atcoder.jp/contests/abc116/tasks/abc116_c)。DPじゃない？ (でもなにを[i][j]に入れます？ となってた)とか。でも、全然解けそうにないまま、残り40分くらいになってしまう。
方針を転換して僕はFに行く。パズルっぽい感じで、あと僕の好きなグラフなので、閃けば実装まで行けそうと思った。spiderさんはDを考え続けることに。ちょっと経ってコンピュータがずっと空いてもったいないので、ziroppeくんがEを実装することに。Eは言われた通り全列挙するだけなのは初期からわかっていたけれど、実装がすごく重そう。さらにしばらくして、ここから考察して実装まで持っていくのは無理そうと結論づけて、D,Fから撤退し、Eに三人のリソースを全て使うことに。けれど、あまりに重くて、結局時間切れ。
あっという間で密度の濃い三時間に「お疲れ様」と虚脱していると、他のチームの人から「予選通過じゃない？」と指摘される。
学内3位だというのはわかってて、でも通るのか？ と思いながら見てみると、†ホスト校†の力でなんとか通りそうとわかる。浮かれながら先生のお疲れ様の挨拶を聞いて、学内の記念撮影を終えると、手計算で予選通過かどうかを確かめてみることに。東大強いなーと上から順に順位表を見ていき、通過を確信する。すっごい浮かれる。ウキウキしたまま、チームメイトのみんなで夕飯を食べにいく。せっかくだからステーキ食べに行こうということになってステーキ食べた。
チームの二人と pic.twitter.com/VozyJk4toJ
— ろい (@Roy_R_) 2019年7月12日
美味しくいただきながら色々なことを話した。店を出ると、秋のアジア予選に向けて精進頑張りましょうと、鼓舞しあって別れた。空を見ると月の光冠が綺麗に見えて、エモい気持ちになりながら帰宅した。
反省や感想や意気込みとか
目標にしていた予選突破を果たせてよかったです。また、慶應の次のチームとの差がほんのわずかなペナ差だったので、ABあたりの早解きの練習が生きた感じがして、それもいい感じです。
ただ、Dは通せてもよかったかなーと思うし、Eの実装をもっと早く始める判断をしていれば行けたのではというのも考えなくはないです。
しかし何はともあれ、一緒に戦ってくれたチームメイトに感謝を。で、秋もあるということなのでこれからも一緒に頑張っていきましょう！
ところで、個人的にアジア予選の本番までには青になっていたいです。
