11/29(月)

先週の週記を投稿してから1時間くらい、インターンのコーディングをした。このようにやる気を出したら1時間で終わるようなものを作るのに、自分はどれだけ放置していたんだろう。猛省。

布団に入って少しだけハーメルンを読み、午前10時半に就寝。

午後4時半起床。今日も定例会があるが、寝る前に進捗を産んでおいたので、ギリギリまで寝ていることができる。ということで追加で15分くらい横になって、ギリギリに着席して進捗報告のスライドをサッと書いた。今週からいよいよ業務の体験が始まるので、しばらくは生活リズムを正して連絡に備えておく必要がありそうだ。

定例会は特に何事もなく終了、勉強会まで終えて、しばらくTLを眺めていたら学食が閉店してしまった。冷凍の弁当を食べてコードゴルフを始めた。

PerlのUnionFindに新手が出ていた。ルートノードを!defined$p[$v]で特徴づけると、$p[$v=pop]&&=find($p[$v])でpath halvingが行える。ここで$vはローカル変数ではないため、find関数の最後に$vを返しておけばちゃんとルートノードが得られるというわけらしい。そこから問題に合わせてさらに縮む余地があって、$vの代わりに$_を使ったり、popするのではなくfind関数の呼び出し時に書き換えるようにしたり、配列@pではなく変数${-$v}を使えたりするようだ。最初に見たときABC228-Dを思い出したが、確認してみるとあまり似ていなかった。

atcoder.jp

これを使って縮む問題が他に7問ほどあった。ルートノードの@pの値を迂闊に書き換えてはいけないのがつらいところで、ちゃんとルートノードが異なることを確認してからuniteする必要があるため、コードこそ少し長くなりがちなものの、find関数がこれまでに比べてあまりにも短いため、猛威を振るった。最も単純には、「グラフを連結にするのに新たに必要な辺の本数は？」という問題がAtCoder上に少なくとも2問存在し、これは何もなくてもルートノードが異なることの確認をしなければならないため、かなり効いた。逆に、適当にuniteした後同じ集合にあるかどうかを判定するような問題にはほぼ効かなかった。

昨日投稿した週記の一部に誤りがあって、修正した。

2021/11/29追記：⇒は嘘だった。
週記（2021/11/22-2021/11/28） - kotatsugameの日記

午後11時半になってCodeChefで謎のコンテストがあったので、試しに参加してみた。公式コンテストではないが、一応div.2以下でRatedではあるようだ。

https://www.codechef.com/FOUR21A

全完1位。問題名が長く、問題コードは公式コンテストとは異なり無機質な文字列に設定されているので、以下では順位表の左からABCDEと付けておく。solved数はこの順ではないようだった。

Aは、とりあえず全体の最小値だけ回してから引いて、非ゼロ要素が最も長く連続する箇所を探せばよいか、と思って提出したらWAだった。改めて問題文を読み直すも、特に読み飛ばした要素はない。ここでサンプルの説明文を見ると、なぜか人が並ぶ順番を自由に入れ替えている。慌てて数列をソートしたら通った。後から問題文を確認したところ、「Among all possible ways in which the $N$ neighbours start the game」が順番を入れ替えてよいという意味に取れなくもない。しかし、「Any person can hold the bowl initially」とあるのだから、このpossible waysとは誰が最初にbowlを持っているかについて言っているととらえるのが素直な読み方ではないだろうか。

Bは自明。Cは残す文字を決め打って、取り除かなければいけない区間を数える。それが $K$ 個よりも多ければ、残したい区間も短い順に使っていくしかない。これもWAが出てびっくりしたが、負になりうる整数とsize_tを比較していたのを見つけて、試しにintにキャストしてみたら通った。このバグをすぐに見つけられたのはかなり冴えていたのではないか。Dは $S$ が $T$ のどこに対応するかを全探索して左から貪欲に決める。文字を追加した後、その文字を巻き込んでflipする可能性があるので、一応端には気を使っておく必要がある。そのことは最初から分かっていたのに、コスト計算を間違えて1WA。ところで入力のテストケース数 $T$ と文字列 $T$ が被っているのは誰も何も思わなかったのだろうか。

Eはそこそこ面白かったが、modを取る要素は要らないかな……。まず観察として、購入する座席の長方形は左上に寄せてよい。なぜなら、左上に寄せていくと総和が小さくなる一方、数値同士の間隔が狭くなるからである。さらに、縦よりも横が長い長方形だけ考えることにしてもよい。これも長方形を倒すことで総和が小さくなることと、間隔が狭くなることからわかる。コンテスト中は総和にだけ注目して、数値の間隔は考えていなかったが、フルフィードバックなのでヨシ。さて、ここで数値の間隔などに着目すると、 $S_{i,j}=(i^2-i+j^2-3j+2ij+2)/2$ であることがわかる。 $[1,H]\times[1,W]$ で和を取ると閉じた式ができるが、その値のオーダーは $O(HW(H^2+W^2))$ となって、この問題の制約下では64bit整数に収まる。よって普通に最小値を計算して、出力の時だけmodを取ればよい。

