週記（2021/11/08-2021/11/14）

11/8(月)

先週は週記を投稿してからすぐ布団に入り、しばらく本を読んで寝た。午前10時半だった。

午後3時半すぎ起床。眠気がかなり強かったためしばらく布団でクネクネして、30分くらいかけて布団から這い出た。

毎週恒例のインターン先の定例会がある。先週は進捗をほとんど産めていない。ICPCがあることを言い訳にしていたが、そのICPCに対しても特別努力していたわけではないので、もうどうしようもない。今週も4年ゼミの発表があるのでほとんど動けない予定だ。とりあえずパッとコーディングできることを一つ見繕い、ひとまずの形にすることにした。コーディングした後に進捗報告のスライドを作っていたら、1分ちょっと遅れてしまった。定例会は特に何もなし、のはずだったが、いよいよヒアリングに向けて動き出すということで、手始めに来週火曜日にミーティングが追加された。頑張っていきたいという気持ちはある。

毎週、定例会の後に勉強会が開かれる。来週は僕が担当なので、何かひねり出しておく必要がある。これまで2か月見てきた感じ、題材は本当に幅広いので、まあ何を発表してもそれなりに受け入れられるのではないかという楽観的な期待がある。その前に木曜日のゼミ発表の準備もしなければならないが。

定例会が終わってからは、しばらくICPC参加記を漁っていた。C問題はいろんなチームで一人が割り当てられ、そのまま帰ってこなかったところといつの間にか通っていたところに分かれるようだ。やはりコンテスト中の時系列、特に自分が担当していないところのものを復元するのは難しい。僕の参加記も結構曖昧になっている。また、イベントの順序という意味での時系列ではなく、何時何分という意味の絶対的な時系列はさらに難しい。これについては、時間の感覚がないのは参加記を書く以外でも問題かもしれない。個人的にC問題はスムーズに通せた印象だったが、実際には問題を見てからでさえ確実に20分以上かかっているのだった。

学食に行って、帰りにコンビニでパリパリバーを買ってきた。確か、最近何かのツイートで目にして思い出したはずだ。実家では一時期よく食べていたが、いつの間にか見なくなっていた。アイスは主に母が購入するもので、母の好みか何か知らないが、一定期間は同じ種類のものがずっと買われ続ける。パリパリバーもそうして僕の前に現れ、消えていった。

AGC055-D「ABC Ultimatum」を自力ACした。

atcoder.jp

本番では手も足も出なかった問題。今日ふと思い出してちょっと考えた方針が思った以上に良く、そのままゴールまで突き進むことができた。本番ではまず判定問題を考えようとして、それにすら失敗していたので、逆転の発想で判定問題を解かないのでは？と考えた。

分解した後の文字列が、ABCa個、CABb個、BCAc=N-a-b個となったとする。このとき、文字Aは先頭a個がABCに、その次のb個がCABに、残りのc個がBCAに含まれるよう組み替えることができる。さらに組み換えを続けて、同時に文字B、文字Cについても先頭から順番に割り振ったようにできることがわかる。よって、aとbを全探索し、現在それぞれの文字が何個あるかを持つ3次元dpをすればよい。……というのはまだ足りなくて、最後のサンプルが合わない。同じ文字列が複数の(a,b,c)による分解に対応してしまう可能性がある。ここでいったん諦めてしまったが、実は重複を省くのは簡単。ありうる(a,b,c)のうち辞書順最大なもののみ考えるようにしたい。これは、先ほどのdpで文字列を構築しつつ、同時に(a+1,b-1,c),(a+1,b,c-1),(a,b+1,c-1)のそれぞれでも条件を満たし得るかを3bit使って持っておけばよい。この3種類のどれも条件を満たさないような文字列の分解は、(a,b,c)が辞書順最大となってくれる。祈るように実装したら最後のサンプルが合い、AC。

