10/24(月)

午後4時起床。余裕をもって定例会に参加できた。

今日報告できる進捗は先週水曜日に書いたコードと金曜日の1on1の内容。言葉でまとめると簡潔になるが、実際のところ普段よりかなりコードを書いたなという感触があるため、自信を持って発表できた。といっても週に二日も働いていない。

勉強会は圧縮アルゴリズムの話。アルゴリズムが小さなデータにおいて解説されるときは非常に細かい改善に見えていたものも、ちゃんとデータが大きくなるにつれてスケールしていくのが興味深かった。例えば、4bitで $0\dots 15$ を表すのではなくそこに来る数が $1$ 以上なので $1\dots 16$ を表すことにする、と聞くと微妙な感じがするが、入力が大きくなればもっと大きな数になるとわかってもっとずらせると聞くと確かに効果がありそうな気がしてきた。

会議を終えて午後8時に先週の週記を投稿。今週もこまめに書いておいたので、もう校閲まで済ませてある。

やる気が出ず、微妙な眠気を抱えながらYouTubeで2時間ほど溶かしてしまった。シャワーを浴びて気分を切り替え明日のセミナーの準備に取り掛かる。

先週日曜日の日記に、用語の定義を間違えていて予習がやり直しになったと書いた。実はこのやり直しが終わっていない。しかしいざ切羽詰まってみると案外進むもので、数時間かけながらも発表予定の範囲を一通り理解して行間を埋めることができた。尻に火が付いたからというより、単に紙に示したいこと・示したことをまとめながら読んだのがよかっただけかも。寝っ転がって頭で考えるだけではメモリ的な意味で無理があったようだ。

予習しながらまとめた命題リストを見てどの順番で話していくか考え、原稿を作る。方針をメモしただけの証明を肉付けするのもこの部分で行った。一度概観しておくと、似たような議論を繰り返す部分をあらかじめ補題に抜き出しておけたりして、かなり書きやすかった。急がば回れと言うし、時間に余裕がないときでも下書きしてから原稿を作るようにしたほうがよさそう。

午前4時過ぎに何とか完成。食事して午前5時就寝。

10/25(火)

午前9時起床。チンタラ準備していたら学食に寄る時間がなくなった。コンビニでゼリー飲料だけ買いつつ大学へ向かう。今日は午前10時からセミナー。

午前中は同級生の発表。前回の発表が先々週ということで記憶があやふやな上、その先々週は時間が足りず発表されていなかった（はず）のところをスキップして次の部分に入っていたため、ちょっとついていくのに苦労した。自分の早とちりで存在しない間違いを指摘してしまったりと大変。内容も難しくなってきている。

これが午後0時半くらいに終了し、購買に駆け込んで昼食を確保。食事して午後1時から2時間は自分の発表だった。

黒板の使い方は自分なりに考えてやっていけたと思う。後々使うことは左に寄せて書き、右に証明を書いては消し、書いては消しとする。その証明自体は、グラフの性質を正確に見ていこうとした結果記号が乱舞して、確かに初見ではわかりにくくなってしまったかもしれない。細かい話は教科書を読んでいる自分が理解していればよくて、発表時は多少なりともイメージに頼るべきか。

一つ、証明できたと思っていたところができていないのに説明の最中に気づいて、黒板の前で少し固まってしまった。少し考えたら議論が完成したのでボヤ程度の出火。しかし上手く証明がつけられたのは偶然というか、その場で閃きがあったからこそなので、本当に危ないところだった。

今日の最後はD3の方の発表。前回の続きっぽいイントロから式変形に入ったところで、不等号の周りの変形が符号によっては怪しいことを発見。指摘して議論していたら、教室に留学生の方が二人ほどやってこられた。どうやら指導教員の先生の講義を受講していて、レポート問題の質問があるらしい。ちょうど発表も止まっているのでその質問に全員で取り組むことになった。先週のセミナーで解いていたもの。

先生が講義で使用するスライドに載せられた演習問題を解いて議論していた。
週記（2022/10/17-2022/10/23） - kotatsugameの日記

