週記（2021/04/19-2021/04/25）

04/19(月)

先週のぶんの週記を投稿してからの話。最後に書いていたARC117Cの最短コードは、エンコードするところでさらに更新できた。ord^5は天才的だが、tr RWB 012をするのでもよくて、ここで'R'はわざわざ置換しなくてもよい。結局tr WB 12になった。

月曜日の夜はサークルの解説会だ。今週からしばらくは新歓イベントのつもりで、MeetのURLを外部に公開する予定になっている。しかし肝心かなめの解説役がまだ1問・1人しかいない！僕も解説をしようと思って、ABC198のE問題を選んだ。ところで、この問題はマージテクで解けないだろうか？map<int,vector<int> >と持ってみて、mapのマージとvectorのマージの両方でマージテクを使うようなコードを書いたら、2ケースTLEしてしまった。テストケースの名前を見ると、スターグラフの時に落ちているらしい。なぜダメなのかわからないのでしばらく考えていたが、そのうちに椅子の上で寝てしまった。

首の痛さで起きる。今は諦めて一旦寝ることにする。布団に入ってから少しだけなろうを読んだ。土曜日に読み始めたと言及した作品だが、今はもう興味が薄れてきてしまっている。これの読了についてはあきらめることにして、ブラウザのタブを閉じてしまった。午前10時就寝。

午後6時と6時半の目覚ましでは起きられず、午後7時にようやく起床。相変わらず解説会用のスライドは手付かずなのに、残り1時間しかない。困った。とりあえずホスフィンに頼み込んで1問担当してもらうことにして何とか体裁を整える。自分はE問題の解説スライドを作る。ところで、マージテクで解くことについてはまだ諦めておらず、寝ている間に新たな方針を思いついていた。multimap<int,int>で持つというもので、こちらだとちゃんとACできた。そこそこ面白いと感じられるので、これもスライドに載せておこう。

なんとか完成して、解説会が始まる。10人以上が参加してくれていて、ありがたい限り。外部の参加者とサークルメンバーが半々くらいか？

まずホスフィンがABC198Cを解説する。直前に無理を言って作ってもらったとは思えない出来。この流れで僕も……！と勢い込んでE問題の解説を始める。まず問題文を読む。

「N頂点からなる木が与えられます」

え？

初見の人もいるのに「木」は、ダメだろ。慌てて何とか説明をしようとしたはずだが、正直頭が真っ白になっていて何も覚えていない。サンプルに図がついていなかったのでマウスとペイントで書いたが、書いている間の微妙な時間が耐え難かった。何とかスライドを最後まで読んだものの、1ミリも伝わった気はしない。

最後にsotanishyさんによってF問題の解説が行われた。こちらは計算がゴツいものの、競プロをやっていない人にも伝わるような問題だったし、解説もそうだった。見返してみればD問題もプログラムで覆面算を解くといういかにも面白そうな問題だったから、こちらを解説しておけばよかったものを、なぜE問題というグラフ理論の用語がバリバリに使われた問題を選択してしまったのか……。

ECR16のABを解いて時間をつぶし、CF #716 div.2に出た。4完遅解きでひどい順位だった。

Aは平方数でない数があればYES。BはNK。Cは難しい。必死に実験すると、gcd(N,i)==1なるiを集めてきて、総積が1にならなかったらN-1を外す、という感じのようだったので実装したら通った。gcd(N,i)==1なるiを集めてくることまでは普通にわかるべきらしくて、このとき総積pはgcd(N,p)==1を満たすから、p!=1のときはpを外す、というのがTLでよく見られた解法だった。pが1またはN-1であることも証明できるらしい。

inamori.hateblo.jp

DはMo's algorithmとSegment treeで書いたら当然のようにTLEしたので乱択。wikipediaからxorshiftをコピペして提出すると通った。そのあとE問題を考えながら30分くらい椅子に突き刺さって寝ていたが、ふと起きるとDがHackされていた。xorshiftが固定シードだったのを狙われたらしい。気づいた瞬間は乱択を落とす暇人にキレていたが、冷静になるとxorshiftの最初の30回くらいの値を見るだけで簡単に落とせることに気づいたので、反省。現在時刻をシードにしたmt19937で出しなおした。速度的にちょっと不安があったが、xorshiftと比べて悪化しているようには見えない。まあ同じループでlogオーダーの処理をしているので、そちらが支配的なだけか。