日付が変わったあたりからゼミ準備を始めた。手始めに、前回・前々回の発表資料を読む。毎週ギリギリに起きているので頭が回っていないし、それでなくても集中が保てなくてまともに聞けていない。いつの間にか教科書でかなり進んでおり、焦った。前回の僕の発表はmodに関する話が登場し始めたところだったので、なかなか競プロチックだなあとワクワクしていたのに、それから2週間でその章が終わってしまったようだ。

何とか読み終わったが、疲労困憊。実際に自分の発表分の教科書を読むのは明日以降にしよう。少しコードゴルフをして、布団に入ってしばらく本を読み、午前7時半就寝。

11/09(火)

午後4時から午後5時まで起きていた形跡がある。ネット小説の更新を確認して、いくつか読んでいたようだ。またすぐ寝て、実際に起きたのは午後9時半だった。

食事してからゼミ準備をする。今週のゼミは写真撮影のため対面で行われるらしいので、発表も黒板を使うことになるだろうが、準備としてはこれまでと変わらずBeamerでスライドを書くことにした。しかし教科書を1ページ進めたくらいで集中が切れてしまったので、読み止しのラノベを開いた。そのまま3時間ちょっとかけて読了。

「迷探偵の条件」。「薬屋のひとりごと」の著者の新作であるが、買ったときはそのことを知らなかった。それだけ魅力的な表紙・タイトル・あらすじだった。内容もかなり良かったと思う。ミステリかどうかはともかく、ラノベとして十分面白い。それだけに、文章が微妙なのが気になった。ロープトリックの読解が難しかったので、図が欲しいところ。また、事件の関係者をアルファベットで置いたからなのか、それを間違えているところもあった。

ゼミ準備に戻り、さらにしばらく進めるとまた集中が切れたので、今度は火曜5限のPythonの講義の課題に取り組んだ。もうPythonの基本的な使い方については一通り済ませたのか、今日はライブラリを使って多項式回帰分析をしていた。やっていることがどんどんそれっぽくなっていく。向こうも脱落者を出さないように念を入れているのか、課題提出用に用意されているPythonノートブックには元から完動するプログラムが書かれるようになった。こうなると、自分なりに追加で何かするのは難しいし、何より適当に弄って出せば終わりでいいのだからそれ以上のことをするのが面倒になる。今日はそれなりに図表など描画してみたが、実際にやっていることはほぼ、無。

またまたゼミ準備に戻ったが、今度は購買が開店する時間になったので、それと学食に行った。野菜サラダを2皿選んで健康になった気でいたが、1日のそれ以外の食事に一切野菜が含まれていないため、全体としてみれば全然足りていないことに気づいてしまい、悲しい。毎日野菜を十分な量摂取するのはなんと難しいことか。僕の食事の写真を見た親にいつも、野菜が足りていないと言われるわけだ。

帰ってきて、ゼミ準備のラストスパート。午後2時半くらいに今回の担当分の教科書を読み終わり、スライドも作り終わった。もう眠いし、一晩寝かせるという意味も込めて、手直しだったり実際の発表の流れを確認するのは明日に回すことにする。とりあえずスライドをホスフィンに投げておいた。毎回確認してアドバイスをくれてありがたすぎる。

日記を書いて寝ようと思ったが、もう少しだけ起きていることにした。今日遅く寝れば寝るだけ、木曜日変な時間に起きてしまう確率を低くできる。CF #753 div.3を埋めることにした。

Dashboard - Codeforces Round #753 (Div. 3) - Codeforces

Aはよい。Bは実験すると4回ごとに元に戻るようだ。Cは操作によって要素の大小関係が変わらないので、操作する回数を順に試していける。Dは青色の要素が順列の小さい値に対応するとしてよい。Eは(0,0)からスタートしたと考えたとき、ロボットが最大どれだけ上下左右に動いたかを持っておく。Fはdpっぽいことをするが、ループを検出した場合はそのループ内の値をすべて同じにする必要がある。ループ内かどうかを頑張って検出しつつdfsした、と思ったらMLEしてしまった。どうやら最大1e6回の再帰はマズいらしい。stackを使って自分で再帰を書いたら通った。