最初は交代で話すのを他の人が聞くスタイルだったのに、いつの間にか1対1が二つできていた。自分はその片方。つたない英語を紙とペンでカバーしながら四苦八苦しつつ解き進めていった。本当に伝わっているかは知らない。大まかな流れを全部説明しつつところどころで計算してもらってみたが、題意を伝えられなかったのか前提となっていてほしい知識が足りないのか、あまりうまくいかなかった。

そもそもその講義が数学科向けというわけではないので、先生もそこは織り込み済みだったのか、必要な事項が講義のスライドに全部載っていて感動した。それを探し当てて適用するのを繰り返す形に。面白いかどうかはともかく解けはする。

終えて大学を出たのが午後7時半。コンビニに寄ってパンを買い込みつつ帰宅。道中で自分の出した答えが間違っていることに気づいたため、すぐさま修正のメールを送っておいた。そんなことをしていたら食事する時間もなく、午後8時からSRM840。Roomに赤が二人しかおらず、代わりに青が大量にいた。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19471

Easyから面倒。よく見ると $N\le 10^9$ でかなり腹が立った。解法自体はUFでサイズ管理するだけなのに無駄な座圧要素が入っており本当に嫌な気持ちになる。

Medはdp。挿入dpっぽく相対的な大小関係だけ考えると、直前の値未満にいくつ空きがあるかを持つ方法が思いつく。あとは直前に増加しているか減少しているかだけで、とりあえず状態数は $O(N^2)$ になる。もう解けているだろうと見切り発車で書き始めて初めて、遷移が区間に対する加算になることに気付いたが、最後にimos法、というより単に上または下に累積和を取るだけで対応できた。

prefixとして1項以下しか与えられなかった場合、直前に増加しているか減少しているかわからないため、両方に1代入しておくのが初期状態となる。 $N=1$ のときこれを両方カウントしてしまうことに気づいて、最初に弾いておくことにした。このケースはチャレンジできそうなので覚えておく。

Hardは乱択。とりあえず $S$ としては $N=2P^K$ と互いに素なものだけ考えてよい。 $S$ のべき乗が初めて1になるまで辿る値の総和ということで、とりあえず個数を考えてみることにした。カーマイケルの定理によれば $\lambda(N)=P^{K-1}(P-1)$ 乗すれば必ず1になるらしい。

適当に選んだらこのくらいの周期を持つものが出てきそうに見える。しかし本当にそれが最大か、実は周期の長さが同じでも辿る値が異なるものがあるのではないかと結局よくわからなかったので、今度は実験することにした。

適当な $(P,K)$ を選び、 $S$ の候補すべてについてどの値を辿るか見てみる。すると、周期の長さと辿る値が完全に対応していることが分かった。また周期が最大の $\lambda(N)$ のものは他の周期の倍くらいの数を辿っているため、明らかに総和も最大になりそう。実際試した範囲では最大だったから、周期が $\lambda(N)$ のものの存在を信じたうえでどうにか見つけて答えることにした。

これは乱択が十分高速に動作するはず。 $2$ でも $P$ でも割り切れない数 $S$ をランダムに持ってきて周期の条件をチェックする。周期は $\lambda(N)$ の約数なので、約数で全探索することでも行えるが、実際には $\lambda(N)$ の各素因数 $p$ について $\lambda(N)/p$ 乗して1にならないか調べるだけでよい。これは原始根を求めるときのテク。

チャレンジフェーズでは上に書いたケースでMedを一つ落とした。システスはHardが落ち、6位。レートは2807→2829(+22)でしょっぱい。

Hardのミスは、 $\bmod$ が $10^{14}$ オーダーのため掛け算がlong longでもオーバーフローすることに起因するものだった。当然そんなことはわかっていたのだが、何を考えていたのか__int128_tではなく__int64_tを使っていた。これはひどい。