Eは、（コンテストの時はうろ覚えでここまではっきり名前がわかっていたわけではないが）トーナメントグラフの場合a->bという辺があるかどうかを比較関数にしてソートするだけでハミルトン路が得られる、という話を覚えていたので、その方針で考えてみることにした。これだと1つ目の質問はn \log n回必要で、9nと比較してあまり余裕はない。問題を解くにはハミルトン路においてどこまで戻れるかを求めなければならないので、2つ目の質問を2n回行うだけでそれを知らなければならない。適当に二分探索したら落ちたが、二分探索する前に「そもそも戻る辺があるか」を各頂点で1回かけてチェックしたらpretestに通った。

わくわくしていたらシステムテストで落ちた。解説を読むと、二分探索ではなく尺取り法をすればよかったらしい。これは非常に悔しい。思いつけてもよかったが、そもそも前提となるハミルトン路の作り方さえあいまいなままだったので、自信をもって考察を進めていくことができなかったということだろう。

午前2時くらいに寝落ち。

04/20(火)

午前5時半起床。布団でノクターンノベルズを読んでいた。

https://novel18.syosetu.com/n7518em/

ARC117Cがさらに縮んだ。3つおきに取るのと隣り合う2項を足して符号反転するのを行っていたが、3つおきに取ったとき、さらに隣り合う2項を足して符号反転するところまでやってしまうようにしたところ、コードの大部分を共通化できた。

また布団に戻ってなろうを読んでいたが、午後2時半くらいに寝落ちした。

https://ncode.syosetu.com/n5465fc/

午後9時半起床。競プロ典型90問のコンテストがスタートしていたのと、「えびまのお誕生日コンテスト 2021 Day 1」も始まっていた。

atcoder.jp

お誕生日コンテストの問題を読んでみたところ、どれも普通の問題のように見える。後から気づいたことだが、「お誕生日」の問題はDay 2に隔離されたらしい。言われて初めていつの間にか2日制になっていたことに気づいた。

A問題は解けそうなので布団でスマホコーディングした。答えを最大化しようとしたり、中途半端に修正したり、違う値を出力したりして3WA。Bはよくわからなかったのでまた布団をひっかぶってモゾモゾしていたが、しばらくしてなんとなく実験する気になったのでパソコンの前に移動した。実験するとフラクタルな構造になっているようだ。例えばK=3だと、3で割って2余るものや、9で割って6以上余るもの、27で割って18以上余るもの……等々は消えて、それ以外は残る。適当に実装してみたら一発で合った。解説によるとK進数として見れば示せるらしい。

さらにE問題が解かれていたので、読んだ。前から順に合わせていくことを考えて、バブルソートのように隣り合う要素を交換していくのかとも思ったが、いくらか飛ばして大きなものを後ろに持っていくように交換するとさらにコストが小さくなることに気づいた。それで実装してみるとACした。未証明。TLで見かけた説明だが、このような交換では互いにあるべき相対位置に近づいているので損していない、と考えると納得できそう。

D問題を読んだ。あるkについてA_i-A_j=k(j-i)、つまりA_i+ki=A_j+kjとなるペアを数える問題のようだ。うまくiとjを分離できているので、kを全探索することを考えたいが、これはできない。そこで最初の式に戻ってみると、kがある程度大きいときはj-i（の絶対値）が小さくなることがわかる。よって、平方根のあたりで分割して小さいほうを全探索すれば間に合う。A_i+kiの重複カウントにmapを使ったらTLEしたが、ソートしてランレングス圧縮する方針で書いたら余裕を持って通った。

結局4完。最初から真面目に出ていたらCも解けたのだろうか。解説を見ると、あんまり見たことがない添え字の持ち方をするDPのようだ。

論理学の履修制限について。結局04/16(金)までに履修登録したことが履修する必要十分条件となったらしい。僕はちょうどその金曜日に履修登録していたので、何とか滑り込めた。

競プロ典型90問のコンテストを埋め始めた。

コードゴルフについては特に言うことがない。そもそも問題が簡単ではないので、適当なスクリプト言語でACして、コードゴルフの定石を手癖で適用していくだけの作業が多い。

