tardigradeの競プロ日記

マラソンコンテスト(プログラミング)について書きます

ICPC2024国内予選参加記

2024/07/05に開催されたICPC国内予選にチームHokkaidoDekkaidoで参加しました。

メンバーはTodayさん、koutyくん、僕(tardigrade)です。

結果から書くと、ABCDEの5完で44位でした。

コンテストが終わって打ち上げに行ってシャワーを浴びて、そのまま惰性でこの記事を書いてるので、ところどころ読みにくいところもあるかと思います。 後々こっそり修正するかもしれません。

～コンテスト前夜

チームが結成されたのは遅めの新歓を終えた5月の下旬で、国内予選まで残り一か月半を切っていました。

チーム練習はだいたい週1、多い時は週2で、基本的には国内予選のバチャに取り組みました。去年一昨年とICPCに出て今年が三年目ですが、今年が一番チーム練習の時間を取ったと思います。今年からライブラリが解禁になったことで、「コーディング環境をどうするか」「ライブラリを誰に合わせるか、どう調整するか」みたいなやり取りがかなり活発に行われて、こういう要素も面白いな～と感じました。

個人ではICPC Japan Problemsを埋めていて、特に構文解析・幾何は重点的に対策をしました。最近はボーダー付近に置かれなくなってきている印象ですが、今後はどうなるんでしょうか。

icpc-japan-problems.irrrrr.cc

あとは、国内予選用にJIS配列のキーボードを買いました。普段はUS配列のキーボードを使っているのですが、koutyくんがJIS配列だったので今回はそれに合わせました。

ちなみに、今後使う予定が無くてどうするか悩み。弟にでも送りつけようかな。

コンテスト前夜～コンテスト直前

前夜は、金曜日締め切りの課題をやっつけて、構文解析を一問通して、そのあとは5時間くらい友達と通話していました。メンタルがかなり整ってめちゃめちゃ良かった。超感謝。

11時くらいに起きて、14時ごろに大学に到着。かなり人が揃っていて、大会だ～という気持ちになった。

プリンターのチェックとか、環境の最終確認とか、色々をしているとあっという間にコンテスト開始時間に。

A問題

Todayさんと一緒に眺める。普段はTodayさんが一人で解いているのだけど、プリンターが詰まって若干手持ち無沙汰な時間があったのと、Todayさんが少し不安そうにしていた（緊張？）ので今日は一緒に解いた。

特に考察することもなくAC。

B問題

B問題はいつも僕の担当なのでB問題を見る。が、僕もド緊張するタイプなので頭が全然回らず、D問題に飛んで行ったTodayさんを呼び戻す。

一瞬「あれ？」となったけど、Todayさんに説明していく過程で自己解決してそのあとはスムーズに実装が進む。

Todayさんに眺めてもらいながら実装できたのでかなり安心感があり、無事AC。

C問題

あんまり見てない。koutyくんとTodayさんが2人で通してた。感謝。

D問題

2人がC問題を見ている間にD問題を読む。ループ検出したら解けるなぁと思っていたらCが通ってPCが空いたので、問題を読んでもらっている間に基本的な実装を始める。

「ループ検出で解けますよね？」みたいな話をしたら「ダブリングのほうが楽では？」と言われて、確かにそうかも～～～～～～と思った。

ダブリングで解けない場合（ループが発生しない場合）の処理をTodayさんが、ダブリングの部分をkoutyくんが書いてくれて、僕は実装のミスと注意が必要なケースを指摘する人になっていた。「繰り返し回転しないといけないパターンが怖いかも」とは問題を読んだ時からずっと思っていて、ちゃんとそれを実装中に指摘できたのは良かったけど、僕にもっと実装力があればもっとスムーズだったはずなので、うーん。

サンプルが通ったのでテストケースを実行するが、かなり重たい。mapを使ったのと、20万回くらい最初に愚直をしているので、ちょっとやばいか…みたいな空気が漂い始める。高速化できる部分を考えて、直すかぁ…と思っていたら3,4分で実行が終わってAC。よかった。

学内最速の4完ではなかったが、ペナ差で学内1位。まだ1時間も経っていない感じで、このあたりでようやく気持ちが落ち着き始める。

E問題

「先頭と終わりが違ったら"No"じゃない？」というギャグが生えたが、順位表を観察して流石に違うよねという話になる。checkerは比較的簡単に書けそうなのでTodayさんに担当してもらい、僕とkoutyくんはFもチラ見。

以降僕はずっとFにつきっきりで、E問題の内容は全然追えていません…。後の内容はざっくりとした立ち回りだけ。

koutyくんとTodayさんがめっちゃ頑張ってくれて、手元で作ったやばいケースとサンプルに対しては正しい解を返すようになる（残り1時間くらい？あんまり覚えていない）。

その後checkerに投げてみるも、checkerが壊れていることが判明してどうするか相談。いったん投げてみようで投げたらWA。

checkerのバグを直して、テストケースで壊れていた部分をめちゃめちゃ頑張って直して、AC。

Todayさん、koutyくん、ありがとう！！！！！！！！

F問題

考察だけまとめる。想定解とは違いそうだけど、解けているとは思っている。

辺を軸に対称移動させたらいい感じに処理できそう、という考察がすぐ生えて、その方針で考え始める。