Gはちょっと考えてわからなかった。椅子の上で一瞬意識を飛ばしてしまったので、布団に移動して寝てしまうことにした。午後6時半就寝。

11/10(水)

消えた。

11/11(木)

午前2時くらいに起きてしまった。夢を見た。

頑張って眠ろうとして、目を瞑ってdiv.3-Gを考えていたら、解けてしまった。仕方ないのでHを読んでもう一度目を瞑ったら、これまた解けてしまった。

仕方がないので一旦起きて、ラノベを読むことにした。午前6時くらいまで読んだあと、今度こそ眠ろうとしたが、どうにも眠れず、午前8時くらいに諦めて身を起こした。

広義昨日に作ったスライドをチェックする。一読して推敲しつつ、教科書と照らし合わせて抜けている情報がないかを確認し、印刷してさらにチェック。今度は、口頭で発表する際の助けとなるような情報を書き加えておく。章の変わり目に線を引いたり、細かい式変形をちゃんと式にしておいたり、参照している定理のステートメントを確認したり。それも終わったので、これで準備完了と考えてよいだろう。

シャワーを浴びようとして、うっかり今朝読んでいたラノベの続きを手に取ってしまい、そのまま最後まで読み切った。「護衛のメソッド」。特に意識せず買ったが、著者が小林湖底さんなのに気づいてびっくりした。僕の認識では、この方は今「ひきこまり吸血姫の悶々」が売れている。内容は、面白かったと思う。どんでん返しが何重かになっているのは良かったが、仲間だった人が実は敵、を1巻からやるとは、以降シリーズ化するとなったときどうなるのだろうか。確かに、1巻が売れないとどうしようもないのだが……。

死装束を着たキャラがいるシーンに挿絵がついていたが、ちゃんと左前になっていて感心した。昔道着を着るとき無意識に右手から折りたたんでいることに気づき、左側が前になっている……！と愕然としたものだが、左前とは対面から見た時の左側が前である、ということを知って安心した覚えがある。

ラノベに挟まっていたチラシで1冊気になるものを見つけたので、hontoでほしい本リストに入れておいた。

その後シャワーを浴びたので、対面ゼミに向けて出発したのは正午だった。学食に行ったらホスフィンの姿が見えたので、呼び止めてホスフィンの連れと3人で昼食を摂った。

ゼミ。発表した側の感想としては、結構うまくやれたのではないかと思っている。何も見ずに再現できるというレベルではなかったが、定理のステートメントだけ準備したスライドから書き写して、その時ついでに述べておく情報も確認して、あとは証明を黒板でやりつつ話をしていった。本の内容自体が簡単めなので、証明の再現には特に手間取ることもなし。付け加える情報については、どういう流れで話すか整理不足だったので少しとっ散らかった場面もあった。書きながら話していたので、黒板のほうを向いて喋っている時間が長かったかとも思ったが、大きな声を出すように意識していたので、聞こえてはいたようだ。

対面でゼミをするのは、やる前は面倒に思っていたが、いざ発表してみるとかなり楽しかった。普段はスライドで丁寧に（あるいはねっとりと）式変形をしてしまい、発表時はそれを読み上げるだけになっていたが、今回はほぼ手の運動な証明を口でちょっと説明するだけで終わらせられたりと、爽快感があった。実はこれには急いでいたということもあって、自分ではかなり飛ばしたつもりでも結局用意していた分が全然終わらなかったので、次回またオンラインのゼミでスライド読み上げマシーンになってしまう予定。今週と来週分のスライドは、例のごとく以下にリンクを張っておく。

Apostol_Chapter6_6.5-6.10.pdf - Google ドライブ

ゼミが終わってから、以前院試ゼミの友人と遊んだ部屋に行って、今度は5人でスカルをプレイした。ハチャメチャに楽しかった。2回戦って、1回目は僕が勝利した。どちらの回も、全部オープンするチャレンジが成功して勝負がついていたので、かなり劇的だった。今日は、ドクロを伏せておいてブラフでチャレンジしたのに、そのまま自分がチャレンジすることになって自滅するのが多かった。どうやら雰囲気がやってやろうという感じだったらしい。気を付けたい。