あとは $H\le W$ かつ $HW\le max_N=4\times 10^5$ の範囲で全探索できる。まず $H$ を $H\le \sqrt{max_N}$ の範囲で全探索し、 $W:=H$ としてどんどん増やしていく。このとき、「中央値（ただし要素が偶数個の場合は小さいほう）」、「中央値が存在するマスの座標」、「中央値以下の値の総和」を管理しておくことで、 $S_{i,j}$ の総和の式と合わせて常に最小コストが計算できる。まず最初に、 $H=W$ のときは $1$ から十分多くの整数が連続で含まれているため、中央値 $\left\lceil H^2/2\right\rceil$ となり、それ以下の値の総和もすぐ出るし、座標もちょっと実験するとわかる。そこから $W$ をインクリメントするときには、中央値が何個ずれるかを求めて、その回数ぶん座標をずらし、座標から値を取得することでうまくいく。各 $H$ に対して、中央値をずらす操作が全体で $O(max_N)$ なので十分間に合って、今の前計算をもとにクエリに答えればよい。

div.3の問題も残り3問解いておいた。こちらは特に言うことはない。

布団に入って少しハーメルンを読んだ。「帝征のヒーローアカデミア」を読了。

syosetu.org

面白かった。普段のほほんとしている主人公の、見せ場における圧倒的な威風が読んでいて気持ちいい。やはり古龍を題材にするとあまりに強力な個性を持つことになってしまい、先日読んだ主人公が悪役となってしまったハーメルンに似たものを感じて勝手に不穏な空気を感じていたが、今のところ真っ当にヒーローをしていてよかった。

さらにしばらくハーメルンを漁り、午前5時就寝。

11/30(火)

午前10時起床。TLに検索してはいけない言葉をまとめたwikiが流れてきて、見入ってしまい二度寝どころの話ではなくなった。

正午から1on1。今日はちょっとした進捗報告で、この後の動きももう結構前から話してはあったから、再度確認するだけですぐ終わった。

昨日ゴルフしたPerlコードがいくつも縮められていた。値が異なることの判定は引き算して非ゼロであることを使っていたが、XORを取って非ゼロであるか判定すると、例えばF-FというコードがF(-F())と解釈されるのに対してF^FはF()^F()となるため、括弧がいくつか省ける。何とか取り返そうとコードをガチャガチャしていたが及ばなかった。

学食に行って昼食を摂り、注文していた本を受け取って帰宅。午後2時過ぎからインターン先業務に関する追加の説明をしていただいた。先週、研修をしてもらったが、今日はその周りの細々としたことについてで、ツールのアカウント発行をしてもらったり、他の人とのやり取り方法（Slackの各チャンネルの目的と投稿テンプレート）を聞いたりした。早速始められる状態になったが、いざ自分でやろうとしてみると腰が引けて、思ったより手が出ない。

一旦1時間ほどラノベを読んでから再度取り組んでみた。内容によって個別に判断しなければならないことが多く、質問したいことがたくさん出てきてしまった。工程の最初のほうにダブルチェックがあるので、とりあえず仮にそこまで進めて聞いてみることにした。と、そういう内容でSlackに投稿を行ったが、その後マニュアルをよく読むと午後4時までに投稿しなければならないとされていて、時間が過ぎていたので申し訳なくなってしまった。

今日の業務はこれで終わり。火曜日のPythonの講義がClassroomに投稿されていたので、課題を終わらせた。今日はパラメータ2つとそれの戻り値で3次元プロットを使ってみた。jupyter notebookではグラフをマウスでぐりぐり動かせた覚えがあったのだが、Google Colab上ではある一定方向からの画像しか表示されないようで、ちょっと残念だった。%matplotlib notebookと書くと、そもそもグラフが表示されなくなってびっくりしたが、調べた感じ、そもそもこれがjupyter notebookでグラフを動かすときのおまじないだったらしい。

ラノベを1冊読了。「ログアウトしたのはVRMMOじゃなく本物の異世界でした」。導入部分はほぼソードアート・オンラインで大丈夫かと思ったが、現実とゲーム設定が入り混じった世界に飛ばされてからは、ゲーム知識とゲーム内で育てたステータスで正当に（？）無双していてよかった。主人公のスキルで新しく「呪紋」を作るのも、いろいろ設定があってなるほどと納得できる。ただ、ステータスの魅力値を参照してヒロインたちが主人公に惹かれていくような描写だったのは気に入らなかった。そこだけは本当に正当にやってほしい、というのが僕の好みだ。

別のラノベを開いて少し読み進め、午前0時半就寝。

12/01(水)

午後1時起床。すぐ学食に向かい昼食を摂って、今日もまた注文していた本の受け取りをした。

11月の集計
買った：24冊
読んだ：16冊
積読：+8冊
積読（累積）：+98冊
— こたつがめ (@kotatsugame_t) 2021年12月1日