対称移動を繰り返して頂点を複製する作業を何回繰り返せばいいのかを考えると、aとbの最小公倍数回だけその操作が必要になることがわかる（最初これを勘違いしていてひどいことに…）。

「x軸に平行な辺に対して対称移動させた回数」の偶奇と、「y軸に平行な辺に対して対称移動させた回数」の偶奇を固定すると、ボールがどの位置に移動したのかを簡単に記述することができる。ちなみにこの4パターンの場合分けは、コインに対してどの方向から入射するのかに対応している。

あるボールから斜め45度移動を繰り返してコインに到達できるかを考えると、x座標とy座標についてそれぞれ式が立てられて、それをまとめると一次不定方程式がでてくる。

その一次不定方程式に解が存在しないならコインに到達することは不可能。解が存在するなら、一般解から「ある方向からコインに到達する場合の最小の移動回数」が求まる。

4方向全てについてそれを求めて、それを全てのボールで行って、minを取れば（めっちゃお気持ち）、解けていると思う。

必要な道具が出そろった時点で残り5分を切っていて、さすがに実装しきれなかった…。

振り返り

自分たちの実力を踏まえたときに、Dまではかなり理想的な立ち回りができていたと思う。この辺は練習の成果で、めっちゃよかった。

E、Fで完全に別チームに分かれてしまったことが一番考えないといけないポイントだと思っていて、あの時の正解の立ち回りがなんだったのかは今もよくわかっていない。また近いうちに話し合いたい。

終わり

応援していただいた皆さん、ありがとうございました。

（正式な結果はまだですが、）恐らく国内予選突破です。 1年生から3年連続で横浜に行けることをとても嬉しく思っています。

チームメイトの2人にも本当に感謝です。またこれから頑張っていきましょう。

playoff行くぞーーーー！！！！！

ICPC 2023 Asia Yokohama Regional 参加記

チームtatitsuとして、itigoさん、pitsuさんとICPC 2023 Asia Yokohama Regionalに参加しました。

自分は去年に引き続き2回目の横浜でした。また、itigoさんpitsuさんのラストイヤーでもありました。

11/23(木)

17時ごろに横浜に到着。金曜から行くか迷ったけど、早めに土地の雰囲気に慣れておきたい気持ちがあった。

宿

ある程度の広さのプライベートな空間が欲しかったので、自分は普通のビジホに泊まった。宿代だけで43000円くらいかかってお財布が痛かった（宿泊費+交通費は支給されるけど、流石に赤字）。

itigoさんとpitsuさんは、3泊8500円のカプセルホテルに宿泊。向こうに着いてから「目覚ましがかけられない！」という話になって、ちょっとビビった…。本番だれも寝坊しなくて良かった。

ごはん

この日は小籠包とコンビニでちょっとしたものを買って食べた。

11/24(金)

お昼前から、pitsuさんと一緒に中華街を回った。

小籠包、点心、ちまき、大鶏排、フルーツ飴など、主要なものは一通り食べたと思う（めっちゃ奢っていただいて感謝…！）。いろんな話ができてとても楽しかった。

結局5,6時間くらい歩いて17時過ぎにいったん解散、夜は北大OBの方々+北大現役勢（tatisu,elephant_spaghetti）でご飯を食べた。 JAGのこととかOBの方の近況とか、面白い話もたくさん聞けて楽しかった（ビザ間に合うといいですね…）。

11/25(土)

開会式&リハーサルの日。pitsuさんのお友達+tatisuでお昼ご飯を食べてから会場に向かった。

リハーサル

席は一番左の列の真ん中くらいで、去年とは逆サイド。前には東大のSPJがいて、夏合宿で同部屋だったzkouさんと少し話をした。

リハーサルでは、コンテスト本番で使うvscodiumの設定を確認したり、インタラクティブ問題のサンプルケースを手元で回せるやつ（去年はなかった）の確認をしたり、キーボードの叩き心地を確認したり（キーキャップが小さめで、僕は結構苦手だった）。

夜

この日の夜は、高校の友達（ICPCのバイトで来てた）と中華街や山下公園まわりを散策した。

久しぶりに話ができて楽しかったし、適度に気持ちもほぐれてめっちゃいい時間だった。感謝！！！

その後はホテルに戻って23時くらいに就寝。

11/26(日)

7時起床。寝覚めはいい感じだったけど、しっかり朝ごはんを食べたのは失敗だったかも（眠気が…）。

会場入りは8:40からで、8:45くらいには入場（受付の人が、前日会ってた高校の友達でびっくり）。

荷物をまとめたり適当にだべっていたりしたらすぐに時間がきて、「緊張：ワクワク＝3：7」くらいの心境でコンテスト開始。

コンテスト中

itigoさんがPCのセットアップ、pitsuさんがA、僕がBを読む。

itigoさんがPCを空けたあとすぐにpitsuさんが実装を始めた。安心感を覚えると同時にBが思ったよりわからず少し焦る。

序盤のタイムロスは痛いので、あまり一人で悩まずすぐにitigoさんに相談する。

  • この辺でpitsuさんがAをAC