Hardの背景には、 $\mathbb{Z}/N\mathbb{Z}$ の可逆元の集合 $(\mathbb{Z}/N\mathbb{Z})^{\times}$ が乗法を演算として巡回群になるという定理があるらしい。そのような $N$ の形は限られており、その一つが $2P^K$ のようだ。周期 $\lambda(N)$ の数の存在さえ信じられれば、 $\left|(\mathbb{Z}/N\mathbb{Z})^{\times}\right|=\phi(N)=\lambda(N)$ ということからその数が $(\mathbb{Z}/N\mathbb{Z})^{\times}$ を全部辿って、当然総和も最大になることがわかる。

integers.hatenablog.com

しばらくコードゴルフしつつYouTubeを見ていた。ちょうどプレミア公開されていたにじバラ #39。

www.youtube.com

屋外のロケだとVTuberが現実に居るという「存在感」があっていいなあと思いながら見ていたら、テントを張るシーンで内側に明らかに人がいるのが見て取れてびっくりした。22分56秒時点。ろふまおの屋外ロケでは影すら写さないよう徹底していたので、こういうシーンがカットされないのは驚き。3Dモデルではなくパネルを置いて撮影しているのも含め、ちょっと適当なのがにじバラっぽさなのだろうか、それにしたって危険じゃないかと心配してしまう。

https://www.youtube.com/watch?v=f2gNxg9w6BM&t=1376s

日記を書いて午前4時半就寝。

10/26(水)

午後1時くらいに起床。生命情報システム科学という講義で木曜日が期限のレポート課題を課されているため、その講義スライド3回分を布団で読んでいた。

2回目の講義でDNAのアラインメントを行ういくつかのアルゴリズムが紹介されて、特にdpによるものは疑似コードまで載っており、AtCoderで予習済みと思ってニコニコしていた。しかし3回目の講義に入るともうアルゴリズムの話は影も形もない。残念。生物学的な知識が足りないのか読んでも全然頭に入ってこないので、今はとりあえず最後まで目を通すことを目標とした。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

それを終えて午後3時過ぎに布団から脱出。しばらくコードゴルフして、午後5時前に外出した。ゲーセンに向かう。

10/13に大型アップデートがあってから初めてのゲーセンということで、今日はほぼずっと新曲を埋めていた。高難度にいくつかやり残したものがある状態で閉店。成果としては、14+で詰めた2曲でSSS+とSSS+寸が出て、あとは「トンデモワンダーズ」で理論値が出せた。

トンデモワンダーズ　理論値！！！！！！！ pic.twitter.com/Idb6TvgGev
— こたつがめ (@kotatsugame_t) 2022年10月26日

以前の日記にも書いた通り非常に好きな曲なので狙ってみた。とはいえまさか13+でこうもうまく出せるとは。譜面のどの部分も安定しなかったが、特に中盤とラストにある変なリズムの部分が苦手なので、これは期待薄かなと思いながらプレイしていたところ、4落ちから急に全部揃った。

トンデモワンダーズが収録されるらしい。かなり好きな曲なので最高。
週記（2022/10/10-2022/10/16） - kotatsugameの日記

その理論値を含め手元動画をいくつか撮っていたので、帰宅してから投稿した。店に1台アーム付きの筐体が用意されていたので、自前のスマホアームではなくそれを使用した。ちゃんと画面上端からスライダーの下まで画角に収められ、いい感じ。

トンデモワンダーズ理論値手元 pic.twitter.com/LVlYuHoe2L
— こたつがめ (@kotatsugame_t) 2022年10月26日

しばらくなろうの読み返しに時間を費やした後、10月・11月に刊行される本をチェックして注文した。20冊。最初はあまり新シリーズに手を出さないように心掛けていたが、物足りなさを感じてしまいどんどん基準が緩くなって結局普段通りの冊数になった。

リストを眺めていると見覚えのある単語が目に飛び込んできた。昨年末読んだなろうが書籍化するらしい。予約しておいた。

なろうを1作読了。「鷹は瑞穂の空を飛ぶ～プラスチックの専門家が華族の娘に転生したので日本は化学立国になります～」。
週記（2021/12/13-2021/12/19） - kotatsugameの日記