先月は思ったより読んだなあという感想だが、相変わらず買った本のほうが多くてどうしようもない。本棚にももう入りきらないので、そろそろ買い足すべきではないだろうか。普通に本棚を買うと付属する棚板が少ないため各棚をラノベの高さに合わせることができず、1段はラノベの上に直接ラノベを並べるアクロバティックな配列にならざるを得ない。なので、本棚を買うときは忘れず棚板も追加で買うようにしよう。

しばらくパソコンの前でボーっとして、午後3時半からインターンの作業を始めようとした。結構時間に余裕があると思っていたが、冷静になるとやり取りの締め切りである午後4時までは残り30分しかない。慌てて昨日の続きを少しだけ進めたが、今日もまともな進捗は産めずに終了。

ゲーセンに行くことにした。今日は夜から雨が降るらしいので、地下鉄で向かう。まず仙台駅のほうまで足を延ばして、予約できなかった本を1冊買った。

「時々ボソッとロシア語でデレる隣のアーリャさん」3巻が12月の頭に発売されるが、それだけ予約受付が終了していた。
週記（2021/11/22-2021/11/28） - kotatsugameの日記

今日も結構いい感じ。新曲の14+を99AJし、既存の14+でSSS+とAJをそれぞれ1つ出した。また理論値も5譜面出た。これまで出した理論値は、何回もプレイして1落ちを踏んでようやく出たというものだったが、今日は適当に選択したら1発で出たものがあって、かなり上手くいったなあという感想。内部精度はかなりボロボロだったので、運がよかっただけにも思える。

Yakumo >>JOINT STRUGGLE (2019 Update) AJ！！！！！！！ pic.twitter.com/c8rze8mAJe
— こたつがめ (@kotatsugame_t) 2021年12月1日

DAYBREAK FRONTLINE 理論値
トランスダンスアナーキー理論値
この内訳で出てないの奇跡だろ pic.twitter.com/zi7ExwTnvW
— こたつがめ (@kotatsugame_t) 2021年12月1日

帰宅。AtCoderに「Rated/Unrated登録機能」が追加された。今週末のコンテストから適用される予定らしい。僕は（自分が覚えている限り）いわゆるNoSubをしたことがないので、完全に歓迎する側の立場である。ああでも、AtCoderを始めてしばらくは青でもARCに出ずにABCに出ていたことがあったので、そういう意味でRatedから逃げた経験はある。今でもCFのdiv.1はサボり気味。

Rated/Unrated登録機能追加のお知らせ - AtCoder

少しインターンの作業を進めてから布団に入り、しばらくラノベを読んで午前6時就寝。

12/02(木)

午前11時半に起床。

昨日進めておいた分のチェックのためにやり取りをしていた。大きな修正は後からにすると決めていたが、すぐ終わるような修正がポロポロ見つかって、それを直して再度チェックをお願いするということを繰り返していたら午後1時前になってしまった。毎週木曜日は4年ゼミだが、特に今週からは山の教室で、対面で行われる予定。完全に遅刻である。

急いで身支度をするも、出発がそもそも午後1時だった。どうしようもないので開き直って学食で悠々と食事をし、今日もまた注文していたラノベを受け取って、教室に到着したのは開始から30分以上過ぎたころだった。今日は僕の発表の番ではないので、聞くだけ。しかし換気のため扉が開け放たれた教室は寒すぎる。防寒着を羽織ってパーカーのフードを被り、震えながら発表を聞いていた。暖房が強められ、部屋が暖まってきたくらいで終了してしまった。

その後は部屋を移動し、前回の対面ゼミのときと同様に5人でスカルをプレイした。前回の経験から、部屋の使用は6時をオーバーしても大丈夫そうだったので、みっちり2時間ほどプレイしていた。今日はあまり振るわず。攻め時がわからず、初手でドクロを置いてめくられず終了、みたいなことが多い。ドクロを置いているのでチャレンジにも参加できない。ところが、逆にドクロを置いているのにチャレンジに参加し、ブラフを使うのが非常に得意な人がいた。一度など、場に10枚しかないのに7枚を宣言するから、僕も強気でやってやろうと思って8枚を宣言し、いざその人のタイルをめくってみると一番上にドクロがあったということがあり、心底びっくりした。

解散して、閉店ギリギリの学食で食事。テレビがついていて、バラエティ中の小ドラマに片桐仁さんが出演していた。ちょっと前にTLで片桐仁さんの個展の話も流れてきたことだし、そうやって活躍されている様子を見れるのは嬉しい。

午後8時前に帰宅。今朝受け取ったラノベを読み始めた。

└( ＾ω＾ )┘♪ 買った♪└( ＾ω＾ )┘♪ 買った♪ pic.twitter.com/ZbussHhWwB
— こたつがめ (@kotatsugame_t) 2021年12月2日

あまりに眠く、布団に倒れこんで午後11時から午前1時半まで昼寝していた。また起きて読み進める。1年ほど前に1巻を読んだ時も書いた気がするが、この作品は、リメイク前のなろう→リメイク後のなろう→書籍版と辿ってきて、これで読むのは3回目になる。特にリメイク後のなろうと書籍版にはほとんど違いがなく、同じ文章を2回読むことになって、気づいていなかった伏線をいくつか見つけることができた。僕は普段本を読み返すことがないので、こうやって見落としてきた伏線が数えきれないくらいあるんだろうなあと思った。まあ、1つの作品を深く読み込むより大量の作品をとにかく摂取することを求めて読書しているので、仕方のないことではある。