午後6時まで4人でボードゲームをして、山の学食で夕食を摂って帰宅。

週記（2021/10/25-2021/10/31） - kotatsugameの日記

山の上の学食で夕食を摂り、帰宅。

朝頭の中で解いたdiv.3のGHを実際に書いた。Gは、aから必ず引かなければならない分を最初に考慮した後は、差の絶対値が最小値をとるまでaからさらに引いていけばよい。Hは、まずa+b-mでグループ分けした後は、各グループでaの値をできるだけそろえればよい。これは可能なaの値が区間になって、区間スケジューリング問題を解けばよい。

眠くなる前にと思い、掛布団を秋用のものから冬用のものに交換した。シーツについている紐を蝶結びするとき、以前から自分の蝶結びのやり方を動画に撮りたいと思っていたのを思い出して、チャレンジしてみることにした。右膝の上に左足を乗せて左足の指でスマホを保持すると、何とか動画の撮影に成功した。この蝶結びのやり方は、片方を折り曲げてもう片方を周りに巻くやり方よりかなり簡単だと思っていて、中学生の頃どこかで知って以来ずっと使っている。しかしツイートしても一切反応がなかったので、もしかしたら常識なのかもしれない。

シャワーを浴びてしばらくパソコンを触っていたら、案の定すぐに眠くなったので、就寝。就寝報告のツイートをする間もなく寝たらしい。午後9時半くらいだった。

11/12(金)

午前7時起床。もうちょっと寝ようかどうしようか迷いつつ布団でスマホを弄り始めたので、当然のように二度寝ができなくなった。午前8時半くらいに身を起こす。夢を見た。

AOJ-ICPCの600点から1問解いた。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2250

問題文がちょっと曖昧だが、サンプルの3番目を確認するに、電話がかかってきてからちょうどL単位時間後まで電話を取れるらしい。適当に二分探索してみると、親切にもサンプル3で落としてもらえた。これ間に合うんじゃないかと思って二分探索の範囲を全探索するコードを書くと、通ってしまった。解説スライドを読むと、全探索が想定解らしい。向こうはlogを付けたりしているが、こちらはそれどころか1ケースあたりO(N^2 T)に定数倍が64分の1ついているので、圧倒的に速い。

さらにもう1問開いたが解けなかった。悩んでいるうちに午前10時になったので、切り上げてゲーセンに行くことにした。途中学食で昼食を摂り、先週木曜日のチュウニズム新作稼働以来初めてのゲーセンへ。

カードを通すとレートが16.82になった。実は旧筐体では、2019/12/30にレート15.83を記録してからほぼ2年highestを更新していなかった。まさかこのような形での更新になるとは……。

理論値済みの譜面を選んで試しにプレイしてみると、FASTがすごいことになった。判定Bという新しく増えた項目の値を-1.0くらいにするといい感じにFASTとLATEのバランスが取れたので、しばらくこれでやってみることにする。他に、判定時にFASTとLATEを表示したり、JCの表示をなくしたりしてみた。

今日はずっと新曲を埋めていた。MASTERチケットを使ってあらかた解禁した後、ポプアニの譜面についてはAJ埋めまで済ませておいた。やはり新筐体になって精度が出しやすくなっているのか、今日AJを出した譜面は全部99AJだった。そのうち初見AJは20譜面。最初はAIRの新しく増えたノーツにびっくりしたり、譜面が見えずミスを出したりしたが、AIR-SLIDEは手の誘導になっているということを意識すると何となくわかってきた。ただしAIR-CRUSHは譜面が見えなくなるだけなので、害悪。

通っているゲーセンはチュウニズムの後ろにmaimaiが並んでいるのだが、今日そこからSweets Timeが聞こえてきてびっくりした。どうやらちょうど今日追加されたらしい。