二人で少し考えているとitigoさんが解法を語り始めたので、実装を引き受ける。途中、問題をめちゃめちゃ誤読していたことに気づいたりしながら実装を終えるも、サンプルが合わない。しっかり焦る。

Fが良い感じっぽかったので、コードを印刷してitigoさんにPCを明け渡す。

解法は正しい自信があったので、一生懸命コードを睨んでバグを探していたら入力を受け取っていないことに気づく。あーーーーーーーー。

  • ごめんなさいをしながらBをAC

ACを取ったことで頭が少し冷える。itigoさんがFを書いている間にpitsuさんと手分けをして解けそうな問題を探す。

まずJを読んだが何もわからない。何もわからないことを報告してKを読む。これは解けそう。

pitsuさんの方にはすぐに解けそう感じの問題はないらしく、一緒にKを考えることにする。

誤読防止のためにpitsuさんには前情報を入れずに問題文を読んでもらうことに（これは国内予選のときからやってた）。

pitsuさんが読解をしている間にそれっぽい解法が生える。回数が結構ギリギリなので、慎重に吟味しながらpitsuさんと解法を煮詰めるフェーズに入る。

  • 解法の正当性を確信して、ある程度の実装方針が固まった辺りでitigoさんがFをAC

すぐにPCを貰って実装を始める。怖いところがいくつかあって、pitsuさんにこまめに確認を取りながら実装した（itigoさんはこの間にDE辺りを読んでいたと思う）。

一通り実装を終えたと思ってチェッカーで確認したら、色々バグっててやばかった。チェッカー神。

  • なんやかんやでKをAC

itigoさんが「Dは実装が重いけど解ける」という話をしていて、pitsuさんが頑張ることに。自分はE、itigoさんはGH(？)を読む。

EはbitDPっぽさが凄くて、愚直にやると $O(N^{3} * 2^{N} )$ というところまではスムーズに考察が進む。「8secだけど $N \leq 24$ だし流石にですよね...？」とitigoさんに聞いてみたところ、枝刈りの案が返ってきたので突き進んでみることに。

Dの実装が終わり、WAがでたタイミングでPCを譲ってもらう。実装は軽かったが投げてみるとTLE。

ここからしばらくDのWA、EのTLEと戦う時間が続く。

Dはpitsuさんとitigoさんが印刷されたコードを読んでバグ探し、Eは自分がPCを貰って定数倍高速化を図っていた。

お互い何度か失敗するも、同じくらいのタイミングで、それぞれ気合でACを取る（Dは誤読してたらしい？）。

  • DをAC（2WA）

  • EをAC（3TLE）

順位表的に次に解けそうなのはG、次いでH。残り時間は1時間半くらい。

pitsuさん「Gは苦手枠。力になれそうにない」

itigoさん「ＨよりはＧの方が簡単そう」

僕「どっちも頑張りたい」

ということで、pitsuさんがH、itigoさんがG、僕が両方の考察を行き来する感じになった。

そして椅子を温める…

そして椅子を温める…

そして椅子を温める…

コンテスト終了。

Gは「操作回数が少ないから何かを全部試せそう」、Hは「一人だけなら解ける」というところまでは考察が進んだ。

特に、Hはpitsuさんが2回くらい貪欲を投げていたがWA。

解説・結果発表

最終28位。去年より1個順位が上がった。

Kの想定解を聞いた感じ、query回数の制約が500ちょいしかなくても解けそうに思ったけど、そんなことはない？

Eの $O(N^{3} * 2^{N} )$ はやっぱり非想定だったね。

Gは可能枠だったのに拾えなかったなぁ…解説聞いても理解できていない部分があるから、aizuのjudgeに追加されたら取り組んでみる。

あとは、Speed Starは凄かった。

コンテスト後

20:40発の飛行機に乗るために早々に撤収。

飛行機が20分くらい遅れて、札幌までの終電逃しそうだった。危なかった。

感想

まずは悔しい。でも今できる最大限のパフォーマンスはできたようにも思う。自分に対して思うことは色々あるけど、これを最後の年までひきずらないように、これからやることをやっていく。

あとはやっぱり楽しかった。itigoさんとpitsuさんには入学したときからすごくお世話になってるし、そんな先輩方のラストイヤーに、同じチームで出場させてもらえてとても光栄でした。

来年のICPCに向けてまた精進します。

2023JAG夏合宿参加記

はじめに

こんにちは、tardigradeです。北大の競技プログラミングのサークルに所属しています。

2023/09/16～2023/09/18に行われていたJAG夏合宿に参加しました。 jag-icpc.org

本記事はその参加記です。

合宿参加前

実は7月末くらいからほとんど競プロをしていませんでした。

テストが忙しかったり、外せない予定がたくさん入っていたり、メンタルが死ぬ出来事が起きていたり、色々理由はあるのですが、とにかく本合宿が久しぶりに競技プログラミングに触れる機会になりました。

「チームメイト（itogoさんとpitsuさん）に迷惑をかけるかも」という申し訳なさと、「同部屋の人とちゃんとコミュニケーション取れるかな」という不安とで、合宿前はかなり緊張していたのを覚えています。

Day1（コンテスト以外）

一度東京駅で迷子になりましたが、なんとか13時前に集合場所に到着。意外と綺麗な場所でびっくり。