朝になって、さらにちょっとだけインターンの作業を進めた。布団に戻って寝ようとしたが、今度はハーメルンを読み始めて、午前9時になってしまった。作業に関するやり取りを投稿してよい時間になったので、改めて起き上がり、いくらかやり取りを進めて、午前10時半に就寝。

12/03(金)

午後6時半起床。少しハーメルンを読んで布団から脱出。

ABC227の学生奨励賞4位ということで、アマギフが物理的に届いた。再配達をお願いしていたもの。実は昨日、再配達の時間設定を2回も変更していた。最初は特に何も考えず18時～20時を指定したが、サークルと被ることに気づき、また床屋にも行きたくなったので、一気に午前中にずらした。ちゃんと夜眠れればそれでよかったのに、うっかり朝方まで起きてしまったので、今度はサークルのあとになるように19時～21時を指定した。今日は結局午後6時半起床ということで、サークルにも床屋にも行けていない。無力。

学生奨励賞 4位

拝啓　　厳しい寒さが続いておりますが、いかがお過ごしでしょうか。

貴殿は「キーエンスプログラミングコンテスト2021-Nov.」にて素晴らしい成績を収められました。
これをお祝いし、賞金としてAmazonギフトカードをお贈りいたします。

賞金を同封いたしましたので、ご査収くださ pic.twitter.com/KK36hG0Ho3
— こたつがめ (@kotatsugame_t) 2021年12月3日

しばらく日記を書き進めて、午後9時からABC230。今日は金曜日開催。

AtCoder Beginner Contest 230 - AtCoder

Aから難しい。適当に提出していたら2WAも重ねてしまった。とりあえずAWKでACした。Bは"oxx"を9個結合して、入力された文字列が含まれるかをチェックするコードをPerlで書いた。普通にやると改行のせいで常にマッチングに失敗するので、どうやって取り除くのがよいかしばらく試行錯誤して、結局chopするコードを出した。CからC++。Cは、今見ているマスがもし黒で塗られるなら、それのもとになった $k$ の値が確定するので、それを元に $B+k$ と $B-k$ をチェックした。Dは区間スケジューリング。Eは商の値でまとめる典型で、うっかりミスで1WA。Fは難しかったが、累積和を取って考えると、元の列の累積和から適当に選んだ場合の数を数えているとわかったので、同じ値は一番右の位置における場合の数だけ保存するようにdpを書いたら通った。

Gも難しい。ちょっと前にCFで似たような問題を見た気がするが、覚えている問題内容から判断してコードをコピペしに行く必要はないと思い、コンテスト中は探さなかった。ちなみにこの問題だ。

https://codeforces.com/contest/1575/problem/G

ただ、方針は似ているだろう。各 $d\ge 2$ に対して、 $i\le j$ かつ $d\mid i$ かつ $d\mid j$ かつ $\gcd(P_i,P_j)\gt 1$ なる $(i,j)$ を数えられれば、あとは包除原理で求まる。これは後から調べるとGCD畳み込みを再発明していただけらしい。まず、 $d\gt\sqrt N$ のとき、関係するインデックスが高々 $\sqrt N$ 個しかないため、2乗かけて愚直に調べても間に合いそう。この部分は $O(N\sqrt N\log N)$ となる。 $d\le\sqrt N$ のとき、今度は関係する $P_i$ たちを全部集めて、そこでGCD畳み込みをすれば求まる。この部分も $O(N\sqrt N\log N)$ になる。組み合わせても5secには間に合いそう。一度WAが出たが、修正すると4700msで通った。

実は定数倍が少し良い。最初、誤読して $i\lt j$ なる $(i,j)$ を数えようとしていたが、この時 $d\le \frac N 2$ としてよい。また、 $P_i$ たちを集めて行ったGCD畳み込みにおいても、 $\frac N 2$ 以下の範囲だけ考えてよいことになる。この定数倍をなくして提出してみるとTLEしてしまったので、コンテスト中は運のよい誤読をしていたということ。

残り1時間弱でHに進んだ。とりあえず愚直にdpするコードを書こうとして、それすら挫折してしまい、あとはコードゴルフしていた。

A問題はdcが短くなった。10で割った商とあまりを続けて出力すれば、2桁のゼロ埋めと同じことができる。AGC0はそのまま出力しておけばよい。BはVimで書いていたが、普通にsedで判定できたらしい。xxxかooかoxoを含めばNo、それ以外はYes。確かにそうである。テストケースも多いので、これ以上少なくすることはできないだろう。CはRubyをVimで書いたものが今の最短。dcで無理やりコーディングしてみたら、一応短くはなったもののTLEしてしまった。またOctaveは64bit整数が読めず、精度が落ちてしまって通らなかった。DはPerlだと思っていたが、AWKで判定してwc -lするbashコードが短くなった。さらにそれをVimから行うコードで-1Bされるも、Vimの場合はwc -lのオプションを外して、手作業で余計な出力を取り除くほうが短くなるので、さらに-1Bできた。