https://t.co/ugNdeSQ0xX
「【旧題：鷹は瑞穂の空を飛ぶ】令和の化学者・鷹司耀子の帝都転生　～プラスチック素材で日本を救う～」更新しました！
書影が公開されました！野上武志先生の素晴らしい表紙にビビッと来たら、ぜひ予約注文をお願いします！https://t.co/5CkCE4OCkT pic.twitter.com/jOivXP0vYM
— 雨堤俊次/コモンレール (@commonkryng) 2022年10月21日

「ifの世界線」というSFアンソロジーが出版されていた。宮内悠介さんの名前があるのに惹かれてあらすじなどを確認していると、なんとVTuberでびでび・でびるさんの推薦コメントがあるのを見つけた。これも購入。

【発売まであと5日】
『ifの世界線　改変歴史SFアンソロジー』

いかいのとびらがひらかれた……でびでび・でびるさま（ @debidebiru_sama ）より伴名練さん「二〇〇〇一周目のジャンヌ」へのコメントをいただきました。世にも恐ろしい推薦文をご覧ください。#ifの世界線 #10月14日発売予定 pic.twitter.com/jjWpqBUXDR
— 講談社タイガ (@kodansha_taiga) 2022年10月9日

午前6時就寝。

10/27(木)

午後2時起床。昨日書籍化を知ったなろうは、昨年末に一気読みしてから開いていなかったので更新が溜まっていた。しばらく布団の中でそれを読んでいた。

午後3時半ごろに布団を脱出し、TAのため大学に向かった。生協でラノベを買いつつ教室へ。今日発表分の資料がまだ共有されておらず、明日から学祭だからもしかして休みかもと思っていたが、普段ととくに変わりなく行われるらしい。資料も共有されていないだけで作成済みだった。

何を話すか知らない状態で今日の発表を聞くことになったが、普通そういうものか。内容についてはしっかり完成されていて良かった。その場では言うべきことがほぼ見当たらない。単に座って普通の学生と同様に話を聞いているだけだった。普段からこういう業務だと楽だなと思ったものの、今度はそれで給料を貰うことに耐えられないので、良し悪しといったところ。

講義後先生が質問対応をされていたからか、自分にも質問が来た。先生が講義でたびたび話題に出しておられた群論と今扱っている多面体の関係について。二面体群の話を例に挙げればいいかなと思ったら、空ではうまく言えず愕然としてしまった。後半はもっと大まかな話になって、自分の好きなことをいろいろ喋り散らかしたが、質問に答えるという点では褒められたものではなかったと自省している。

学食で食事し、学祭の準備で活気づく大学を背に午後7時帰宅。

しばらくコードゴルフしてからレポートに取り掛かった。水曜日の昼過ぎに読んでいたスライドのもの。改めて読解に挑戦するも相変わらずよくわからない。Rのパッケージを用いてプログラムを書くという課題もあって、こちらは環境とデータさえ用意すればチュートリアルに従うだけでそれなりに形になりそうだったので手を出してみたものの、肝心のパッケージを動かすためにUbuntuに入るRより先のバージョンが必要だと知った。

手動でアップデートしてもよかったが、慣れないことをすると罠にハマりそう。おとなしく通常の課題に取り組むことにした。まずRで行うはずだったことをWebサイト上で行う。この部分はある程度わかっていて、ただし得られたものを見ての考察ができない。時間いっぱい格闘して何とか文章は書けたが頓珍漢な内容だったら恥ずかしいなという気持ちがある。ともかく提出には成功した。

解放感からハーメルンを開き、1作読了。「ようこそクズヒモ男の教室へ」。

syosetu.org

もうよう実原作のハーメルンも数作目だから展開を覚えてしまって、ちょっと申し訳ない気持ちにはなるもののその分スムーズに読めるようになった。個人的にAクラススタートの設定のほうが最初から盛大に動けて好きで、Dクラススタートのこの作品もどうせAクラスの人間と深い仲なら主人公もそちらに合わせてしまえばいいのにと思っていたが、今のままで十分面白い。まだAクラスと対決するシーンまで進んでいないので、その深い仲のキャラはクラス対抗にはあまり顔を出していない。これからが楽しみ。