004 Cross Sumは4e6個の入力と4e6個の出力を求められて大変だった。スクリプト言語は軒並みTLEして、PyPyで何とか通した。016 Minimum Coinsも想定解が1e8回のループを求めていて大変。こちらもスクリプト言語はTLEしてしまった。

朝方、TCB35の問題を解いていた。今回は念願の理論値を達成することができた。この週記が公開されるころにはイベントが終了しているので、ここに問題の感想を書いておこう。

Aは結構謎。Bはそこそこ難しい、と思っていたが、X座標が1、2、3で固定なので、Y座標も等差数列をなしているかチェックすればよかったのか。Cは全探索。Dは重複チェック。

Eはなもりグラフのループを求める。TechFULは再帰しすぎるとREになるイメージが強かったので再帰を使わないことにし、UFでループの最後の辺u-vを検出して、それ以外の辺を使ってu->vの経路長をBFSで求めた。実は再帰でのREについてはつい最近修正されている。このことを知ってはいたが、今回は安全側に倒したということ。ちなみに後ろのほうの問題では面倒になって問答無用で再帰関数を使っている。

Fは行ごとに見て列をデータ構造で持つのが思い浮かぶが、実は座圧すれば縦横2000に収まる。Gはグラフを作ってダイクストラ。Hは最大流。IはSCCしてDAGの先頭に来る頂点だけが候補。Jは1e5以下の素数9592個をbitsetで持ってxorしていく。

今日の競プロ典型90問・20問目は、これまでで最も短く書ける問題だった。dcの16Bがほとんど明らかである。これはぜひ最短コードを取りたい。提出先URLはそれまでの問題からの類推でわかるので、ojで提出するのとsleep 15を繰り返すシェルスクリプトを作っておいた。提出に成功するとojの終了ステータスが0になるので、そのときexitする。これを、問題が公開される予定の15時の5分前から動かしておくことにした。ところが、今日は14時53分くらいに問題が公開されてしまったようで、結局僕は2分くらい遅れて提出することになってしまった。

数理統計学のレポートを提出した。その過程で、先週土曜日に提出したレポートの計算が少し違っていることに気づくも、スキャンした原本はすでに捨ててゴミ箱の底にある。PDFファイルに何か書き足すという方法もわからないので、仕方なくもう一度筆記しなおしてスキャンし、再提出した。レポートといっても1ページなので、それくらいなら何とかなる。

午後7時くらいまでパソコンでTwitterを見ていたが、いつの間にか椅子の上で眠ってしまった。30分くらいして目を覚ましたが、これ以上の活動は不可能であると判断して寝た。午後7時半だった。

04/21(水)

消えた。

04/22(木)

午前6時半起床。非常に良い。

人の週記を読んでいて思うが、やはり解いた問題、あるいはコンテスト単位でも、リンクを貼っておくのがよいのだろう。以前の記事を書き直すことはしないが、以降はコンテストリンクを貼るようにしたい。

朝は典型90問のコードゴルフをしていた。寝ている間に、僕がツイートしているコードゴルフのリプライツリーに更新情報がいくつかくっついていたので、それを何とか取り返そうとしていた。更新したものをわざわざ書き込んでくれるのはうれしい。

そのあと、今日の午後からあるゼミのために教科書を読んでいた。発表ではないからと言って気を抜いていたら当日まで手付かずのままになってしまっていた。2冊本があって、そのうち僕がメインで読み進めるほうの本の内容は手元にあり、今日進めるはずの部分まではとりあえず読めた。すでにわからない箇所を発見してしまったので、その部分の発表は入念に聞いておきたい。そのほかの部分は、初回ということもあって難しくない。

しかし、もう1冊の本はそもそもコピーすら手元にない。先々週のゼミの顔合わせの時には教科書を注文しようかとも考えていたが、なんとなく放っておいているうちに2週間が経過してしまった。仕方がないので今日は山に登って数学科の資料室に行くことにしよう。

と思って出かける準備としてシャワーを浴びたりした後、数学科資料室の入室予約をしようとページを開いたら、昼間は職員の休憩のために閉まるらしく、午前中最後の時間帯の入室予約も終了してしまっていた。失敗！出かける準備は万端だが山まで登る必要はなくなったので、川内で食事をして、一応川内の図書館で探してみることにする。