午後5時から1on1があるので、そこそこで切り上げて午後4時半には家に着いていた。1on1まで新しくなったチュウニズムネットを眺めていた。課金しなくても直近50回のプレイ記録が見られる（内訳は見られない）のと、ランキングのところで自分のハイスコアが確認できるようになったのが変わったところだろうか。あとはOVER POWERもプロフィールから確認できるようだ。思ったより低くてびっくりしたが、まだ新曲を埋めきっていないので、当然といえば当然だった。……よく考えたら、そもそもMASTERを解禁していないので、OPにも含まれていないのだろうか？そうだとしたら、自分のOPがもともと低かったということで、かなりショックだが。

CHUNITHM ■ CHUNITHM-NET

1on1。ここ2週間くらいICPCだのゼミ発表だのでほとんど稼働していないが、そもそもヒアリングをすると決まってからは、実際にヒアリングを始めるまであんまりすることがなかったのだ。まだしばらく時間が空くので、その間何をしていましょうか、ということを話し合った。するといろいろアイディアが出てきて、やってみたいことがたくさん積みあがった。

これでコードが縮むかと思って試してみたが、WAが出て通らなかった。なぜ通らないのか全然わからなかったので、適当に試していたら、8頂点の直線グラフで落ちることに気づいた。驚くべきことに、AtCoder上のOctaveでは以下のツイートのような行列積を正しく計算できないらしい。手元のcygwin+Octave 5.2.0やUbuntu+Octave 5.2.0では正しく計算できている。かなり謎。

yukicoder 322に出た。30分足らずで全完。

yukicoder contest 322 - yukicoder

Aはよい。Bはちょっと難しかったが、冷静になると魔法Aを優先的に使い切ったあとの残り体力の総和を魔法Bで削り切れるか見ればよい。Bの強化版らしいEに飛んで、これはBのコードをそのまま二分探索の判定関数にすればよい。Cは素因数の和。Dは適当に式を立てる。ボールが1個も入っていないケースでREを出してキレてしまった。Fは桁dp。Gは寄与が二項係数の偶奇でわかるので、Lucasの定理で求める。Hはセグメント木を想像して、浅いところに上がるのは立っている一番下のbitに1足す、深いところに潜るのは差を取ってpopcount、とした。

結構眠い。少しネットサーフィンして、午後11時過ぎ就寝。

11/13(土)

午前5時半くらいに起きてしまった。AOJ-ICPCの600点の問題をいくつか頭に入れて考えていたら、また眠れたようだ。午前10時半起床。

すぐ準備をして午前11時からゲーセン。昨日は平日なのに昼間からチュウニズムが埋まっていたので、休日である今日はもっと待ちが多いんだろうな、と思っていたら案外空いていた。今日はLv.12からどんどんAJ埋めを取り戻していくことにする。Lv.12+以上は、旧筐体のときからLv.12以上だった譜面ばかりなのでちゃんとAJで埋まっているが、Lv.12はLv.11+から上がってきた赤譜面が結構あった。ところどころ難しいものもあったが、どの譜面も2回以下でけりをつけてLv.12のAJフィルを取り戻し、そのままLv.12+、Lv.13とAJで埋めることができた。

Lv.13+まで埋めて今日は終わりにしようか、と考えていたら、「XL TECHNO -More Dance Remix-」の赤譜面が異常に難しくて、残り時間はずっとこれをプレイする羽目になった。結局難しくないところに癖がついてしまったので、今日は終わり。ちょうど待ちも出てきたようなので、連動イベントのためにmaimaiとオンゲキをそれぞれ1クレプレイし、帰ることにした。午後3時以降生協から弁当が届くので、それに間に合う必要がある。

メールでアマギフが届いていた。ABC225の飛び賞が当たったらしい。アカウントに反映するのを忘れていたTCB40の1位の賞金と合わせて、一気に1万円が転がり込んできた。定期購入しているお茶の代金に使われるだろう。それにしても、これまで飛び賞なんて設定せず上に詰めてくれよと思っていたが、実際に当たったのでそんなことは言えなくなってしまった。