午前4時から4時間ほどインターンのためのコードを書いた。以前から話題にしていたコードの書き直しについて、とりあえず一通り終わらせることに成功。ようやく出力物が得られるようになったので、以前のコードで作ったものと比較するプログラムも整えて、チェックしておいた。おおむね合っており盛大にバグっているということはなさそう。細かい違いの原因を探すのはまた今度にする。

コードが動くことは確認できても、出力を生成する段階まで書き直し終えないと正しく動いているかどうかがわからないのはちょっと困る。また出力が得られたとして、その形式がこれまでと変わっているので、比較する方法についても考えなければならない。
週記（2022/10/17-2022/10/23） - kotatsugameの日記

布団に入り、今日起きた後に読んでいたなろうの続きに取り掛かって午前10時くらいに最新話に追いついた。戦争部分は主人公の出番が少なくちょっと物足りなかったが、章が変わって自動車の話になると出ずっぱりになったため、満足。

https://ncode.syosetu.com/n1453gs/

午前10時半就寝。

10/28(金)

午後3時過ぎ起床。今日予定されていた1on1は午後2時からということで、つまり盛大な寝坊である。

インターンを開始して1年が経過し初めてやらかしてしまった。午後1時半くらいの目覚ましで目を覚ました記憶はあるが、45分あたりにも目覚ましをかけているからということでうっかり二度寝に入ってしまい、それが思ったより深かった。最近は緊張感が薄れてしまったのかこういうギリギリを攻めることが多くて、だからいずれ訪れる破滅だったのだろう。Slackで平謝り。1on1は今日これからではなく別日に行うことになった。

正直まだ眠いため、その後も布団にいた。しばらくなろうを読んで午後5時に寝落ち。午後8時半に再度起床した。

少しコードゴルフして午後9時20分からyukicoder 366。

yukicoder contest 366 - yukicoder

今日のセットではEのテスターをしているから、まずその話をしておきたい。下に引用した日記で言及していた問題がこれだ。もともと星3.5ということで依頼を受けており、その時は解法が結構ごつく制約も少し小さいものだった。提出一覧の底のほうに名残がある。ところが今の解法で解けたため、制約を上げて星を減らすことになった。

減らすといってもいくつにするかは判断が難しいところ。個人的には星3弱という評価をしていた。しかしこれは自分がすんなり思いつけたからであって、タイミングによってはとことんハマってしまいそうな問題。結果としてはsolved数の逆転も起きなかったため安心した。

TLにyukicoderのテスター依頼が流れてきたので、引き受けてしばらく取り組んでいた。
週記（2022/10/03-2022/10/09） - kotatsugameの日記

そのほかの問題について。Aは面倒。何気にFAを取っていた。Bは貪欲。 $1+1$ と $0+2$ をできるだけ作って、あとはよしなにする。きちんと証明しなかった。Cは $a_j'$ と $a_{j+1}'$ を固定し、それが部分列として連続して現れる場合の数を考えた。 $a_j'$ のほうを場合の数ごとまとめて計算することで線形時間になる。そもそも求める値が $a_1'-a_k'$ であることにすら気づいていなかった。

Dは難しくかなり時間を使った。マスを一つ飛ばしに見た時の値の差などに注意して条件をいろいろ考えていたが、最終的にはほぼ直感。一番上の行に左から一つ飛ばしで連番を埋め、一番下の行で先ほど埋めなかった列を右から見てまた連番を埋める。これを上下ともに2行ずつずらしながら行うと行が一つ飛ばしで埋まる。間の行に対しても同じことを、今度は左右を逆にして行うと、見事にすべてのケースで正しい答えが得られている。

Fに取り組むも解けず、5完。最小費用流が当然のようにTLEしたので、ソートして貪欲っぽく解こうと頑張っていた。

また少しコードゴルフしていたが、すぐになろうに手を出してしまう。椅子に座っているのも疲れて布団にダイブし、寝落ちしそうになりながら昼前までずっと読み続けていた。午前10時くらいになって身を起こし、シャワーを浴びて日記を書き、午後1時前に就寝。

10/29(土)

午後5時半起床。