Eは $2\sum_{i\le\sqrt N}\left\lfloor\frac N i\right\rfloor-\lfloor\sqrt N\rfloor^2$ が答えになるようで、商でまとめる方法だとTLEしてしまうdcでも、こちらの式なら余裕をもって通る。以前から何度か目にした覚えのある式だが、この度4年ゼミで読んでいる教科書の定理からこの式が導けることを発見した。式変形を追うよりも、その定理の下に書いてあった図から一発だろう。ここで曲線は $q=\frac 1 d$ を表している。

Eの最短コード、これか～ pic.twitter.com/NwFC4psIi0
— こたつがめ (@kotatsugame_t) 2021年12月3日

FはAWK。答えが合わなくて、累積和が大きくなりすぎて精度が落ちたかと思ったが、普通に負の数のあまりが負になっていただけだった。累積和自体は最大 $2\times 10^{14}$ と、倍精度浮動小数点数の有効数字でちゃんと表現できる。Gは今のところ、コンテスト中のC++コードが最短になっている。

午前2時からSRM819に出た。

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

Easyはカス。難読テーブルマジック。どんな顔して出題したんだろう。AtCoderのRated/Unrated登録機能を僕が歓迎しているのには、AtCoderはこのようなゴミみたいな問題を出さないと信頼しているからというのもある。解法はまあまともで、およそ前半分を見て文字コードが一番小さい文字が1枚目に選ばれたカードになって、この情報からtopの山の枚数がわかるので2枚目に選ばれたカードも取得できるというもの。後者の事実に気づくのに結構時間がかかった。

Medも難読気味。オートマトンで二分木をdfsしろという問題で面白くはあるが、ratedで解きたいかというと……解きたくない。問題文にリンクが張られていたオンラインでオートマトンを試せるページにdfsのコードが載っていたので、基本はそれを元に考えた。問題内容は「二分木の最大独立集合を1つ構成せよ」というもので、これは葉から貪欲に詰めればよい。dfsして、親に移動する前に子を2つチェックして、どちらもマークされていなかったら今見ている頂点をマークする、というのをオートマトンの状態で管理しつつ行った。

Hardに10分しか残せなかった。焦ってdpを書くも、全然合わず終了。コンテスト後にしばらく頑張ったら通った。1ターンで何人消えるかを各 $2\le n\le N$ に対して求めたい。人を順番に見て行って、次のターン何人消えるかをdpのキーに持てばいけるかと思ったが、「今見ている人が次のターンに残っているか」がわからなければ正しい確率を求めることができない。そこで、 $0\le i\lt n$ を見ているとき、 $[0,i)$ で何人消えるかと $[i,n)$ で何人消えるかの2つに分けて持ってみると上手くいった。ここを分割したせいで各 $n$ に対して $O(n^3)$ のdpを行うことになったが、定数倍がかなり小さいので余裕を持って間に合った。

結局EM2完で14位、2536→2552(+16)。じわじわhighestに近づいている。

布団に入ってハーメルンを1作読了。「デート・ア・ライブ　士道リバーション」。原作完結前に書かれた二次創作で、作品執筆時に登場していた七罪までの精霊たちの攻略順序を逆にするというもの。非常に面白かった。確かに、原作でも精霊たちが士道に惹かれるのはその人柄からであって、別にラタトスクの補助がなくても精霊と出会いさえすれば攻略可能だったのかもしれない。原作では1年で一気に全員を攻略していたところを、1年1人くらいのペースで描かれていて、最初に攻略されたため最も付き合いが長くなって正統派ヒロインと化した七罪が非常に健康に良かった。

syosetu.org

ほかにデート・ア・ライブの二次創作を漁るもあまりピンとくるものが見つけられず、午前7時就寝。

12/04(土)

途中弁当を受け取りつつしっかり眠り、午後6時半起床。食事して日記を書き、午後9時からAGC056に出た。

AtCoder Grand Contest 056 - AtCoder

AC2完で64位（ratedでは63位）、パフォーマンス2871でレートは2850→2852(+2)。一応highest。耐えた。

Aは難しい。問題を読んで、手で $N=6$ の場合の解を構築し、次に $N=8$ を同じ手法で構築しようとして失敗した。ここで初めてサンプルを見ると、なんと $N=6$ の解が書いてあるではないか。しかも自分の作ったものと全然違うタイプで、なんとなく拡張性がありそうな気がする。実際紙で試してみると、 $N=7$ と $N=8$ が作れてしまった。このあたりで実際のコーディング画面に移り、そこでさらに $9\le N\le 11$ を手作業で作るという方針に走った。コンテスト開始から30分弱で6つ全部完成し、チェッカーを書いてみるとちゃんと条件を満たしていることが確認できたので、あとは $N=6$ で穴埋めするコードを書いて提出、AC。すでに300人以上がACしていて血の気が引いた。