いろんな大学から60人くらい（スタッフを入れるともっと）集まっていて、かなりドキドキしました。

この日は最初に簡単な自己紹介をしたのちに、すぐに3hのコンテスト（韓国の国内予選）が始まりました。

久しぶりの競プロ&英語で頭がびっくりして、かなり疲れました。

コンテスト後はご飯を食べて解説を聞いて、あとは自由時間という感じでした。

晩御飯の直後からめちゃめちゃ睡魔に襲われていて、ABCはパス。同部屋の方+αとito（ボードゲーム）をして、お風呂に入って、外のコンビニに買い物に行って、そのあとはすぐ寝ました。

人見知りがでてるなぁという自覚はありつつも、同部屋の方とある程度打ち解けられて少し安心しました。

Day1（コンテスト）

キー配列が違う関係で、僕はこの合宿のコンテストで一秒もキーボードに触れていないんですが、この日は考察も役立たずでした。実質何もしていません。

僕がAを読んでいる間にpitsuさんがEを通して戻ってきて、その流れで問題概要を伝えたらすぐに解いてくれました。

そのあとも、FとかGとかを読んでそれっぽいことを言ってると、itigoさんとpitsuさんが全部解いてくれました。

終わりです（え？）

Day2（コンテスト以外）

朝の5時に目が覚めたので、お散歩をしていました（さすがに眠くなって朝食後に少し寝ました）。

x.com

この日は有志コン（5h）でした。個人的には、3日間の中でこのセットが一番しんどかったです。

コンテスト後は解説を聞いてごはんを食べて、またボードゲーム（たった今考えたプロポーズの言葉を君に捧ぐよ。）をしました。

x.com

ルールを聞いたときは結構えぐいなぁと思ったんですが、やってみるとかなり面白かったです。またやりたい。

その後は21時からARCにでて、しっかり冷えました。でも久しぶりにコーディングしてめちゃ楽しかったので、出てよかったです。

同部屋の人と少し感想戦をして、すぐ寝ました。

Day2（コンテスト）

最初にAを見ました。ナニコレ。

人類がAを通しまくってるので、何かいい方法があるんだろうなと思いながら問題とにらめっこしていましたが、なかなか解法が生えません。

最終的にエスパーを二回くらいして通しました（一時間くらいかかった）。

あとから考えると、実験コード書いて試すのが最適ムーブだったとは思うんですが、「PCが使われてた（itigoさんが沼ってた）」&「自分が実装できない」というのが理由で、あの時は選択肢に出てきませんでした。反省。

その後は、他の問題のエスパーやデバッグを手伝ったりしていました。

いくつかの問題で沼りまくって、かなり辛い気持ちでコンテストを終えました。

Day3（コンテスト以外）

また5時に目が覚めたので、散歩をしました。

x.com

朝食を食べた後にチェックアウトの準備をして、同部屋の方と記念に写真をとりました。

楽しい合宿になったのは同部屋の方々のおかげでもあるので、本当に感謝です。

この日はJAGセット（5h）でした。

コンテストを終えた後は、解説を聞いて、北大勢で少し話をした後解散しました。

Day3（コンテスト）

最初にC以降の問題に一通り目を通しました。

ABが通ったあたりで、順位表からIJが簡単そうという話になりJを担当。

直ぐに解法が生えたのでpitsuさんに話して通してもらいました。

その後は昨日と同じで、それっぽいことだけ言う役目をして終了です。

3日間全体を通して、あまり役に立てなかったなぁというのが僕の感想です。もっと強くなりたい。

最後に

文章にするとうまく表現できなかったんですが、この夏合宿で得られたものはたくさんありました。

参加してよかったと心から思える、とても楽しくて有意義な3日間でした。

運営に関わってくれたJAGスタッフの皆様、本当にありがとうございました。

ICPC2023模擬国内参加記

2023/06/24に開催された模擬国内にチームtsurataNで参加しました。

メンバーはN_haraさん、pitsuさん、僕(tardigrade)です。

ICPCはitigoさん、pitsuさん、僕で参加しますが、itigoさんが学会の発表で予定が合わなかったので、代わりにN_haraさんに来ていただきました。

結果はABCDEの5完で16位でした。

～コンテスト直前

大学内の図書館の一室を予約していたんですが、色々あって開始2分前くらいまでドタバタしていました。

なんとか時間通りに始められて良かったです。

コンテスト開始直後

pitsuさんが問題文を印刷しにいって、他二人がA問題を見るという立ち回りでした。

A問題

はい。N_haraさんが綺麗に実装してくれて難なくAC。

実装している間に問題文の印刷が終わったので、僕がB問題を、pitsuさんがC問題を眺めていました。

B問題

A問題を通した後ノータイムで実装に移ってこれも難なくAC。

普段US配列を使っている関係で、僕は実装をしない方針だったので、pitsuさんに考察を話して実装してもらいました。

実装しないならBをpitsuさんに見てもらったほうが良かったかも。

C問題

pitsuさんがB問題を実装している間にN_haraさんと二人でC問題を考えていました。

僕「上二つだけ使えば良さそうですね」

N_haraさん「あ、ほんとだ。じゃあ121212....111...みたいにするのが最適ですね」

僕「え、天才です」

B問題を通した後、これもほとんどノータイムで実装に移ってAC。