CFに向けた準備をしていたらWindows Updateの通知が来ているのに気付いた。考察の途中に再起動されても困るので、コンテスト開始まで残り10分を切った状態でUpdate開始。幸い特に時間がかかることもなくすぐ復帰できた。

午後6時からCF #831 combined。スタートは正確には午後6時5分、またコンテスト時間が2時間45分ということで、ただでさえABCとのインターバルが10分しかなかったのに、直前で5分こどふぉったためもっとひどいことになった。ABC Unratedの身としては逆に楽しくなってくる。

Dashboard - Codeforces Round #831 (Div. 1 + Div. 2) - Codeforces

Aは $n=2$ は適当に、それ以外は偶数を作ればよい。Bは $a$ と $b$ を適当にswapした後 $\sum a+\max b$ を最小化する問題。常に $a\le b$ となるようにswapして損しない。こう言えば証明の方針もすぐわかるが、コンテスト中は $\max b$ を最大化する方面から考えてしまったためうまく示せず、よくわからないまま提出してしまった。

Cは謎。 $a$ がソート済みとして、とりあえず $|w_1-w_2|$ を $a_n-a_1$ にはできるらしい。そのとき $|w_2-w_3|$ を $a_2-a_1$ または $a_n-a_{n-1}$ にできたので、大きいほうを出力してみた。WA。しばらく考えて、あえて $a_n$ ではなく中途半端な位置の値を使い $(a_k-a_1)+(a_k-a_{k-1})$ 、あるいは $(a_n-a_k)+(a_{k+1}-a_k)$ にしたほうが得する場合があることに気づき、再度提出してACした。

コンテスト中は正当性を示さなかったが、今考えれば $w_2$ を全探索していたのだとわかる。答えを $a_n-a_1$ 以上にするためには $w_1,w_3\le w_2$ か $w_1,w_3\ge w_2$ である必要があって、それぞれの最適値が上に書いた値となる。

Dも謎。 $(1,1),(n,m)$ のほかに1マス空きがあればその空きマスを自由に動かせるらしい。なので、各値を $(n,m)$ に入れる直前にはどれだけの値を $(1,1)$ から外に出しておかなければならないのか求め、その個数が $NM-3$ を超えないかチェックすればよい。空きマスが1行＋1列必要だと勘違いして1WA。

Eは木dp。挿入dpっぽく大小関係だけ考えることにする。あるノード以下の部分木から作れる非減少部分列は、そのノードを含むか含まないかで二通りに分けられる。前者は葉まで一直線のパス上のノードしか使わない場合。後者はそれ以下のどこかで枝分かれがある。これまで枝分かれがあったかどうかを状態に持てばよい。

Fは難しかった。まず状態をどうやって表すか考える。完全にエスパーで、これまで作った集合の個数 $c$ とそのサイズの和 $s$ を持てば、次にどんなサイズの集合まで作れるか計算できると思った。試したところ正しそう。あらかじめ全 $(c,s)$ について $O(n^2)$ で前計算しておき、これを使ってdpする。dpは、使うサイズ $t$ を降順に決めつつ、 $(c,s)$ を状態として遷移していくもの。ただし $ct\le n$ である範囲しか見なくてよいため、ループが $O(n^2\log n)$ になる。

問題は前計算の部分。1回以上現れる要素だけ考えた時の頻度配列を $V$ とすると、状態 $(c,s)$ では各 $v\in V$ について $\min(v,c)$ 以下だけ $s$ に寄与していると考えられる。寄与の和が $s$ 、あるいは $s$ 以上となる条件下で、寄与を引いてもまだ余る $v$ の個数をできるだけ多くしたい。

$c\lt v$ のときは最大の $c$ 寄与するとして問題ない。 $c\ge v$ のときは、まず $v-1$ だけ寄与していると思って起き、 $s$ に足りない分だけそこから追加で1引っ張ってくるのが最適。これで、 $c$ ごとに $O(n)$ の計算を行えば状態 $(c,\ast)$ に関する値が求められて、十分高速になった。