順位表を見るとC問題が多く通されていたので、それを考え始める。まず $S_i$ を $[0,i)$ における0の個数引く1の個数（ただし文字列は0-indexed）として、必要な条件をリストアップしてみた。入力の $L$ の値から $1$ 引くことで半開区間にしておくと、 $(L_i,R_i)$ は $S_{L_i}=S_{R_i}$ を表す。他に必要な条件はあるだろうか。例えば、 $L_x\lt L_y\lt R_x\lt R_y$ という入力があったとき、 $S_x=S_{L_x}=S_{R_x}$ 、 $S_y=S_{L_y}=S_{R_y}$ とおくと、 $|S_x-S_y|\le\min(L_y-L_x,R_x-L_y,R_y-R_x)$ も必要である。同様の不等式を区間が重なる条件たちについて求めれば、それで必要十分な条件が集まっているように思われる。しかし条件の数が $O(N^2)$ になって困る。

例えば、 $\min(L_y-L_x,R_x-L_y,R_y-R_x)=R_y-R_x$ の場合を考えてみよう。この場合、特に $|S_x-S_y|=|S_{R_x}-S_{R_y}|$ と書けば、暗黙的な条件であった $|S_{i+1}-S_i|=1$ より $|S_{R_x}-S_{R_y}|\le R_y-R_x$ が満たされる。つまり、 $|S_{i+1}-S_i|=1$ さえ満たせば、ほかの条件は一切考えなくてよいのだ。このことに気づくと、あとは $S_i$ を条件を満たしつつ辞書順最大化すればよくなって、牛ゲーになる。正確には、牛ゲーのためには $|S_{i+1}-S_i|=1$ を $|S_{i+1}-S_i|\le 1$ に緩める必要があったが、実装してサンプルを試すと一致したので深く考えずに提出した。AC。コンテスト中は $S_i$ の定義の符号が逆だったので、辞書順最小化とか最長経路問題とかに帰着しそうになったが、ちゃんと牛ゲーを見抜けてよかった。

残り100分はBを考えていたが、驚くほどわからなかった。そのままコンテスト終了。

Aの解説を見てひっくり返った。そのままでも十分短くなるが、TLで見た「 $\left\lfloor\frac{N}{3}\right\rfloor$ と $\left\lfloor\frac{2N}{3}\right\rfloor$ を入れ替えれば通る」というのを使うと場合分けがなくなってさらに縮む。美しすぎる。

朝方までずっと日記を書いていた。modint配列を{}で初期化しようとして、コンパイルがタイムアウトしてしまったコードがTLに流れてきた。コードゴルフをしていたときに似たような経験をしたことがある。めちゃくちゃ長いint配列の先頭数要素だけ非ゼロに初期化するのに{}を使うと、コンパイル時間が非常に長くなるのだ。なぜ長くなるのかよくわかっていなかったが、今試しに実行ファイルのサイズを見てみると一目瞭然だった。普通にコンパイルするより何倍も大きな実行ファイルが生成されている。ファイル書き込みが長くて、結果コンパイル時間も長くなっていたのだろう。

そのことを伝えると、stackoverflowの似たような言及を調べて下さった。僕の予想はおおむね合っていそう。ちょっと変な初期化をしようとすると、配列の全要素をunrollして実行ファイルに書き込んでしまうらしい。int配列では{}はセーフで、例えば{1}で初期化すると発生したが、modint配列では{}ですら起こるらしい。

https://t.co/xhdaj6Y8Ov
こんなものを見つけました、確かに実行ファイルでは要素を全てunrollして書き込んでいそうです pic.twitter.com/fkJKaUH6JQ
— suisen (@_su1sen) 2021年12月4日

午前8時半就寝。

12/05(日)

午後4時起床。食事してOpenCup。今日はチームとして8完、HLCDJFKIの順だった。

Aから順番に読んでいるとH問題が通され始めたので、読んで通す。この問題は自明枠。その後Lもシュッと通っていった。Cもsolvedが増え始めたので考えてみると、左から見ていったときに、各列の行先としてはマッチする列かつまだ他の列の行き先になっていない列のうち、最も左の列に決め打ってよいことが分かった。そうでないなら行き先を適当に入れ替えることができて、その入れ替えで転倒数が減る。これを提出するとMLEしてしまった。どうやらqueueがまずいらしくて、何もしなくても最初に512要素確保するのでオーバーしてしまっているのでは、ということ。vectorに変えてWAを出しつつ3ペナで通った。

DとJがポンポンと通って、Kが書かれている間にFも解けた。 $b$ を考えているとき、 $b$ 以上の要素は $\frac{10^6}b$ 個しかないため、それ未満の要素を事前にまとめておけば全体でみる要素数が調和級数で押さえられるというもの。まとめるのも、vectorを舐めて次の $b+1$ に対応するvectorを作りつつ、その直前の要素とマージできるかチェックすればよい。他の問題はよくわからないので考察を進めず、代わりに紙コーディングして完璧に準備しており、Kがバグった隙をついて5分で書いて通すことができた。