ラノベ新刊チェックをした。11月下旬に発売する本は、チェックから漏れていたのか、それとも先月末に予約したからチェックを外したのか、どちらかわからなくてちょっと不便だった。

弁当は結局午後4時半に届いた。すでにかなり眠く、ちょっと昼寝でもしようかとも思ったが、せっかくいい感じの生活リズムなのを崩したくないと思い、シャワーを浴びた後は頑張って日記を書いていた。午後9時からABC227。

KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) - AtCoder

全完10位。学生順位は5位か、6位か。よくわからない人が一人いて怪しい。

Aはよい……はずが、なぜか頭が回らなくて1分もかかってしまった。初手でdc 9Bを出せて最短なので、それはよかった。Bは適当に全探索。うっかりRubyで書き始めてしまい、挙動がよくわからないので書き直すことを何度か行っていたらこれもまたかなり時間がかかってしまった。具体的には、配列の引き算が集合としての引き算であることは覚えていたが、重複する要素が消されるかどうかを覚えていなかったのだ。実はこれは消されないので、ただ引き算をすれば答えが得られる。このことがわからなかったので、本番ではわざわざ要素ごとに.include?メソッドを使っている。Cは適当に全探索したら爆速だったので出した。Dは、降順にソートすると大きなほうからいくつかは全部使えないな、など考えていたら、決め打ち二分探索を思いついた。Rubyで実装しようとして、実行時間を気にしてC++に変え、提出するとWA。二分探索の上限設定ミスと、それを修正したことにより顕在化したオーバーフローで2WAだった。どちらもRubyで提出していれば避けられたミスだけにもったいなく感じるが、そもそもC++でミスるほうが悪いのだ。ちなみに、このアルゴリズムでRubyでの実行時間は問題なかった。

Eはパッと見操作回数をmapのキーに持ってdpかと思ったが、操作回数にどれくらいの種類があるのかわからず怖い。冷静になってみると、操作回数は最大でも転倒数程度にしかならないので、普通にdpを書いた。FはなんとなくAlienDPっぽさを感じた。なぜそう感じたかはよくわからない。二分探索できると嬉しいのがAlienDPの特徴だが、これくらいの制約なら二分探索じゃなくて全探索してもいいんじゃないか、と思い、答えとなる移動における大きいほうからK番目の値を固定してみたら解けた。同じ値の要素があるとつらいので、インデックスを含めて比較するコードを書いた。コンテスト後のTLで知った方法だが、大きいとしても小さいとしても良い、と取り扱うのが一番楽そうだ。Gは区間篩して残った要素は全部素数。区間篩の幅をKにしてしまい1WA。修正のとき、残った素数たちに重複があるかと思ってそれに対応したコードを書いたが、残った素数は全部10^6以上なので、N-K+1\dots Nの素因数として2回以上出現することはない。

Hは難しかったが、何とか時間内に解けた。移動は、方向も含めて24種類しかない。それぞれの移動回数が分かれば経路は復元できるだろう。ここで、各マスの入次数と出次数がそれぞれ入力からわかるので、18個の等式を立てることができる。この連立方程式が非負整数の解をもつか確かめ、持てば復元、という風に解くことにした。連立方程式の解を求めるのには、今回はフローを流せばよかったようだが、わからなかったので、Octaveのglpkという関数を使った。これで解いて経路を復元すればよい。書きなれない言語で必死に頑張り、数十分かけて書き上げた。サンプル2を試すと、連立方程式の解は見つかるようだが、答えはNOになる。実際に経路を復元してみたところ、移動回数が使い切れていない。どうやら経路が2つ以上の連結成分に分かれてしまっているらしい。経路復元で移動回数を使いきれなかった場合NOという場合分けを入れるとサンプルが合ったので投げたが、WA。恐らく、連結成分に分かれるような移動回数の割り当てとそうでない移動回数の割り当てがあって、glpkで求めた解が前者の場合に落ちているのだろう。glpkでは最小化する目的関数を設定することができて、今は適当に重みをすべて1にしていたので、そこをランダム値とすることにした。これで何回か挑戦していれば、そのうちうまく連結になる移動経路を引き当てることができるだろう。というか、残り10分しかないので、これでダメだったらおしまいである。TLの様子も見て5回くらい調べるコードを書くと、爆速で通ってくれた。この乱択っぽい部分はフローで再現しようとするとかなり難しく、実際1ケースWAを出した人が、何とかランダムにしようと辺の順番を弄ったりしたという話をTwitterで見聞きした。