今日は気持ちのよい青空で、気温もちょうどよい。冬と夏の間にある奇跡のような1日だ。

川内に行って食事していると、昼休みに突入したらしく、大学生協の前の広場が人でごった返していた。教科書販売の列もそれなりに伸びていて、かなり危険な感じ。そそくさとその場を後にした。そのまま図書館に行ったが、検索システムがちょうどメンテナンスらしく使えなかったので、数学書の棚を愚直に探索した。ゼータ関数の本がどういうジャンルに分類されるのかもよくわかっていない。結局「有名な関数」だったかのジャンル分けがされている場所にゼータ関数の本が並んでいたが、ゼミで読む本は見つからなかった。

ゼミが始まった。手に入らなかったゼータ関数の本はイントロから積分をどっさりしていて、予習なしでは非常につらいものがあった。積分区間に無限が登場しているところの正当性など、何を示せばいいのか自分はよくわかっていないので、このままではいけないんだなあという気持ちになった。もう一方の本はそれに比べるとやはり簡単か。再序盤に1か所あったわからない箇所については発表を聞いてちゃんと解決できた。残りの部分は、今日は一生最大公約数を定義している。

ゼミが終わってからは履修登録の続きをしていた。単位的には今セメ以降何も取らなくてよいらしいが、気になったものをこれまで2つ履修登録しておいた。ほかに、数学科の7セメスターに開講される講義が複数あるので、それぞれチェックしていく。Classroomに一瞬だけ登録して講義資料を覗いたりした結果、「数学基礎論特選」というのを履修登録することにした。モデル理論？やらをするらしい。

3マスしか埋まっていない時間割を見ると動悸が激しくなる。何回も確認したし、卒業単位は十分確保してあるはずだが、やはり1年生で落とした分を必死に取り返した日々の記憶は色濃く残っており、時間割が埋まっていない状態が見慣れない。

今日は木曜日なので、論理学の講義があったらしい。講義動画を視聴してミニットペーパーを提出した。

ECR16のCからFを埋めた。

https://codeforces.com/contest/710

ABは月曜日に解いたが、そこから放置していたわけではなくて、ただただC問題が解けなかった。C問題の問題概要は以下。

奇数1\le n\le 49が与えられる。 1からn^2を1つずつn\times nの盤面に並べる方法であって、各行・各列・対角線の和がそれぞれ奇数になるようなものを1つ求めよ。

僕の解法はこのようになる：1からn^2のうち偶数であるものは\frac{n^2-1}{2}個あるが、これは奇数nの値によらず4の倍数である。偶数を4つずつ組にして、(i,j),\;(i,n-j+1),\;(n-i+1,j),\;(n-i+1,n-j+1)に置く。すると関係する行・列には偶数が2個ずつ、対角線と重なるなら対角線にも2個ずつ偶数が置かれる。よって最終的に各行・各列・対角線にあるn個の数のうち偶数個が偶数となるため、総和は奇数である。

非常に難しいと思ったが、ホスフィンによれば魔法陣を作るとそのまま答えになるらしい。これが想定解だったらキレていたところだが、想定解はちゃんと構築しているので許した。

DよりEを先に解いた。たぶん良い。何回かWAを出したが、解法自体は正しかった。逆から見るやつだと思ったが、解説では頑張って順方向にDPしている。

Dは非常に難しい。a_1,\;b_1,\;a_2,\;b_2,\;L,\;Rが与えられるので、L\le x=a_1 k+b_1=a_2 l+b_2\le R,\;k,l\ge 0なるxの個数を答えよという問題。

まずb_1\leftarrow b_1-L,\;b_2\leftarrow b_2-Lとして0\le x=a_1 k+b_1=a_2 l+b_2\le R-Lと書き直す。b_1\le b_2としても一般性を失わない。xについての式を1つにまとめたい。g:=\gcd(a_1,a_2)と置くと、b_2-b_1\not\equiv 0 \pmod{g}のとき2つの式が一致することがないことがわかる。そうでないとき、a_1 k_0+a_2 l_0=gなるk_0,\;l_0を持ってくると、a_1 k_0\frac{b_2-b_1}{g}+a_2 l_0\frac{b_2-b_1}{g}=b_2-b_1となるため、a_1(k\frac{a_2}{g}+k_0\frac{b_2-b_1}{g})+b_1=a_2(k\frac{a_1}{g}-l_0\frac{b_2-b_1}{g})+b_2が満たされる。