ところがこれは日記を書いている途中に整理したものであって、本番はもうちょっと面倒なことをしていた。余らせるのを1以下に固定してよいことに気づかず、最初は二分探索、後から $s$ を動かしながら線形探索で求めている。1余らせていては足りない場合の計算は、高速化しないと間に合わなかったので、考察を進めて上と同じものを導いた。

Gには30分弱残した。 $s$ の小さいほうから見て順に $t$ を決めればすべてgoodにできるはずだとわかり、その時必要な隣接関係の管理にはDancing Linksっぽいものが使えそうというところまでたどり着いた。しかし実装してみるとサンプル1すら合わず、デバッグの時間もほぼなくそのままコンテスト終了。

ABCまでのインターバル5分ではシステスが終わるはずもないが、日記だからここに結果を書いておく。6完62位で2668→2678(+10)。しょっぱい。しかしpredictorでは壊れていたのか-30以下を示していたため、得した気持ちになった。

午後9時からABC275。

AtCoder Beginner Contest 275 - AtCoder

Aからちょっと面倒。短い書き方がすぐ出せないのでC++で解き、縮めようとせずBに進んだ。Bはdcで一発。慌てて提出した。

Cはちょっと難しい。正方形の角2点を全探索し、そこから座標の足し引きでもう2点を探す。2種類あるが素直に計算していると特定の一方のみが見つかる。この4点をチェックして正方形をカウントすると同じものが4回数えられるため、最後に4で割って出力した。

Dは2と3が分母に来る分数を切り捨てた値しか使わないため、メモ化再帰。EとFはdp。今回はこの3問が非常に簡単だったため調子に乗っていたら、Gで思いっきり詰まってしまった。

G。とりあえず答えの初期値を $\max_i C_i/\max(A_i,B_i)$ としておく。あとは2種類以上の商品を使う場合だが、特に $A_i\gt B_i$ と $A_i\lt B_i$ から1種類ずつ使うのだろうとエスパーした。この二つをうまく組み合わせることで、重さと体積の合計を等しくできるからである。

実際に計算してみる。使う商品を $(A_1,B_1,C_1)$ 、 $(A_2,B_2,C_2)$ と固定して、 $A_1\gt B_1$ かつ $A_2\lt B_2$ という仮定もおく。すると前者を $B_2-A_2$ 個、後者を $A_1-B_1$ 個だけ集めたものがピッタリになる。それで得られる価値を重さまたは体積の合計で割ったものが $\frac{C_1(B_2-A_2)+C_2(A_1-B_1)}{A_1B_2-A_2B_1}$ 。これを $f(X)/X$ だと思って最大化したい。

式変形と変数の置き換えを繰り返し、何とか解けそうな形まで持っていった。まず分母分子を $A_2B_1$ で割ってみる。 $x_1=A_1/B_1-1,y_1=C_1/B_1,x_2=B_2/A_2-1,y_2=C_2/A_2$ と定めると、 $\frac{y_1x_2+y_2x_1}{x_1x_2+x_1+x_2}$ になる。さらに分母分子を $x_1x_2$ で割り、 $i=1,2$ について $x_i'=1/x_i,y_i'=y_i/x_i$ と定めることで、 $\frac{y_1'+y_2'}{1+x_1'+x_2'}$ まで単純化できた。

$(x_1',y_1')$ を全探索し、 $(x_2',y_2')$ を $y_2'/x_2'$ が最大となるものとして定めればよさそうに見えたが、WA。適当に乱択しても当然通らない。そこで、 $x_i'\leftarrow x_i'+1/2$ と改めて置きなおし、 $\frac{y_1'+y_2'}{x_1'+x_2'}$ にして同じ方法で最大化を試みたところ、見事通った。

時間がなかったのでExはあまり考えず、コードゴルフにかまけていた。7完54位。Gは $\frac{y_1'+y_2'}{x_1'+x_2'}$ までたどり着けたら二分探索で容易に答えが出る問題だということに気づけなかった。品物を高々2種類しか使わないことについては相変わらずよくわからない。少なくとも、自分は極限をうまく言い換えられていなかったようだ。

コードゴルフ。AはVimで、入力を1行1要素に直す部分でいつものテクを忘れており負け。Bは最初に提出した特に工夫のないdcコードが今のところ最短らしい。DはRuby。EもRubyで、こちらは負け。他は手付かず。