オーバーフローでペナを吐いたので、「本番はlonglongだけ使おう」という話になりました。

ちなみにこの時点で全体2位で、結構びっくりしていました。

D問題

N_haraさんがC問題を実装している間にpistuさんと二人でD問題を考えていました。

pitsuさん「DPっぽいな～」

pitsuさん「こんな感じかな～」

僕「すごい、良さそう」

pitsuさん「でも10**11くらいかかるね～流石に遅いかも」

この辺でCが通ったので、とりあえずpitsuさんに実装を始めてもらいながら、N_haraさんと高速化の方法について考え始めます。

僕「累積和を持ってこんな感じでこうすると256のループが一個削れて高速化できます」

N_haraさんpitsuさん「「ほんとじゃん」」

これでDが通って4完です。

E問題

幾何というよりは数学問題だね～という話に。

僕「傾きの近似みたいな感じ？上からと下からでいい感じに抑えたいですね」

↑が良くない方針で、かなり時間を溶かしました。反省。

～～残り20分くらい～～

僕「これ、最短は絶対1/a（厳密には違うけどお気持ち）になりそうで、そうなるとこの一次不定方程式が解ければよさそう？」

↑天才をしました。偉い。

N_haraさん「拡張ユークリッドの互除法ありますよ～」

pistuさん「実装しますね～なんか返ってきた値の絶対値を取るとよさそう～正当性わからないけど時間ないし絶対値とって出してみますね～」

N_haraさん僕「「まぁこんなテキトーで通らないですよね～」」

pitsuさん「通った！」

これで5完です（え？）

終わり

int型は使わないようにしよう。

模擬国内の運営に携わってくださった皆さん、急遽ヘルプで入ってくれたN_haraさん、ありがとうございました。

国内予選勝つぞー！

ICPC2022アジア地区予選参加記

2022/12/28に開催されたアジア地区予選にチームTokishirazuで参加しました。

メンバーはSlephyさん、nmyさん、僕(tardigrade)です。

結果から書くと、ABFGの4完で29位（4完中最下位）でした。

大会終了直後に急いで書いているので、ところどころ読みにくいところもあるかと思います。 後々こっそり修正するかもしれません。

～コンテスト前夜

僕は25日から横浜入りしていました。

25日は横浜に来てくれた高校時代の友達と中華街を中心に散策し、夜はAGCに参加しました。

26日はICPCの過去問を解いて、夜は中華街の食べ歩きをしました。

27日は午後から開会式とリハーサルがあり、環境の確認をしたりOBの方々と交流したりして過ごしました。かの有名な双子とお話しさせていただく機会もあり、なかなか貴重な経験でした。「北大こどげ強くないですか？」「天下一プロコン優勝してて凄い」という嬉しいお言葉もいただけました。

コンテスト前夜～コンテスト直前

緊張と興奮であまりよく眠れませんでした。寝つくのはかなり早かったのですが、ちょくちょく目が覚めて苦しい思いをしました。

朝は7時過ぎに起きて、リハーサルのときに貰った菓子パンを食べつつ、ずっと温めていた青diffの問題を一つ通すなどしました。アドレナリンが出ていたのかわかりませんが、頭の調子は悪くなかったと思います。

8時半にチームメイトとホテルのエントランスに集合して会場に向かいました。Slephyさんは僕と同じくあまり眠れなかったみたいですが、nmyさんは「しっかり寝ちゃってごめんなさい(*'ω'*)」といつもの調子で構えていらっしゃったのがとても心強かったです。

会場についてからは、持ってきた資料を整えたりスマホやリュックを袋に詰めたりして、コンテストの開始を待っていました。

コンテスト開始直後

事前の話し合いで、僕がAを、SlephyさんがBを、nmyさんが環境構築を担当することになっていました。

予定通りSlepyさんから問題冊子を受け取り、さぁ目を通そう！というところで問題が発生します。

ログインができない！！！！！

実はリハーサルのときも同じ問題が起きていたのですが、本番でも同じことが起きてしまいました（PCの不調？）

係の方に見てもらい、PCを再起動してもらうことに。運営の方々の配慮により自分たちだけコンテスト時間を3分伸ばしていただきました。ありがとうございました。

A問題

問題はかなりシンプルで、解法もすぐに思いつきます。

nmyさんが最低限の環境構築を終えるのを待ってすぐにバトンタッチ、そのまま特に詰まることなくACしました。

この間、Slephyさんとnmyさんは二人でB問題に取り組んでいました。

B問題

Slephyさんから大まかな考察を共有していただきます。僕がかなり雑な考察を投げると、先輩方がいい感じに整形してくださって、実装はまた僕が受け持ちました。

二分探索の境界値をミスって1ペナ（大反省）しましたが、これもわりとすんなり通せた感覚です。

D問題

Slephyさんがいろいろな問題に目を通してくださって、「これ行けそう！」という問題を渡してもらいます。 nmyさんと一緒に考察を詰めて、実装はまた僕の担当に。

「実装重たい頭壊れる～」と思いながら頑張って実装をしました。この間にnmyさんとSlephyさんはF問題とG問題を見ていたと思います。

実装を終えて（実はあんまり重たくなかった）投げるとペナが付きました。解法には自信があったのでびっくりです。