元の式におけるk,l\ge 0という条件をギリギリで満たすように、k_0\frac{b_2-b_1}{g}の値に\frac{a_2}{g}を足すのとl_0\frac{b_2-b_1}{g}の値から\frac{a_1}{g}を引くのを同時に行って少し調整したり戻したりすると、x=\frac{a_1a_2}{g}k+b,\;k\ge 0となる。これで解けた。

何回か落ちて、テストケースを見ながら解いた。調整するあたりでひたすら失敗していた。

Fは文字数の総和の制約が小さいことに着目して、検索する文字列について部分文字列の先頭を全探索する方法と、線形時間でSuffixArrayを作って検索される文字列集合を全探索する方法のうち計算量が小さいほうを選ぶようにしたら通ってしまった。想定解はAho-Corasick。動的にする方法は、文字列削除については一度削除した文字列が二度と追加されないことを利用し、削除した文字列だけで問題を解いて答えから引くことで達成する。構築は僕としては初めて見るタイプの手法で、2べきのサイズの集合に対してAho-Corasickを作って、追加する際は20、21、22とまとめて23を作る、みたいな感じにする。2進数の繰り上がりを考えているようなものだろう。文字列が移動する回数がlogで抑えられるというわけだ。クエリ平方分割よりオーダーは良さそう。

今日の典型90問はSCCをするだけの問題だった。C++で書いていたら最短を取られてしまったので、何とかPerlでSCCを実装して取り返したが、そこからさらにドンドン縮められていって、勝てない。そのうえ自分は定数倍バトルもしている。

サークルのバチャに出た。CF #503 div.1。

https://codeforces.com/contest/1019

Aは勝った時の票数を決め売って貪欲。Bは円の向かいの値と組みにして差を見ると、変化が連続（とはいえ-2、0、+2だが）かつ両端の符号が異なるため、関数のゼロ点を求める要領で二分探索できる。ここまで爆速で1位だったが、以降1問も解けなかった。Cは二部グラフのように塗ってみてダメなところを少し修正するもWA。Dは1点決め打って原点に移動させ、もう1点決め打った時に残りの点との外積を見ることを考えていたが、外積のような式の値を検索する方法がわからなかった。

午前零時くらいに布団に入ってなろうを読んでいた。午前2時くらいに寝落ちした。

04/23(金)

午前8時起床。ゴミを出した。布団に戻ってなろうを読みふけっていたら、学食にも行けなかった。

コードゴルフの更新が流れてきた。

atcoder.jp

uniqコマンドのオプション-uを知らなかった、あるいは忘れていた。調べると、ただ1回出現したものだけを抜き出すらしい。まさにドンピシャなオプションのようだ。便利な機能だが、Rakuにはそのようなメソッドはないらしい。uniq -dはrepeatedとしてRakuにも備わっているのだが……。そのこともあって対称差集合という解から抜け出せなかったのだろう。

今日の典型90問は和をgcdで割って3引く。Rakuで書くのがよさそう。dcより10B近く短くなった。

そのようなこともあって、何度かパソコンと布団を往復していたが、午後4時くらいに寝落ちした。本来はゴミを出してからすぐ二度寝する予定だったのに、なろうを読むのがやめられなかったせいで、このような時間に寝ることになってしまった。

04/24(土)

午前3時起床。TC、yukicoder、CFをすべて吹き飛ばしてしまった。TCはunratedだったようだ。

dic.nicovideo.jp

5719757レスに達したらしい。公式からも言及があって、スレが動作や負荷の確認に活用されていたことが明かされている。サービスにおける「普通」を極端に逸脱するようなもので不具合を起こさないか確かめることについては、例えば最近Steamで25000本以上のゲームを所持している人に影響のあるバグが修正されたことが話題になったことが連想される。また僕自身、AtCoderに対してbotに近い回数の提出をしているので、何かのUserScript・ツールの負荷チェックに使われたという話を聞いた気もする。