今日もまた布団に横たわってなろうを読んでいたが、今度は午前6時前に脱出することに成功した。しばらくYouTubeを見た後、日記を書き、布団に戻って再度なろうに手を出す。午前10時くらいに寝落ちした。

10/30(日)

午後2時45分起床。気合いで身を起こし、午後3時からAHC015に出た。

TOYOTA MOTOR CORPORATION Programming Contest 2022（AtCoder Heuristic Contest 015） - AtCoder

開始後しばらくはコードゴルフをしていた。yesコマンドを使って出力。最初に提出したものではちゃんと99個で出力を終えていたが、その後無限に出力するコードでも通った。

その後シャワーを浴びたりしつつ考えをまとめ、真面目に取り組んだ。箱を傾ける関数、スコアを計算する関数、先読みする再帰関数などを実装し、開始2時間くらいで「1回操作するたびにその2手先の評価値の期待値を最大化する」コードが完成した。これが134.4M。直後、終盤4分の1くらいは3手先を読むようにしたものが136.9Mとなった。

終盤で3手先を読むターンが増えればスコアも上がるらしいので、ここから1時間以上かけて高速化を図った。次のキャンディーが来る位置を全探索した後傾けるのではなく、一度傾けた箱の状態を少しずつ書き換えるようにして、シード値0で常に3手読むのにかかる時間を10秒から9秒に短縮。しかし焼け石に水。

一部やたら動作が遅いケースがあるようで、それに合わせると他のケースのスコアも落ちてしまう。よって内部で時間を計りながら方針を切り替えるしかない。10回に1回3手読んでみて、その時間をこれから毎ターン使っても間に合うか判定。138.6Mになった。ほかのチェックもいくつか試してみたものの、結局これが最高スコア。

正確には138649423点で31位、パフォーマンス2411、レートは1911→2031(+120)。Heuristic黄色になれた。

この問題は、移動させることによって空いた空間に次のキャンディーを入れると認識するのがよかったらしい。3種類のキャンディーをそれぞれどの端に集まるか決めて、次のキャンディーが入る空間を空けるように操作するという貪欲解法で、自分の最高スコアに近い値が出せるようだ。

[AHC015]
下・右・左に集める色を決める。
・次が下に集めるものなら上に寄せる
・右・左に集めるものなら、いま上に寄っているなら下に、そうでなければそれぞれ左・右に寄せる
この貪欲？が1投目の138M
これに毎ターンモンテカルロして期待値最大の行動をするようにして150Mくらい
あとは調整
— tomerun (@tomerun) 2022年10月30日

午後11時くらいまでなろうを読んだ後は朝方まで日記を書いていた。その間にやっていたことをいくつか。

まず、土曜日のCF-Gをupsolveした。コンテスト中に考えた方針は合っていた。ポータル同士の隣接関係について、ある面から別のある面にたどり着けるとしてもその逆が成り立たないことが問題。ポータル内部でレーザーが曲がるとこれがずれてしまう。各面に対し、そこに入ってくるレーザーがどこから来たかと出ていくレーザーがどこに行くかを区別して持ったら解決した。サンプルを手で試す時間があれば解けたと思う。

Submission #178614438 - Codeforces

ハーメルンを2作読了。

syosetu.org

「蹄物語」。阿良々木暦視点だと地の文が長すぎてあまり話が進まないため内容はまだよくわからない。化物語シリーズっぽい、あるいは西尾維新っぽい文章を書こうとしているのは感じ取れて、おおむね成功しているのではないかと思う。

syosetu.org

「俺の家に巫女がいる」。完結済み。博麗霊夢と同棲と聞いてウキウキしていたらシリアスだった。展開の謎は最終話までに回収されたが、主人公の設定はよくわからないまま終わってしまった。

午前6時くらいに切り上げて布団に入り、ハーメルンを読み始めた。これがあまりに面白くて睡眠に失敗。週が変わるため一応このあたりで日記も日付を変えておくが、実際はそのまま徹夜で月曜日に突入した。