Submission #27234914 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)

コードゴルフ。Aはコンテスト中のものでよい。Bは各Sに対してaを全探索し、\frac{S-3a}{4a+3}が正整数になるかを確認する。aの上限を適切に決めることで正であることの確認が必要なくなり、整数性だけ確認することになる。つまりこの分数が割り切れればよいという話で、それを調べるときのS-3a\equiv S+a+3\pmod{4a+3}という式変形はかなり頭がよくてびっくりした。Rakuで実装して最短。Cは典型90問-085がかなり近いので、最短コードをコピペしてちょっと変えたものを提出しておいた。DはRubyのbsearchを使うコードをVimで書くとさらに短くなるいつものやつ。以降は手付かずである。

085 - Multiplication 085（★4）

朝方まで日記を書いて、布団に入って少しYouTubeを見てから午前5時就寝。

11/14(日)

午前10時半くらいに起きてしまった。YouTubeを見たりしていたら眠れるわけもなく、しかし起きる気にもなれず布団でゴロゴロしていた。

Twitterで興味深い問題を見つけた。4つの数が与えられるので、適切に並び替えた後四則演算と括弧を使って所定の数値になるような式を作る、という問題。何パターンか取り上げられていたうち、8/(1-1/5)=10はかなり有名な問題で、それの類推から(1-1/9)*9=10、(3-7/4)*8=10、12/(3-13/5)=30は解けたが、3,7,7,11->2という問題の解き方が全然思いつかずに苦しんでいた。あまりに苦しいのでTwitterで助けを求めたところ、引用ツイートで教えてもらえた。

衝撃的過ぎてしばらく呆然としていた。

昼から夕方まで、来週月曜日の勉強会の準備をしようとしていたが、考えが全然まとまらず、結局Twitterを見たりして時間を無為に過ごしてしまった。午後4時からAHC006に1時間だけ参加した。このために今日の午後3時からあったCF div.1は見送っていた。

Kyocera Programming Contest（AtCoder Heuristic Contest 006） - AtCoder

とりあえずコードゴルフのつもりでRakuやVimのコードを提出したあと、C++でコードを書く。どうせ1時間後にはOpenCupなので、とにかくシンプルな解を作ることにした。まずレストランを50軒回って、次に配達先を50か所回るのが一番面倒がなくて確実だろう。このとき、レストラン同士・配達先同士が近ければ良さそう。ここで、領域を4分割すると、レストランが位置する領域と配達先が位置する領域のペアは16通りなので、どこか1つのペアには注文が50個以上属することになる。そのようなペアを固定することで使う注文を決定することにした。

レストランと配達先は適当に巡回セールスマン問題を2-optで解くことにしたが、ここで区間reverseのとき右端をbegin+rではなくend+rにするというバグを埋め込んで大変なことになった。どこで落ちているか確認するために出力を挟むと、落ちる場所が変わってしまう。気づくのに10分くらいかけてしまい、結局OpenCupには間に合わなかった。

チームメイトに遅刻すると断りを入れて、もう少しだけ続けることにする。最初の提出は1303679点だった。次に、2-optを山登り法で行っていたので焼きなましに変えると、1303679点になった。最後に、実行時間にかなり余裕があったので、使う注文50個をリストをシャッフルして何回も選ぶことにしたら、1310835点になった。これが午後5時15分のことで、このアイディアではこれ以上先はなさそうなので、今度こそOpenCupに向かう。