そういえば先週分のyukicoderも解いていない。まとめて埋めることにした。まず今週分から。

yukicoder contest 292 - yukicoder

Aはよい。Bは愚直にやる。タグの「算数」が謎。Cはかなり難しいが、有名な事実ではある。何回かTLに流れてきて、つい最近も話題になっていた気がする。詳しい証明はわからない。Dはナップサック。Eは二項係数で書いてWolfram-Alphaに投げたら閉じた式になった。

\displaystyle \sum_{h=0}^{H-1}\sum_{w=0}^{W-1}\binom{h+w}{h}=\binom{H+W}{H}-1

これの求め方には、解説で紹介されている\sum_{k=0}^m\binom{n+k}{k}=\binom{n+m+1}{m}を利用する他にも、考えているマス目を拡張して経路で考える方法もあったはずだ。少し考えてみた。H\times Wのマス目を下に1段拡張してみる。その段に突き抜けてきた経路は、その経路が最後に右に進んだときの、進む前のマスまでの経路と一対一対応する。つまり、それ以降は1マス右に進んで、あとは下に突き進んでいくただ1通りしかないからだ。H\times Wマスのすべてに対してそのような経路を対応させるには、W列目からさらに1マス右に進むために右にも1列拡張するべきということになる。

さて、一番下の段に突き抜けてきたというのは、最後の移動が下移動だったということだ。一番下の段のすべてのマスについて総和を取ろうとしたとき、実はその段の一番右のマスに侵入する経路をすべて数え上げればよい。最後の下移動から先は右移動しかないからだ。最後に、H+1行1列のマスにたどり着く経路に対応するものが存在しないため、1引くことになる。よって上記の式が得られる。

FはEに比べれば簡単。二次元累積和で、imos法の分と累積和の分で2回累積和を取るのはあんまり見ない気もする。

続いて先週分。

yukicoder contest 291 - yukicoder

Aから難しいが、ちゃんと考えると解ける。Bは最適っぽい行動が実際に最適になっていることがわかる。Cは、2020/11/30に解いたAOJ-ICPCの問題の系だと思って、かんプリンさんのユーザー解説の方法で解いた。

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

Dは二部マッチング専用のライブラリを張ると頂点を毎回H+W+2個作っても間に合った。O((H+W)HW)。Eは超頂点という話を何度も耳にしていたので一瞬。まあこのような問題で超頂点を考えるのはかなり自然であると感じる。Fは解けなかったので解説を読んだが、解説がかなり不親切だった。必死に行間を埋めて、久しぶりに解説記事を投稿した。

kotatsugame.hatenablog.com

昼前に布団に戻り、しばらくなろうを読んでいた。生協の弁当を受け取るため、午後3時には起きている必要がある。午後2時くらいに寝ようとしたが、さすがにあきらめてそのままなろうを読んでいた。

午後3時になって、今日の典型90問のジャッジが公開された。考えていたコードを実装したところTLE。よく見るとO(HW2^W)だった。大体9e9くらいらしいが、TL 8secだし、それ以外はよくわからないので、定数倍バトルをすることにした……と思ったら、値が0のときに遷移をスキップするだけで通った。5700ms。もう少しバトルを続けて、4200msまで落ちた。

これまではマスごとに見ていたが、行ごとに一気に見ることにした。これで計算量からWが落ちるかと思ったら、部分集合全体の和が必要になったので落ちなかった。しかも遷移のスキップができないからか定数倍が悪化したらしく、いろいろいじって縮めつつ7000msくらいになった。そこでコードゴルフはあきらめたのだが、climpetさんによればちゃんとやるとRubyで通るらしい。ちょっと信じられない。

そうしている間に弁当が届いたので受け取り、午後5時に就寝。午後8時半に執念の起床。かなりつらかった。

第六回PASTの問題が公開されていた。ABを解いてちょっとゴルフしていたらABC199が始まった。

AtCoder Beginner Contest 199（Sponsored by Panasonic） - AtCoder

全完12位。EとFでかなり失速した。