その後しばらく苦しい時間が続く。Kが定数倍高速化でかなりペナを吐きつつ通るも、その直前で考察が完了したと思ったIはWA。Aもユークリッド最小全域木を使うコードが投げられ、WA。Iは本当に間違いが見つからないので、チームメイトに愚直を書いて試してもらい、無事WAのケースが見つかる。手で試してみると見事に考察が崩壊して絶望。その後はAに適当に口出ししてペナを量産し、何も進まずARCに逃亡した。

その後、Iがチームメイトの天才的な発想によりACされたらしい。これについてはコードを読んでもよくわかっていなかったが、夜になって別の人のツイートを読んで納得した。下のほうに書いておく。さらにGもセグメント木に乗せるモノイドが分かったらしいが、時間切れで終了したようだ。

午後9時からARC131。5完9位。かなりうまくいったらしい。600点3問をポンポン通せて全能感があったが、Fの前に敗れ去った。ARC全完は遠い。

AtCoder Regular Contest 131 - AtCoder

Aは冷静になると上位桁で $\frac B 2$ を、下位桁で $A$ を作ればよい。 $\frac B 2$ は整数でない可能性があるので、代わりに $\frac{10B}2$ を考えればよい。上位桁と下位桁をつなげるのは、桁数を求めて10のべき乗を掛けて……とすると面倒なので、文字列として連結してしまえばよい。これをRubyで書いて、通るのを確認してすぐさまdcで書き直した。こちらは、文字列連結の代わりに2数を続けて出力する方法をすぐ思いつけて、6Bのコードが完成した。Bは小難しいことを言っているが適当にやればよい。

Cを読んで、しばらく考えてもわからなかったのでDに移った。Dはすぐわかった。矢の間隔は常に $D$ であるとしてよい。非負の座標であって最も中心から近い位置に当たった矢の座標 $0\le x\lt D$ を全探索することを考える。当たった座標が負の矢については、全部反転して非負の場合の計算に帰着できるので、以降座標は非負のところのみを考える。さて、まず $x=0$ の場合における矢の点数を尺取り法で求め、BITに乗せて矢の本数から得点をすぐ得られるようにしておく。今から $x$ をインクリメントしていくが、このとき境界を跨いだ矢を逐一検出して対応する点数を更新したい。実は、 $x$ を動かす過程でそのような更新は高々 $M$ 回しか行われない。なぜなら、ある境界を2本以上の矢が跨ぐとすると、その矢の間隔が $D$ 未満となってしまうからだ。なので、更新されるタイミングの $x$ を最初に計算して優先度付きキューに入れ、毎回それを見て更新していけばよい。

Cに戻った。自分の手番であるクッキーを食べると、次に相手のターンで勝利できてしまう場合を考える。クッキーが3枚以上残っていれば、まったく関係ないクッキーを代わりに食べることで、相手のターンで勝利させないようにできるのではないかと考えた。これは当然大嘘で、まったく関係ないクッキーを食べたら今度は相手も食べるクッキーを変えてくるので、もうちょっと考える必要がある。ともかくこれで実装すると、初手で勝てるかクッキーの枚数が奇数なら勝ち、そうでないなら負けである。証明は全く正しくなかったが、通った。しばらくコードゴルフもした。

Eに進んだ。手で $N=6$ を試してみた感じ、それぞれの頂点から出ている辺がだいたい同じ色になっていればよさそう。 $i=1\dots N-1$ を順に見て、使える辺の本数が $N-i$ 以上残っている色を貪欲に選び $i\lt j$ なる辺 $(i,j)$ に使うというコードを書き、プログラムでチェックしてみたところ、そもそも辺の本数が3の倍数でない場合と $N\le 4$ である場合を除いて全部正しく構築できているらしい。初手で正解方針を引き当てたようでびっくりしつつ提出すると、WA。よくわからないのでとりあえず再度チェッカーを回してみるか、としたが、コード中の定数をよく見ると、色としてRBWではなくRGBを使っている。慌ててこれを書き直し、提出してみると通った。

1時間以上残してFに進んだ。Fはdpだろうと思って、現在見ている区間にどのようなスタンプが押されているかを状態で持ってみるも、サンプル2が合わない。デバッグ出力をにらみつけてみると、これまでスタンプを押してこなかったのに、急にCをスタンプで押したくなったので、文字列を遡ってそのようなスタンプの押し方が可能か探すのができていないらしい。正確には、そのような遡りが2文字くらいならば対応できていたのだが、実際はもっと前まで見なければならない可能性があって、対応できていなかったようだ。これに気付いたのが残り10分くらいで、急いで書き上げてサンプルも試さず2回ほど投げたが、どちらもサンプルすら通っていなかった。

ARCの直後、午後11時からCodeChefでSnackDown 2021 - Online Elimination。

https://www.codechef.com/SNCKEL21