OpenCupはチームで9完だった。AIGEDJBFKの順。最終的な結果を見るに、この9問とそれ以外の3問の間にはかなり大きな崖があったようだ。崖の手前までちゃんと通せたのはよかった。

僕が問題を読み始めた時には、すでにAとIが通っていた。次にGが解かれていたので読み、面倒だけど書けるなと思って書き始め、ちょっと苦しみつつ投げたらWAだった。どうやら誤読をして、直線状に並ぶ街を円環だと思い込んでいたらしい。それがわかってしまえば実装で苦しむ必要もなし、と投げるとまたWA。今度はコーナーケースで、チームメイトが示唆したケースで落ちたので、それを修正して投げるとようやくACできた。次にE問題を読み始めたが、僕が有向グラフであることを読み落としているうちにチームメイトが解いてしまったので、書くのは任せてさらに別の問題を読みに行った。

D問題を読む。順当に最大の要素をどう動かすか考えて、良さそうな移動方法を思いついたが、順位表を見るにかなり落ちていたので、不安になっていた。考えているうちにどんどん正しそうに思えてきて、チームメイトが実際に書き始めたあたりで何となくの証明が完成した。具体的には、「良さそうな」移動方法によって、実際行われるべきだった移動を行えなくなることがないことが言えた。

いつの間にかJのコーディングが始まっているのを横目にKを考え始めたが、全然わからない。唸っていると急にチームメイトがFとBの解法を出してきた。それぞれ幾何と、ランレングス圧縮をmapで管理してごにょごにょするやつで、かなりやりたくなさがあったが、僕はFのほうがやりたくないと思っていて、チームメイトはBのほうがやりたくないと思っていたようだったので、二人とももう片方を担当することになった。JがWAになったあたりでまず僕がBを書き始め、途中一瞬の割り込みでJがACされつつ、30分くらいかけて丁寧にコーディング。投げると一発で通ってかなり気分がよかった。定数倍高速化のため、mapへの挿入時に挿入すべき場所のイテレータを一緒に渡すやつを多用した。しかしこれは、コンテスト後に全部外して投げてみたところ、普通に間に合ってしまった。

Fが書き始められたので、再度Kを読む。最短路という文言を見落としていて、この元では僕が適当に投げたヤバそうな解法が実はヤバくないのでは？という話になった。Fが落ちてしまったのでチームメイトがKを書いたものの、TLE。Kが何度かTLE出ている間にFのコードを読んであれこれ言っていたら、Presentation errorが出たりしつつも30分くらいで何とか通ってくれた。

残りはKの定数倍高速化だけ。1時間くらい全然光明が見えずかなり辛かったが、uniqueを取っていたところは実は最悪ケースではほとんど重複しないだろうことに気づき、チームメイトがそれならBFSではなくDFSで良いということを残り15分で指摘して、残り3分の時点で通った。細かい話を書いてもしょうがないのでこうあっさり言っているが、通ったのを見た瞬間は思わず声が出るくらい感動した。最終的に単純なDFSで解けてしまい、おもしれー問題。ヤバいケースが思いつかないからと言って投げていたが、計算量解析などはどうなっているのだろうか。

AHC006は、僕は入力された頂点のうち先頭100個のみを回っていたが、全頂点を回るコードでもよく、それが最短になっていた。Vimで書き直すとさらに縮んだ。

日付が変わったあたりから勉強会の準備を再開した。題材は決まっていて、それに関して触れたいこともリストアップしておいたので、流れを考えてスライドに埋め込んでいく。しかしもうかなり眠い。2時間弱頑張ったあたりで、もう寝て明日起きて完成させたほうが良いと考えるようになった。

寝る前に日記を書き上げて投稿しようと思ったら、昨日のABC-Hの分から書いていなかったので、+1時間くらい踏ん張る羽目になった。日曜日の部分はかなり頭が回っていない状態で書いており、書き残したいことの集合を日本語の文章にまとめる方法が全然思いつかず、苦労した。