Aはよい。FAこそ取れなかったものの、最初の提出が最短。BはRaku。CからはC++を使用した。Cはかなり面倒。本番は何も考えていなかったが、冷静になってみればこれがC問題で出るのはかなりびっくり。Dは1色決め打って残りは二部グラフ。うっかりdfsで最初に訪れる頂点の色を塗り忘れて1WA。Eはしばらく挿入DPが頭にチラついて悩まされたが、ただ先頭から決めるbitDPでよい。Fは行列累乗。

コードゴルフ。Aは先に触れた。Bは、Rakuにおいてはmin-maxとするよりもA-Bを全探索するほうが短く書ける。CはRubyで書いていたが、Perlに負けた。Dは手つかず。EはRubyでTLギリギリ、ほかにコードゴルフしている人がいないためよくわからない。Fも手付かず。

第六回PASTを埋め始める。

第六回 アルゴリズム実技検定 - AtCoder

ABCDはよい。Eはひたすら面倒。3個掘り出して2個戻す、みたいなことをしないとならないかとも思ったが、普通にdequeのイテレータでeraseしても十分効率的なようだ。先頭と末尾のうち短いほうを動かしてくれるのだろう。よく考えたらdequeではなくlistでもよさそう、削除に時間をかけるかアクセスに時間をかけるかの違い。Fもよい。

Gは難しい。ある辺を見て、これがいつなら使えるかをセグメント木上の二分探索で求めるコードを書いた。解説は辺をpriority_queueに入れるというもので、かなり頭が良い。Hは2つのうちどちらからいくつ取るかを全探索する。よく見るやつで、面倒。Iはdpするだけ。Jは平均値を見るだけ。これがJにあるのはかなり謎。Kは購入金額 mod 100をdpの添え字にする。

Lは頂点集合を全探索して最小全域木。前のPASTでも見た……と思っていたら、今回はコストの計算がちょっと面倒。微妙な幾何要素。Mは区間をsetで管理して頻度をmapで管理する。かなり面倒だが、どうやら想定らしい。Nは比較関数を考えてソートするやつ。Mは木とそれ以外の辺に分けて、それ以外の辺だけ毎回計算するやつ。

コードゴルフについて。Aはめちゃくちゃ嘘解法が通っていてすごい。BはPerlで、/o/ではなく/ost/までマッチさせることで、インデックスを割り算したときに小数部分が出ないようにできる。CはRubyでArray#&。EはRubyだとTLEしたがCrystalでちゃんとDequeを使うと爆速だった。JはOctave。X-mean(X)はcenter(X)と書ける。

そのほかDFKNはRubyで適当に通してある。ILMはC++で書いたものが最短になっている。また、ABC問題で最速コードを保持している。

この問題追加ラッシュで、Shortest 1500問とFastest 600問を達成できた。

朝方はずっと日記を書いていた。溜めがち！

終わってから布団に入って少しなろうを読んでいたが、すぐ眠気が耐えられなくなって寝た。午前10時だった。

04/25(日)

午後4時くらいに目を覚まし、うっかり以前に読んだハーメルンを読み返し始めてしまった。止まらなくなり、そのまま午後6時まで読んでいた。今日は午後7時からAHC002があるので、もう二度寝できる時間ではない。

仕方なく起きて食事した。第六回PASTのE問題が縮められていた。Array#[]?を使った書き方をしたらREが出たので放置していたが、現在の最短コードにはそれが使われている。一体どういうことなのか、Crystalの環境は手元だとサブのノートパソコンにしかないので、引っ張りだしてきて確かめてみると、オーバーフローしているようだった。bytesで得られるのはUInt8型で、その関係だろうか。三項演算子の第二項で型が決まって、第三項がそれにキャストされる……など考えてみたものの、結局よくわからなかった。

atcoder.jp

AHC002が始まった。

AtCoder Heuristic Contest 002 - AtCoder

最初2時間は時間いっぱいdfsする解を投げていた。4近傍のうちポイントが高いマスに行くのは実は全然良くなく、それをするくらいなら4近傍を探索する順番を固定して見ていったほうがスコアが高くなる。時間内に見つかる解というのは、少し探索回数を増やしたくらいではほとんど変化しないことは確認していたが、コンテスト後のTLによれば、この性質を利用して探索時間を短くし、代わりに4近傍を探索する順番を4の階乗通り試すことでもスコアが伸びたらしい。