SORTSEGSは腰を据えて考えると分かった。後ろ、前、後ろと3回ソートすると、ちゃんとすべての値が正しい位置に来ることが直感的にわかる。つまり答えは最大3回なので、2回以下かどうかを判定する。まず数列の前と後ろから触らなくてよい部分を切り落として、何も残らなければソート済みと分かって0回、長さが $K$ 以下なら1回。2回で可能かの判定はちょっと考えたが、結局両端を触らなければならないので、後ろ→前か前→後ろの2通りの手順しかない。両方試すことにした。

TSPはたまに見るdp。経路のループを頂点 $1$ と $N$ で分割し、両方 $1$ から $N$ に向きづけてみる。すると、途中で頂点番号が小さいほうに移動しなくてよいことがわかる。 $c_{ij}\lt D$ の制約が効いていて、そのような移動があった場合、順番をswapすることで必ず距離を縮められるからだ。よって頂点 $1$ と $N$ 以外で重ならない2本の経路の、長さの和の最小値を求めることになり、これは頂点 $1$ から延ばした経路の現在の端点を2つ持つ2次元dpで解ける。頂点番号の差の絶対値によるコストは定数として後から足した。

RNDCHULLはかなり嫌な感じだが、丁寧に実装するとすんなり通って気持ちよかった。とりあえず $i\lt j$ と $i'\lt j'$ を用意して、 $(x_i,y_{i'})$ と $(x_j,y_{j'})$ を結ぶ辺がどれだけ寄与するかを考える。これはXY平面において右上がりの線分で、それより上または線分上にしか点が存在しなければ $x_iy_{j'}-y_{i'}x_j$ の寄与、下または線分上にしか点が存在しなければ $-(x_iy_{j'}-y_{i'}x_j)$ の寄与をすると考えられる。後者は $i$ と $j$ 、 $i'$ と $j'$ を入れ替えたものも考えればそちらでカウントすることにして無視できるが、後々のためこの状態で数えることにしておく。

さて、とりあえず線分より上または線分上にしか点が存在しない場合を考える。これは、X座標が小さくなるにしたがって使えるY座標が大きいほうから広義単調に増加していくため、どのY座標を使えるかは尺取り法で求められ、また場合の数も「今使える個数」引く「もう使った個数」を掛け合わせることで出せる。逆も、X座標が大きくなる方向に計算すれば同様のことができる。これを図に書いてイメージするため、先に $i\lt j$ と $i'\lt j'$ のように固定しておいたのだ。実は $j'\lt i'$ の場合も考えなければならないが、これもほとんど同じコードの繰り返しになる。

ONECHANGEは解けなかった。各文字は高々2つの部分列にしか現れず、aとbの後半を組に、bの前半とcを組にすると必要な部分列が1減らせる、のように計算していくものだと思った。しかしそのように使える組の列をまともな計算時間で列挙する方法がわからず、適当に貪欲してWAを出した時点で集中が切れてしまった。残り30分くらいは別のことをしていた。

結果は3完ほぼ最速で40位。思ったよりFinalが近かったようだ。

ARCのコードゴルフ。A問題はコンテスト中の6Bが最短。Bを飛ばして、CはPerlでコンテスト中に書いたのが49B、そこから$%==$_を/$%/にすると、1回TLEしつつも通ってくれて47B。この書き換えは同値ではなく、例えば$%==1かつ$_==11などでTrueと判定されてしまう。それ以外にも、ループのためにgrepを使っている箇所も微妙に嘘である。Dも飛ばして、Eはコンテスト中の方針をRubyで書いて101B。

昨日のAGC056-Aが今日の昼頃縮められていたので、取り返しておいた。斜めに大きな連結成分を作り、周りに1x1の連結成分を大量に作るという方針らしい。文字列を作りながら行ごとに出力するのは昨日と同じで、行番号のswapの必要がなくなって縮んでいた。文字の判定で-1B、Rubyのゴルフテクでさらに-1Bした。

OpenCup-Iについて。この定義がどこから降ってきているのか全然わからない。遷移を読むと確かに定義通りの値を計算しているんだなあとなるが……。次見たときに思い出せるようになりたい。

f1(S, p): S の subset であって、どの 2 要素を取って xor しても p 以下になる物、の大きさの最大値
f2(S, T, p): S, T それぞれの subset の組であって、それぞれから 1 つずつ要素を取って xor しても p 以下になる物、の合計サイズの最大値

これで再帰します
— 制約広げる (@noshi91) 2021年12月5日

今日も9時間ほどコンテストに出ていた。CodeChefで思うように問題が解けず、集中が切れてしまったと思っている。腰を据えて考えるのが苦手である。まあ今のところどうしようもない。精進しなければ成長せず、逆に精進していないので成長しないのは当たり前なのだ。

ところで、インターンの業務の進捗が悪すぎて、とりあえず今あるタスクの期限である火曜日まではそれに全力投球することになりそう。しかも今週木曜日の4年ゼミは僕の発表の番だ。非常にまずい。4年ゼミは前回の発表者がまだ結構残っているようなので、最悪は今週分として30分ほど話す内容だけ用意しておけばいいかな……という気持ちがある。