デバッグには時間がかかりそうだったのと、G問題の考察がすでに終わっているらしいので、ここでnmyさんとバトンタッチ。

コードを印刷してSlephyさんと一緒に間違っていそうなところを探す作業に入りました。

F問題・G問題

D問題のバグが一向に見つからないので、Slephyさんから一旦F問題の概要と考察を聞きます。

「なるほど～確かに」と相槌を打っていると、いつの間にか簡単な部分和問題に帰着しました（びっくり）。 Ｇ問題のサンプルが合わなくてnmyさんが苦しそうだったので、ここで再び交代します。

二人がG問題のデバッグを進めている間にF問題の実装に取り掛かりました。 やることは簡単なDPだったのに実装が下手くそ（mapを使いました）でTLEを連発。 解法はあってるはずだと信じて、定数倍高速化の道を模索することに…。

自分が苦しい時間はnmyさんがGの実装を、nmyさんが苦しい時間は自分がFの実装を、Slephyさんは僕が書いたDの解法の粗探しをしつつ他二人のサポートを、という体制で戦う時間がしばらく続きました。

順位表が凍結して20分がすぎたタイミングで、ついにGの実装を詰め切ってAC。殻が一つ破れました。

D問題・F問題

残り時間も少なくなる中、D問題のデバッグとF問題の定数倍高速化を続けます。 F問題の方は、PBDSのhash_mapを使ったり、QCFiumをつけたり、cin/coutの高速化をしたり、本当にいろんなことをしました。

D問題の方も、手動でいろんなテストケースを作ってもらったり、assert入れて投げたり、こちらもいろんなことを試しました。

そんなことを続けていると、終了20～30分前についにF問題が通ります。どうやらmapを持ったのが大悪手で、素直にvectorを持つのが良かったようです。うーー悔しい。過去に、mapでDPテーブルを持つとTLEせずに通る、という問題を解いたのですが、その時の記憶に引っ張られていました。

テキトーに考えてテキトーにAC数増やしてるからそんなことになるんだぞもっときちんと問題に向き合えよ（自戒）

そしてD問題の方は通せずにコンテストが終了してしまいました…こっちも悔しい…。

コンテスト後

Dの解説を聞いたのですが、結局自分の解法の何が悪いのかわからず…これからまた考えます。

＜追記＞

F問題は難問想定だったようで、これはちょっと意外でした。あと解説がwataさんで、感動しました（いつもyoutbe越しにマラソンの解説を聞いていたので）。

Yes/Noはやっぱり盛り上がりました。自分たちのチームは凍結後に2問通していたのですが、他のチームもいっぱい通されていて、すごいな～悔しいな～と思うなどしました。

それと、ものすごく当たり前のことではありますが、上位勢は強いなと思いました。来年・再来年はもっと勝負できるように実力をつけたいです。

終わり

応援していただいた皆さん、ありがとうございました。

これからまた、来年の国内予選に向けて精進していきたいと思います。

参加記～第9回 Asprova プログラミングコンテスト～

1．はじめに

本記事では第9回 Asprova プログラミングコンテストのmy解法をまとめています。

考察ノートを兼ねているので、あまり解説っぽい記事にはならない気がします。

2．問題概要（超ざっくり）

  •  M個の設備があるよ
  • X週稼働させるからそのスケジューリングをしてね
  • 長く稼働させるほどコストがかかるよ
  • 各設備ごとの稼働パターンはなるべく毎平日（毎休日）一緒であってほしいよ（でもC回までだったら変えてもOK）
  • 設備の計画が出力されたらこっちでN個のタスクを与えてその計画を評価するよ
  • ちなみにタスクの情報は個数含めて一切与えてあげないよ
  • 「一つでもタスクを完了できない」or「稼働パターンの切り替えがC回を超えた」場合は0点ね
  • そうじゃない場合、スコアは設備の稼働コストのみに依存するよ（どれだけ早くタスクを終わらせたかは関係ない）
  • 出力→評価をE回繰り返して一番良かったスコアが君の得点だよ

3．1日目・2日目

まず、問題文を理解することに難儀。この記事を書いている時点でも（2日目終わり）、気持ちを100％理解できているとは言えないです…。

次に、ビジュアライザを動かすことに難儀。検索しながらよくわからないままぽちぽちしてたら、これまで競プロをしていた環境がぶっ壊れました…。clarを投げると丁寧な回答をいただけて、無事動かすことに成功しました。感謝の気持ちでいっぱいです。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

1日目・2日目の解法のベースは、スコアのフィードバックを利用した山登り法です。

初期解は「全部9」、遷移は「ランダムに設備を1つ選び稼働時間をランダムに短くする」としました。

130Bを超えたあたりで壁を感じ始め、いろいろ工夫はしましたが140Bに乗らず...。

焼き鈍しにすることも考えましたが、300回しか回せないのは致命的なので断念。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

この時点で1位が155B。今の山登りだとどう改善しても150Bを超える未来が見えないので、解法を一新することを決断します。

同時に、いろいろと問題を整理し直す意味も込めて、この記事を書き始めることも決めました。

4．3日目・4日目・5日目

思ったことが実装できていなくて、それを直すと140Bに乗りました。

とは言え壁は感じているので、1から解法を考え直します。