さて、4近傍を探索する順番を固定すると何がうれしいかというと、探索する場所が固まりやすいことのようだ。目先の利益だけ求めてふらふらさ迷い歩くと、いつの間にか盤面を横断してしまって片方を全然踏めない、ということが起こりうる。

ここで、「固定する」ということにとらわれていたのか、一定の方向に進むのを繰り返すことを考えた。右と決めたら右に、下と決めたら下に、できるだけ移動するようにして、進めない時だけ少しずれるがまた戻るという探索を実装しようとしたが、実はこれはかなり難しい。方向の履歴を見て決めるのはどういう決め方にするかよくわからないし、直前の方向だけ見ているとちょっとずれるつもりがその方向に驀進してしまったりする。dfsを何回かに分けて呼び出して、その時々でどちらに進むか決めるものも書いてみたが、結局制約からまっすぐには進めないので、ずれるときの処理で困っていた。今から考えてみれば、もし実装できたとしてもうっかり盤面を横断してしまいそう。

AHC001で盤面を分割していた人がいたことを思い出したので、その方針で実装してみることにした。これは探索する場所が固まっているのでかなりよさそうだ。先ほど諦めてしまった「一定の方向に進む」ことも、分割した盤面を並べるときに考慮することで実装できる、と考えていたが、結局このことは使わなかったし、実際にあまり一定の方向に進んでいるような感じはない。

適当に10x10マスのブロック5x5個に分割することにした。ブロックの区切りをタイルがまたいでいるとき、そこを経由してブロックを移動することはできない。よって、そうでないマス、つまり経由することでブロックを移動できるようなマスの組を探し、そういうマスが存在するかどうかでブロック間に辺を張ってみた。そうしてできた25頂点のグラフをdfsして、適当にハミルトン路をとる。以降はこれに沿って進んでいくことになる。

1つのブロックの内部は、dfsで全探索しても間に合うようだ。始点を決めて、そこからdfsする。終点としては（結局すべてのマスに対して計算結果を保存するものの）先ほどチェックした次のブロックに移動できるマスを考えている。そのようなマスそれぞれに対して最もスコアが高くなるような経路を探し、それぞれ1歩移動してブロックの境界を越えたものたちを次の始点として扱う。ちょっと変則的だが、ビームサーチしているようなものだと思っている。例えばこれが1通りしか経路を保存していないと、うっかり先に進めなくなってしまったりするのだ。

最後のブロックの終点は、ブロック内のすべてのマスが候補になる。なかなか実装に苦労したが、何とか1時間半弱で書けた。提出すると5e6点を超えた。時間にいくらか余裕がありそうだったので、ブロックの始点の数を制限していた部分を消して提出しなおしてみると、さらに2e5点くらい伸びた。最後のブロックの始点としてこれまでの最大スコアの経路だけ考えていたのを、他のブロックと同様前のブロックから境界を越えてきたものすべてでも計算するようにしてみると、さらに少しだけ伸びた。

分割するサイズもいろいろ変えてみようと思っていたのだが、ちょうど50の約数になっている必要があることもあり、ほかのサイズだとハミルトン路を求めるdfsかブロック内のdfsのどちらかに非常に時間がかかるようになってしまった。10x10はこのどちらもそれなりの時間で終了してくれる、なんともちょうど良い分割サイズだったようだ。

ブロックの始点としては現状1マスにつき1つだけ経路を保存しているが、この制限もなくしてみようと考えて実装した。しかしバグってしまいそのままコンテスト終了。終わった後もしばらく格闘して、なんとかバグは修正できたものの、スコアは逆に下がってしまった。

ブロックとしてみれば、右上の始点から下に進み、あとはジグザグに埋めているような感じか。表示してわかることだが、ブロックの境目の取りこぼしがかなり多くて残念。

atcoder.jp

結果は5370372点で22位、パフォーマンス2707、レート794→1783(+989)。非常に良い。

そういえば、ハミルトン路を求めるときはスコアを何も考えられていない。この時、最初にやっていたように、できるだけ一定方向に進むような順序で探索してみると、次の画像のような経路が得られた。周囲をぐるっと一回りした段階で次のマスに進めなくなってしまったようだ。

TCB35が終了した。理論値が僕を含めて3人いたり、賞金ボーダーの点数が理論値-18点だったりと、今回はみんな点数が高い。