この問題の難しいポイント

作成した計画の評価をこちら側で出来ないのが辛いです。

評価を得られるのは最大でも300回なので、焼き鈍しをしようにもそのままだと試行回数が少なすぎてスコアが伸びません。

打開策は？

作成した計画の完璧な評価はできませんが、スコアは稼働コストのみに依存するので、全く予測不能というわけではありません。

より具体的に言えば、「その計画ですべてのタスクを完了できるかがわからない」のであって、「完了できると仮定した場合のスコアがいくつか」という計算は可能です。

つまり？

得られたフィードバックをもとに、「計画は少なくともこの制約を満たしていないといけない」というリストを作れないだろうか？

それができれば、その制約の範疇で焼けそうじゃない？

制約をどのように設けるのか

事実として、以下の二つのことが言えます。

少なくともこの二つは、制約として加えてもスコアが悪くなることはないはずです。

とりあえずこれだけを使って実装をしてみます。

実装

まずは山登りを書いてみます。乱択にしました。

下の画像を参考にしてください。（山登りの部分は乱択に置き換えてください）

最初にいくつかの解を提出するのは、何も制約がない状態で山登り乱択をするのはうまみが少なそうと考えたからです。

OKな計画のリストでは両方のリストで（実装の簡単のため）、計画そのものの他に「スコア」と「稼働パターンの切り替え回数」も記録しておきます。

結果

130Bくらいでした。最初に提出する解の個数は10個にしています。

考察

山登りから乱択に変更したのは、少ない探索回数の中で多様性を確保したいと思ったからです。

制約はかなり緩めのつもりでしたが、意外とスコア伸びたなという感想。

下は0000.txtの出力の様子（の一部）ですが、かなり0が多いことがわかります。

これは、今使っている制約が弱いので妥当な感じですね。

5．6日目

130Bが出たときは、OKの計画を変化させる際に、それぞれの設備について50％の確率で稼働パターンを変更するようにしていました。

これを0.5％まで下げるとスコアが145Bに乗りました。

うーーなぜ？

0000.txtの出力の様子を見てみるといい感じにスコアが更新されていることがわかります。

OKの計画から選んで変化させているのは、近傍をとってよりいい解を見つけられたらいいな、という気持ちだったのですが、設備の計画を複数個変化させてしまうと状態が離れすぎてしまうのかな？（0.5％の確率での変化であれば、複数個変化することはほぼなさそう）

試しに、1つの設備の計画だけを変化させるように書き直してみます。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

上の考察は正しそうです。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

0002.txtの出力を見ていたら、前半にベストスコアが出て、後半はそれが全く更新されていないことに気が付きました。

毎回出力するたびに記録する計画の個数が増えるので、制約のチェックに計算がかかり、乱択の試行回数が減っていそうです。

あんまり良くない解が増えることで、よい解を得にくくなっているという線もあるかな？

best_scoreを更新する可能性がない解は、可能な限り出力しないようにすると、質の悪い解が減って嬉しい？それとも多様性が減って悲しい？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

乱択の試行回数は増えたけど、スコアはそんなに伸びなかったね。

0002.txtのスコアは3.7Bくらいでもともとかなり高かったし、ここに執着する意味はあんまりないのかな。
1位が160B（平均3.2B）とかなので、3.0Bに届いていないケースを重点的に見ていくべきかも。

E=100,300のケースを見ても、かなり早い段階でスコアが収束してるっぽいので、スコアはEの値よりもタスクの値とcostの値に大きく依存してそう。だとすると取れるところで取るのが正解なのかな～わかんない…

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

今まで稼働パターンの切り替えを許容していなかったので、それを許容するような遷移を足します。

足したら150Bに乗りました！！！！！

ただ、この遷移を足したせいで、後半の乱択の試行回数が一桁になっていて辛そう。

OKの計画のリストの個数を制限した方が良いのかも？多様性が犠牲になるのでスコアにつながるかは怪しい？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

20個までしかOKの計画のリストに入れないようにしましたが、あんまり変わらないですね。NGの計画のリストのサイズがボトルネックになるだけでした。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

考えてみたいこと

  • NGの計画のリストをどうにかして軽くすることができないか
  • 乱択をいい感じに山登りに変えたらスコア上がったりする？
  • フィードバック、スコアの値以外全然活用してないけど？

6．最終日

後半に行くにつれて最高スコアの更新頻度が著しく下がることが気になっています。

これまで均等に乱択の時間を割り振っていたけど、出力を何回か無駄打ちして、一回の乱択にかける時間を伸ばしたほうが良い？

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

あんまり変わんない…

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

ちょっと早いですが、調整して撤退です…辛かった…

7．コンテスト後の反省

（他の方の解法を見て追記する予定）

ICPC2022国内予選参加記

2022/07/08に開催された国内予選にチームTokishirazuで参加しました。

メンバーはSlephyさん、nmyさん、僕(tardigrade)です。

結果から書くと、ABCDの4完でペナが11000くらい、全体30位北大内1位でした。

コンテスト前

前日の夜は緊張と蒸し暑さで全く寝付けませんでした。4時になった時点で、2限の授業をぶっちすることを心に決めました。多分5時前には寝れて起きたのが12時なので、睡眠調整はばっちりです。

朝ごはん兼昼ごはんを食べながら、適当にAtCoderの問題を見ました。DPが出題されるだろうと山をはって、EDPCを中心に考察したり実装したりしましたが、これが良かったかと言われると正直微妙なところです。

一時間前くらいに家を出て大学に向かうと、すでにチームメイトの二人が来ていました。「緊張しますね～」と言いながら立ち回りを確認したりトイレの位置を確認したりして、コンテストが始まるのを待ちます。

今年は検索あり同時コーディングありで、普段のAtCoderのコンテストにかなり近い状況だったので、PCとルーズリーフと筆記用具とお守りのぬいぐるみだけを持っていきました。

立ち回り

「チーム内で一番力があるであろうSlephyさんに、なるべく多くの問題の考察をしてもらう」ということを基本方針として立ち回りを考えました。

Aは僕が担当、Bはとりあえず二人で見て、出来そうならSlephyさんがCにすぐ移動。僕がAを通した時or開始から20分たった時点でいったん情報を共有し、必要であれば戦略を立て直す、ということだけ最初に決めておきました。

コンテスト中

問題：

All Problems (iisf.or.jp)

去年は問題を読み込むのにかなり時間がかかったという話だったので、今年もそうなることを予想していましたが、運営がきちんと対策をしてくれたのか、スムーズに問題文を見ることができました。

A問題

例年通りかやや簡単めな印象を受けました。特に何も考えずに実装して提出するとAC。一時ファイルの場所を見失ってしまい、時間をロスしてしまったのは反省…。確か5分くらいで通せていたと思います。

C問題

Aを通したのでいったん3人で相談します。

B問題は実装するだけのようで、nmyさんが頑張っている途中でした。「あと30分あれば通る」というお言葉をいただいたので、17:10頃にまた進捗を確認しようという話になりました。

C問題はSlephyさんが考察を始めたばかりでした。「数学っぽい」「ARCみたい」「実装は軽いと思う」「そこまで難しくないはず」等々のアドバイス（？）をいただき、Cを引き継ぎます。一見無駄が多いようにも思えますが、僕もCを見て同様の感想を持ったのと、面倒そうな見た目をしているDをSlephyさんに処理してもらうメリットの方が大きいと考えたがゆえのムーブでした（実際これが大成功）。

DPやらO(1)数学やらに浮気しそうになりますが、手を動かしながら問題をにらんでいるとそれっぽい解法が降ってきました。自分では妥当性が示せなかったので、実装しながらSlephyさんに2回ほど相談をし、「あってる！」と太鼓判を押されたタイミングで投げてAC。この直前にnmyさんがBを通していました。

D問題

僕がCを通した時点で、Slephyさんが「D問題の本質にたどり着いた」「あとはそれをどう処理するか」とおっしゃっていたので、とりあえずnmyさんと一緒にそこまでの考察を聴きます。いろいろ質問したり自分の考えを共有したりしていると、Slephyさんが解法っぽいものに辿り着いたようで、再びそれを聴きます。

3人で話し合った結果、「かなり良さそう」という結論に至りました。実装量が少しありそうだったので、僕が実装をしてる間にnmyさんに手動でサンプルをチェックしてもらいました。Slephyさんはこの間、E問題の考察をしています。

その後、僕が実装をバグらせていることに気づいたのとほぼ同じタイミングで、nmyさんが解法の穴に気づきます。SlephyさんをE問題から呼び戻して解法を詰めなおすと、幸いにもこれまでのコードに+αの実装をするだけで良さそう、ということがわかりました。

順位表を見ると、その時点でEを通しているのは1チームだったため、一旦Eは放置して僕とSlephyさんのそれぞれで解の実装を、nmyさんがWAを吐いたとき用のチェッカー（愚直解）を実装することに決めます。

僕がバグを修正して実装の7割方を終えたタイミングで、Slephyさんから「サンプルが通りました」との報告が入ります（実装速すぎてビビった…）。3人でお祈りをしていると無事AC。この瞬間はめちゃめちゃ嬉しかったです。

E問題＆F問題

EとFはあまり難易度差がなさそうだったので両方とも見ました。

Fは構文解析で、見た目のわりに内容は単純でしたが、考察の進め方が分からず断念。

Eを最後まで3人で考えていましたが、クリティカルな考察はできずに終わってしまいました。

感想

今回のMVPは間違いなくSlephyさんでした。Dの考察から実装まで整然とこなしていて、とても頼もしかったです。

加えて、立ち回りもかなり良かったように思います。今考えると、BやCで詰まると効率が悪い感じになりそうなので、一発ACしたnmyさんと僕もかなり偉いです（自画自賛）。

EとFは地力不足を痛感しました。いろいろ考察は出てきましたが、どれを深掘りするのがいいのか、そこに対する嗅覚が足りていませんでした。これからしっかり復習したいと思います。

大学に入学してから辛いことがたくさんあり、競プロにかなり懸けてる部分があったので、国内予選を通過してアジア地区予選に進めること、そしてこのコンテストを心から楽しめたことを、とても嬉しく思っています。チームを組んでくださったSlephyさん、nmyさんには感謝しかないです。

年末のアジア地区予選に向けて、また精進していきたいと思います。