01/24(月)

先週の週記を投稿してからの話。日曜日に行われたJOIG本選の問題を確認した。ぱっと見た限り3問目まではコードゴルフできそうで、4問目は面倒、5、6問目はそもそも解くにあたって少し考える必要がある。まだAtCoder上に移植されていないので、今は頭を使わずスルーした。

学食に行って昼食を摂り、予約していた本を受け取った。その際下のようなことが起こった。特別扱いされているようで悪い気はしない。

生協の店員さん、ついに僕の顔と名前を完全に覚えたらしく、僕が書籍カウンターに並ぶや否や何も言わず予約していた本を出してきた
— こたつがめ (@kotatsugame_t) 2022年1月24日

昼食が変なところに入っていったのか、異常な腹痛を抱えつつ帰宅。少しコードゴルフをした。文字列を2進数として解釈するto_i(2)は、hexあるいはoctで置き換えられる可能性がある。具体的には $\mathbb{F}_2^n$ における基底を扱う場合がそうで、立っているbitの位置が各数で一様にずれるだけなので計算結果に違いはない。ABC236Fでは基底を持つのではなく生成可能なすべての元を持つことで縮んだことから、ほかの問題でもそういうことが起こらないか探していて気付いた。ちなみにそちらの短縮については、制約が小さくとも $n\le 300$ となっており、生成可能な元が超大量にあるためうまくいかなかった。

atcoder.jp

ハーメルンを読んでいたが、あまりにも眠い。本当はこのままインターン先定例会まで起きているつもりだったところ、さすがに耐えきれないと判断して午後2時くらいにベッドに倒れこんだ。

ちゃんと30分おきに目覚ましをかけていたのに、起きたら午後4時半、定例会が始まるちょうどの時間だった。先週と同じく焦りながらミーティングに接続。何とかギリギリ遅刻ではないような感じになった。先週金曜日の1on1から今日までに何らかの進捗を産もうとして、それで日曜日から今日にかけて徹夜っぽいことをしていたのに、実際はハーメルンを読んだりコードゴルフしたりで真に何もしていない。うっすい進捗報告スライドを生成して発表した。その後勉強会の発表を聞き、特に正しくもないコメントをしたりしていたら終了。

yukicoderのテスター作業をした。実に3週間も前に手を付けたセットの続きである。忘れてはいなかったが、セット後半の問題が残っていたので、その難しさから心理的ハードルがあってずっと放置してしまっていた。テスターを依頼されたときの話を聞く限り1月中に終わっていればよさそうな見通しだったので、何とか間に合わせたといったところ。

夜中から朝方にかけてyukicoderのテスター作業をした。年末に依頼されたものをずっと放置していた。結構数が多かったのでいくつかはまだ残っている。時間に余裕はあるらしいが、うっかりするとすぐ忘れてしまうので、注意したい。
週記（2022/01/03-2022/01/09） - kotatsugameの日記

テスター作業は午後11時半まで行っていた。一通り解いて問題文・解説のチェックを終え、達成感からボーっとしてTLを眺めていたら、JOIG本選の最短コードがatgolferに流れてきているのを見つけた。いつの間にかAtCoderに追加されていたらしい。どこかのタイミングで、JOI過去問をAtCoderに移植されている方が「JOIG本選をAtCoder上で解けるようになるまではしばらくかかる予定です」とツイートされているのを見たはずだが、ツイートが消えていてわからなかった。今日はないだろうと気を抜いていたところに不意打ちを食らい、急いでコンテストページを開いて解いた。

JOIG 2021/2022 本選過去問 - AtCoder

AはRakuで32B、Vimで34B。Bは最初にAWKでfor文を圧縮したコードを書いた。後から試しにRakuのcombinationsを使ってみたら、普通にやるとTLEのところ、文字列のリストを数値のリストに直しておく高速化を入れると間に合ってしまった。Cは普通にC++で書いてみるとループ1回で済んだので、すぐに短くなりそうに見えた。しかしAWKに移植すると答えが合わず苦戦。C++に戻すとそちらでもWAが出て、いろいろいじった結果累積和配列への代入タイミングが変わったのが問題だと分かった。 $X_i=0$ のとき、 $S_{i-0}+Y_i\le S_i$ のような条件式になる。ここで右辺の評価時に $S_i$ を更新すると、左辺の評価時と値が変わってしまうのだ。代入タイミングを修正してAC。

残りはC++で通しておくだけ。Dはmapでカウント。探索する場所が $9N$ 種類でそれぞれ $9$ 箇所の足し算が必要になるので、何も気にせず書くと900ms、mapに存在しない要素を構築しないようにしても670msになってしまった。EFはちょっと考える必要があると書いたが、実際はすんなり解けた。Eは絵の種類を添え字にする実家dp、Fは拡張dijkstraで、よく見ると辺のコストが決定できる。

その後公式解説を読んで、Eを上位2要素を持つ方法でRubyを使いコードゴルフしておいた。絵の種類に関する重複を省くのには、降順ソートしてからuniqを使うのが便利だった。午前3時就寝。

01/25(火)

午前9時前には起床していたはず。覚醒してからしばらくTLを眺めたり、YouTubeの動画を漁ったりすることが多いが、これをすると閲覧履歴の日時が復元できないため、自分がいつから起きていたのか定かでなくなる。午前9時というのはChromeでハーメルンを開いた時刻であった。そのまま学食にも行かずずっと読み続けて、午後2時くらいに少し起きだしてパンを食べたはず。しばらくしたらゲーセンに行こうかな、など考えていたのに、午後4時くらいに再度寝落ち。

次、午後10時半起床。またずっと読み続けて、午前4時に1作読了。「ウマ娘　ワールドダービー　凱旋門レギュ『4:25:00』　ミホノブルボンチャート」。

syosetu.org

非常に面白かった。先週の週記の最後にも書いたことだが、ウマ娘を知らないままで楽しめた。ただ一応、キャラの名前で検索してビジュアルを確認するくらいのステップは必要か。文中では毛・目の色と服のパーツという断片的な情報しか描かれないので、確認しないままだとイメージがあやふやになって読みづらかった。トレーナーのビジュアルも正直あまりよく想像できない。芦毛で顔がよいと書いてあるため、つまりは白髪イケメンキャラとなるはず。これを想像するのは難しい。競馬用語については雰囲気。筆者の語彙がやたら豊富で、知らない言葉が頻出してびっくりした。

以前RTA形式の二次創作について以下のようなことを書いた。今読んだ作品でもおおむね同じ面白さがある。しかし、主人公が操るキャラの扱いについては大きく異なっていた。以前読んだ作品は、主人公が操るキャラの行動がすべてRTA走者の視点から描かれた一方で、今読んだ作品では、おおむねRTA走者の選択に沿った行動をしつつ、細部はキャラが自身で補完しているような感じだった。その結果、RTA走者がボタン連打で読み飛ばしていた会話なりイベントが後々影響を持ってきてチャートが壊れることが何回かあって、それも面白かった。

もしかして、RTA走者の軽薄な描写と、それを原作キャラの視点から見るギャップを楽しむものだろうか？そういう第3者視点で主人公の凄さを語るシーンは僕の好みのものだ。
週記（2021/12/13-2021/12/19） - kotatsugameの日記

同作者の別作品、というか今の作品の過去IFを読み始めて、最終話近くまで行きつつ午前7時に就寝した。

01/26(水)

午後1時起床。

寝る前に読んでいたハーメルンを読み切った。「ウマ娘　ワールドダービー　称号獲得レギュ『1:11:11』　サイレンススズカチャート」。こちらは途中で止まっている。

syosetu.org

追加でいくつかウマ娘のハーメルンを漁ってから、学食に行った。昼食を摂り、予約していた本を受け取って帰宅。今日は僕のことを覚えている店員さんがいなかった。帰ってきて少しコードゴルフ。一昨日のJOIG-AがVimで縮められていた。ソートした後先頭と末尾を削除する方法しか考えなかったが、dcの加算コマンドの回数を制御していてなるほどという感じ。

atcoder.jp

ABC236-Eも縮められていて、こちらは取り返せた。入力の1行目を無視するため#を前置してコメントとして扱っていたところを、そのまま配列に入れて、代わりにmapの部分をmaxにするのが最短を取られたときの短縮。そこからアドホック気味に縮めた。初期値0の変数を用意していろいろ計算し、最後に0と比較している。ループ内部で計算してきた値の正負をチェックしており、よく見ると初期値と同じ値を用意できるならその値は0以外でも構わない。よって入力の1行目に書かれた値を初期値にして、これを比較時にまた使うため、maxの結果がその値になるようにブロックの返り値を固定（この場合は0に）した。

atcoder.jp

JOIG-DもAWKでコードゴルフされていた。各点の9近傍を探索しつつそこのカウントを1つずつ増やしていくと、結局そのカウントの最大値を求めることになるので、昨日説明したコードより定数倍がよく、AWKでも僕のC++コードより高速に動作している。いろいろ一般的なテクを組み合わせてさらに縮めた。

atcoder.jp

午後4時から1on1。本当は昼からその準備をするつもりだったのに、上のようなコードゴルフに時間を取られて30分くらいしか準備できなかった。正直に進捗が全然ないと言ったらペアプログラミングをすることになった。いろいろ確認を取りながら進められるのは楽しく、わちゃわちゃしているうちにかなり長引いて終わったのは午後6時を回ってからだった。書いたコードの量としてはあまりないが、やりたいことの準備みたいな部分なので、仕様の把握などに努めていたと考えればこんなものか。最後に進捗をGitHubにアップロードするとき、どのファイルを変更したのか覚えておらずgit add *をした結果、別のターミナルで開いたままだったVimによる一時ファイル.swpもaddされてしまい赤面。

結構遅い時間になったし微妙な眠気もあるのでしばらく迷っていたが、結局ゲーセンに行くことにした。自転車を漕いでいる最中に雨が降ってきて、帰りはヤバいかな～と思いつつ駐輪場に自転車を止める。イオンのフードコートで食事し、洗剤・柔軟剤・ほろよいの新味を購入していよいよゲーセン。

今日は新曲の精度が上手かった。しれっと1曲理論値が出ているほか、ラグトレインも理論値を出した。他にもいくつか狙ったはずがうまくいかず、微妙に伸びたくらい。今は判定Aが-0.2、判定Bが-1.0と結構いじっているつもりなのに、かなりFASTに振れる。特に14+などやると本当にひどいことになる。

今日精度上手いか？ pic.twitter.com/o7leTEvKFw
— こたつがめ (@kotatsugame_t) 2022年1月26日

ラグトレイン理論値！端フリック最高！ pic.twitter.com/ZO4BSkCput
— こたつがめ (@kotatsugame_t) 2022年1月26日

閉店したので帰宅。駐輪場から自転車を出した時点では結構雨が降っていた。夜遅く、感染拡大の影響もあって店が閉まっているかと思ったのに、思ったよりいろいろ開いていた。雨は立ち食い蕎麦屋で食事している間に止んでくれた。

帰宅して買ってきたお酒を飲みつつ日記を書き始めた。まだ今日の分に追いついていないうちに1缶空き、眠気が尋常ではなくなったため就寝。午前4時だった。

01/27(木)

午前10時起床。

しばらくYouTubeを見ていた。チュウニズムに最近追加されたVTuberのオリジナル曲を昨日プレイしてきて、いくつか耳に残るものがあったので寝る前に検索して聞いたのだが、ほんの数個動画を再生しただけなのにもうおすすめ動画に配信の切り抜きがいくつも上がってきていて、その感染力とも言うべきものに驚かされた。

HHKBのコンテストで学生応援賞に当たったらしい。以下のように自分より上に学生が4人いると思っていたので、かなりびっくりした。

全完14位。学生5位に滑りこんだかと思って喜んでいたものの、トップページを確認すると4位以下は飛び賞しかなくがっくり。
週記（2022/01/10-2022/01/16） - kotatsugameの日記

1年くらい前のコンテストでもいい感じの位置に滑りこんで、その時貰ったキーボード（日本語配列・白）をずっとメインで使っている。今回2台目が貰えることになって、相変わらず無刻印への憧れはあるものの、実用性を考えて今度は日本語配列・墨を指定することにした。普段ずっと日本語配列を使っている以上、キーボード1つだけ英字配列にするなどというのは不便なだけである。

HHKB プログラミングコンテスト 2020の受賞メールが届いていた。学生3位ということで、HHKBのキーボードがもらえる。
週記（2020/10/19-2020/10/25） - kotatsugameの日記

学食に行って食事し、パンやおにぎりを購入して帰宅。午後1時からオンラインでゼミに参加した。実はもうラストまで教科書の内容を発表する機会はないようなので、今日はひたすら気を抜いていた。日記を書いたり少しコードゴルフをしたりしつつ、午後4時半くらいに終了。すぐ布団に倒れこんで、そのまま寝てしまいそうになったものの、来客があって何とか意識を取り戻した。

来客とは、隣人かつFFの方であった。一度日記でも言及している。この度引っ越すことになられたようで、わざわざその挨拶に来てくださったのだ。手土産に仙台市指定ごみ袋を頂いたので、何かお返ししようと思って昨日買ってきたお酒、ほろよい1缶をお渡しした。もう荷物も運びだされた後らしかったので、ちょっと邪魔だったかもしれないと後悔。一方こちらが頂いたごみ袋は、邪魔にもならないしあると確実に役に立つしと非常に嬉しいチョイスであった。

ちょうど隣人が帰宅したので、挨拶でも……と声をかけた。ちょっとした立ち話になって、「もしかしてこたつがめって名前のアカウントでTwitterやってますか？」と聞かれた。大正解である。FFの方だった。
週記（2020/09/28-2020/10/04） - kotatsugameの日記

ラノベを1冊読了。「パシられ陰キャが実は最強だった件」。YouTubeの漫画動画が原作らしい。「クラスの大嫌いな女子と結婚することになった。」が売れたので味を占めたか。1巻では、ヒロインがヤンキーに絡まれてそれを主人公が助けるという流れが2回繰り返され、仲良くなっていった。助けが間に合わないということは当然なかったが、それでも絡まれている間の描写は結構読むのがつらかった。主人公がどうしようもないところで味方キャラに危害が加えられる・加えられそうになるという描写は苦手だ。しかしそういうところでヘイトを溜めた分、主人公が無双するシーンが格段にスカッとするという効果もあって、読んだ後は面白かったという感想を抱いた。

食事しようと弁当を解凍したのに、また布団に倒れこんでしまい、午後10時ちょっと前から午前0時まで寝てしまった。起きると弁当は冷え切っていたし、CF div.1も始まっていた。いいとこなし。仕方ないので弁当を温めなおして食べ、ラノベをもう1冊読んだ。

「辺境都市の育成者」5巻。面白かった。主人公に好意を抱いているキャラが大量に出てきてよくわからないまま読んでいたが、この巻はそのうちの2人が特別であるような書き方をされていたので、なんとなくストーリーの整理がついた。ラストシーンで主人公がメガネを外したイラストが描かれ、これまでの温和な印象を一気に塗り替えるような精悍さが見られてかなり好み。口調や一人称がガラッと変わるのも良い。エピローグで「勝手に呼んだ挙句使い捨てた世界」というようなセリフがあった。純粋なファンタジーに見えて実は異世界転移ものだったのかも知れず、びっくり。よく考えれば、名前のスタイルが作中世界の人物と微妙に異なる人物も出ていたので、それも伏線になっていたのかもしれない。後書きで盛んに6巻が出るか心配していたのが気になる。売れ行きは好調に見えるので、作者の作業量の問題だろうか。ぜひ続刊してほしい。作業量といえば、この作者はデビューから3年間で2シリーズ14冊を刊行していることになって、いくらネット小説の書籍化だからとは言えかなりの速筆である。加筆修正も大量に行っているようなので余計すごい。

コードゴルフを1問。Pythonのheapqを使う際、最初から列に要素があるなら、そのリストをheapifyする必要がある。これは何をしているかというと、うまく並び替えて大小関係の条件が成り立つ二分木を構築しているのだ。heapifyはリストを引数にとってそれを直接更新するので、実行はちょっと面倒である。ところが、実はheapifyでなくとも、リストをソートしさえすれば求める大小関係は自動で成立する。この際sortedを用いることで、リストを変換しつつ変数に代入することができるようになる。また関数名も1文字短くなっている。こういう更新がatgolferに流れてきたので、そのまわりを弄って最短を取っておいた。

heapq --- ヒープキューアルゴリズム — Python 3.10.0b2 ドキュメント

atcoder.jp

午前9時くらいに布団に入り、そこからハーメルンを読みふけって、正午就寝。

01/28(金)

午後8時半に目を覚まし、少しハーメルンを読み進めて午後9時半にまた寝たような記録がある。

次に午前1時に起床。またずっとハーメルンを読み続けて、午前6時に1作読了した。「ハリー・ポッター RTA　ヴォルデモート復活チャート」。

syosetu.org

エタり気味だが、面白かった。原作の設定をかなり深く掘り下げているようで、その努力が後書きから伺える。また、必要の部屋を最初から使えたり、一方で魔法は本で読むか実際に見ないと解禁されないという設定が、いい感じに原作知識を縛っていて面白い。キャラも好き勝手に動いていて、RTA走者が気にも留めなかった些細な描写が後々の小説パートでどういう意味だったか明かされ、ちょっとした障害になったりするギミックも手が込んでいる。またRTAとはあまり関係ない点で、原作や多くの二次創作で不遇だったキャラを立てるような背景が創作されているのもよかった。

また別のRTA ハーメルンを読み始めた。今度はSAOの二次創作である。SAOの1層からの攻略を描く「ソードアート・オンラインプログレッシブ」というシリーズがあって、それをもとに書いているように見える。自分はそのシリーズを1巻から積んでいるため、どうしてもネタバレになってしまう。読み進めるかどうか迷い、結局ずるずると読み続けていた。午後1時半就寝。

01/29(土)

午後3時、弁当の配達で一瞬起きた。またすぐ寝て、次に午後8時過ぎ起床。シャワーを浴びて食事し、午後9時からARC134。

AtCoder Regular Contest 134 - AtCoder

Aはよい。Bは貪欲だろうという読みがついて、しばらく考えても正しそうなので実装。文字の昇順、インデックスの降順でソートしておいて、文字列の先頭から順番に「その位置とこれまで使った一番左の位置の間にあるインデックス」が見つかるまで、先ほどソートしたものの先頭から値をpopしていく。最後に、交換して辞書順で小さくなるかを確認する。

Cは言い換えが面白かった。 $1$ が書かれたボールと $2\dots N$ が書かれたボールを1つずつ組みにしておけば、それらを適当に箱詰めした後、残った $1$ のボールを各箱に1つ以上入れる場合の数になる。これはすべて重複組み合わせで書けて、それぞれ $O(K)$ かける方法で求めれば間に合う。しかし $a_1-\sum_{i=2}^N a_i$ をint型で扱ってしまい1WA。

Dもすんなりいった。まず、 $a_{1\dots N}$ の最小値を1つだけ使うか、それとも全部使った後さらに付け足すかに分かれる。付け足す場合は、 $a_{1\dots N}$ の最小値をとる最小のインデックスを $i_0$ としたとき、 $a_i\lt a_{i_0+N}$ であるかあるいは $a_i=a_{i_0+N}$ かつ後ろを1つずらしたときに辞書順で小さくなればよい。後者の判定は隣接項の大小関係のチェックになるので、最初から計算しつつやっていけば線形時間で求まる。しかしこのチェックで不等号の向きをミスし、しかもその修正を2回も失敗したため、3WA。値を入れ替えるべき場所が2か所あり、最初にそのうち下だけを入れ替え、次に「上だけ入れ替えた」と勘違いして下をもう一度入れ替え（つまり最初に戻し）、3回目でようやく気付いた。最高にアホ。

Eは頑張った。2要素・3要素で実験した感じ、負けるパターンは「1のみ」「2のみ」「4と8のみ」「12の倍数の組み合わせ」に分かれるようだ。手作業の実験をもとに正当性を考えることで、何か見えないだろうか。まず2以下の数しかない場合はよい。3以上の数がある場合、奇数が存在すれば $m=2$ で操作することで勝てる。また偶数しかない場合も、4で割って2余る数があれば $m=4$ で操作することで勝てる。残りを $12k+0,12k+4,12k+8$ と書いて組み合わせを考えてみると、「4と8のみ」「12の倍数のみ」以外は $m=3$ と $m=12$ のどちらかで操作することで勝てるようだ。これでとりあえず正当性が分かった。

しばらく12で割った値とにらめっこしていたが、 $m=5$ や $m=16$ で操作するケースがあって厳しい。と、残り30分を切って、ふと $\lfloor 200/12\rfloor=16$ であることに気づいた。つまり12の倍数の集合をbitDPで数え上げることができて、残りのこまごまとしたケースを処理することで負ける場合の数を全部求められる。 $K=16$ として $O(NK2^K)$ のbitDPと $O(K2^K)$ に定数倍 $200$ がついた判定フェーズになって、手元で微妙に時間がかかるもTL 6secを信じて提出、すんなり500ms弱で通った。

5完26位。4ペナが効きすぎるほど効いている。

コードゴルフ。これは以下に書くCodeChef後のものも含む。A問題は列がソート済なので、dcで書ける。適当にガチャガチャしていたら何もかもがうまく作用して、当初想定していたよりずいぶん短く書けた。Bは前のほうに持ってくる文字を順に試して、rindexを使って位置を検索するのが短くなった。Cは想定解が $O(NK)$ とRubyでは通らなかったので、Crystalを持ち出した。相変わらず $a_1-\sum_{i=2}^N a_i$ が大きくなりすぎてオーバーフローのREを起こし続けていたが、答えが0になる場合変数の初期値を0にするようにしたら、オーバーフローするようなケースでは掛け算した値が0になるので問題なくなった。以降は手付かず。

午後11時半からCodeChef January Lunchtime 2022 div.1。

https://www.codechef.com/LTIME104A

PERMXORSUMは、bitごとに立っている数と立っていない数を数えて、立っているbitができる限り無駄にならない場合を考えたら通った。つまり、 $2^i$ のbitが立っている数が $1\dots N$ に $c_i$ 個あった場合、答えに $\min(c_i,N-c_i)\times 2\times 2^i$ を足す。コンテスト中は証明しなかったが、後からTLに流れてきた方法というか、構築方法が天才的だった。 $N$ 以下で最大の2べきを $2^b$ とすると、 $2^b\dots N$ と $2^b-(N-2^b+1)\dots 2^b-1$ （の逆順）を対応させることでbitwise ANDが0であるようなペアばかりを作ることができ、その上残りもまた $1\dots N'$ の形をしている。よってこの要領で組にしていけば「立っているbitができる限り無駄にならない」という条件を満たすことができる。最後に高々1個余るが、それはどうあがいても無駄になってしまうbitたちである。

CIRCPRMRCVRYはよくわからない。 $A_i=K$ となるような $i$ を集めてきたとき、 $N$ の制約から2つの間隔（の円周上で短いほう）が $K$ 以下なので、値の大小関係がわかる。その大小関係において最大だと分かるものが高々1つあるはずで、そこを $N$ と確定してよい。そのようなものがなければ答えは $-1$ である。さて、今 $N$ が確定したとして、そこから遡って $K$ 個ぶん $A$ の値をインクリメントし、今のチェックを繰り返す。これで構築できればそれが答えとなる、はず。サンプルを手で試しているうちに思いつき、いかにもよさそうなので出したら通った。実装は遅延セグ木だったりsetだったりを使って結構大変だった。

PERMDELは端から2要素しか削除できないため、真ん中を決め打って左右の操作列を数え上げた。数え上げは次のようになる：例えば左を考えると、 $(i,i+1)$ が左から2要素になっている場合の数をdpで管理して、そこから $i+1,i+2,\dots$ とどこまで削除できるかをチェックする。 $i+1,\dots,j-1$ をこの順で消す場合を、最後に $i$ を消して $(j,j+1)$ を残す操作列としてdpに足しつつ、真ん中が $j$ になる場合として別に保存しておく。この $j$ は区間になるので、遅延セグ木の区間加算で扱える。提出すると全然答えが合わなくてひっくり返ったが、 $N=5$ を試すとすぐわかった。左右をどの順で操作するかも考えなければならなかった。

残りは部分点のみ。DIVDISTは全方位木dpを書いて35pt。ANTHRXORTASKは $K=1$ を貪欲。空きがある中で最も上位のbitを立て、以下のbitはXORする値たちを見ながら桁ごとに総和が減らないように決める。とりあえず $K=1$ は通って15pt、これを $K$ 回繰り返したら通らないかと思ってもう一度出してみるも、 $K=2$ からWAになるケースがあるようだった。以上350ptで14位、2614→2662(+48)とhighestを更新した。

朝までずっと日記を書いていた。そこからラノベを読み始め、1冊読了。

「美少女エルフ（大嘘）が救う！弱小領地」。非常に面白かった。ストーリーや終盤の山場はシンプルに劇的で良い。とはいえ経済の話を置いておくわけにもいくまい。1巻での経済的な発展は、まず出自等による信用を使って証券を発行し、その対価に得た貨幣を元手に紙幣を流通させるまでだったと認識している。後者が特徴的で、貨幣（銀貨）と兌換できる紙幣を発行するのではなく、土地等と兌換できる紙幣を発行していた。それも宝くじの景品として、である。確かに紙幣の形にしなければならないほど銀貨が流通していないような描写だったので、こちらのほうが現状に即しているのかもしれない。宝くじによって流通させるというのも初めて見た。さて、すでに経済を扱うなろうやラノベをいくつか読んだことがあるが、やはり難しい。より現代に近づいた舞台だと、すでに成立している資本主義に乗ってお金儲けをすることになるので、読み手としてはある程度の金融商品に対する知識が前提となる。そこまでいけば正直よくわからなくても気にならない。一方このラノベのように一から経済を作り出していく話では、自分でも理解できそうなラインの話をされるため、何とか飲み込もうと必死になって頭を働かせることになる、ように思う。

もう1冊本を開いて少し読み進め、午後2時就寝。

01/30(日)

午後8時半起床。食事してABC237。

AtCoder Beginner Contest 237 - AtCoder

Aは微妙に書きにくい。どう書いたら短くなるのかがわからないため、安定を取ってRubyで書いておいた。次にBを開くも、解法がすぐには見えなくて戸惑う。少し考えて、逆順に見れば列の先頭と末尾に値を入れる操作に言い換えられるとわかり、実装して提出。しかしサンプルからWAが出ているうえにREも出ている。空白区切りのところを実装の簡略化のため改行区切りで出力していて、そこも見られているのかと思い修正するも、またWA。絶望しつつ再度問題ページに遷移すると、見覚えのない問題が載っていた。びっくりして問題一覧を見に行くと、D問題の問題名が問題ページに載っていたものに一致している。開いてみると先ほどまで解いていた問題だったので、今までB問題だと思っていたのはD問題だったようだ。後に知ったことだが、コンテスト開始から5分弱、B問題の問題文がD問題のものになっていたらしい。

Dに提出しなおして、再度B問題に取り組む。これはOctaveで転置すると簡単。出力に手間取るもすぐACし、そこから少しだけコードゴルフもしていた。次にC問題。先頭と末尾の'a'を削除してから回文判定するコードをPerlで書いて投げると、WAとTLEが出る。TLEは正規表現が遅いからだろうが、WAも出ているので困る。冷静になると、左端の'a'の文字数は右端の'a'の文字数より少ない必要がある。その条件も含めたコードをC++で書いて通した。

Dは先ほど通していた。Eは始点と終点の標高がわかるので、移動における楽しさの変動はその差に加えて「どれだけ余計に登ったか」がわかればよい。これで辺の重みが非負になるので、dijkstraで解ける。FはLISをdp配列の二分探索で求めることを考えて、その際のdp配列の内容をそのままdpの添え字にすればよい。Gは $X$ 未満の数の位置を管理する列と $X$ より大きい数の位置を管理する列を2つ用意して、ソートはそれぞれの列から $X$ 未満の数・ $X$ より大きい数の個数を取得して左右に振りなおせばよい。区間SET区間SUMになる。Exは各位置から右に最も長い回文だけ考えてよさそうだということまで感づいていたが、最大200頂点のグラフの最大独立集合を求めることになって絶望。解けなかった。

Bに2回提出した分が削除され、7完1ペナで41位。

しばらくコードゴルフして、午後11時半からCF #769 div.2。

Dashboard - Codeforces Round #769 (Div. 2) - Codeforces

Aは $n\ge 3$ なら必ずNOになる。BはペアにしてXORを計算するのかと思ってARC122-Dを思い出し、binary trieを貼ろうとしたところで誤読に気づいた。この問題では、 $n$ 以下の最大の2べき $2^b$ を取ると、どうやっても $2^b$ のbitが立っている数と立っていない数のXORが出現するため、答えは必ず $2^b$ 以上になる。 $2^b-1,2^b-2,\dots,0,2^b,2^b+1,\dots,n$ と並べるとその下界が達成できる。

D - XOR Game

Cは非常に難しい。大体はORを取る3つ目の操作で一致させるんだろうなと予想がつく。実際、ORの操作で一致しなかった場合は必ず $a\gt b$ となって、この時 $a-b$ の値を小さくするためには2つ目の操作で $b$ をインクリメントするしかないため、追加で $a-b$ 回操作することで一致させるのが最短だとわかる。この考察によって、ひとたびORを取った以降の手順が一意に定まる。 $a$ を $x$ 回、 $b$ を $y$ 回インクリメントした後ORを取る、と固定すると、一致させるのに必要なコストは全体で $x+y+1+( (a+x\mid b+y)-(b+y))=x+1-b+(a+x\mid b+y)$ と書ける。

まず $a+x\ge b$ の場合を考えよう。今 $y$ の値は非負ならば何でもコストに影響しないため、 $y=a+x-b$ とするのが良い。このときコストは $x+1-b+(a+x)$ となって、これは $x=b-a$ の時に最小値 $b-a+1$ を取る。しかし、最初からインクリメントだけで一致させるコストがより小さい $b-a$ なので、 $a+x\ge b$ の場合は考えなくてよいということが分かった。そんなことを計算しなくても、 $x\ge b-a$ 回もインクリメントすれば当然途中で一致する。よって $0\le x\lt b-a$ となり、これは $\sum b$ の制約が存在することから全探索できる。 $x$ を決め打った時、 $y\ge 0$ の範囲で $(a+x\mid b+y)$ の最小値を探す必要があるが、これについては $a+x$ と $b$ のbitを上から見て行って、最初に $(a+x,b)=(1,0)$ となる位置より上は $b$ から、より下は $a+x$ からbitをコピーしてくると得られる。

コンテスト後にTLで $a$ と $b$ のどちらかしかインクリメントしないということを知った。上で述べたことの延長で考えてみる。まず $(a\mid b)=b$ となる場合を除く。 $(a+x\mid b)=b$ の場合、 $a$ しかインクリメントしなくてよいためOK。残りのケースは $(a\mid b)\gt b$ かつ $(a+x\mid b)\gt b$ となって、このとき $x\gt 0$ を考慮しなくてよいことを説明する。 $(a\mid b)-b$ （つまり $(a,b)=(1,0)$ となるbitの集合）と $(a+x\mid b)-b$ を考える。 $(a\mid b)-b\le (a+x\mid b)-b$ であれば当然 $x=0$ のほうがコストが小さい。 $(a\mid b)-b\gt (a+x\mid b)-b$ であれば、 $(a\mid b)-b$ で立っていた最上位のbitを桁上がりさせて $b$ に吸収させたとわかって、このとき桁上がりしたbitより下は全部0にできるため、 $(a+x'\mid b)=b$ なる $0\le x'\lt x$ が必ず存在する。以上より、 $(a+x\mid b)=b$ となる場合か $x=0$ のみ考えてもコストの最小値が求まると分かった。前者の $x$ を頑張って求めると、全体で $O(\log b)$ が達成される。

Dは、書き換える値を非常に大きな素数だと思うと、そうやって書き換えた値で列を区切ってそれぞれで条件を満たしていればよいことになる。この書き換えは区間スケジューリングを考えると貪欲に行うのがよい。あとは書き換えが必要かのチェックで、これは $r$ を固定すると高々1つの $l$ をチェックすることになるとわかる。なぜなら、 $l$ が左に行くにつれて $r-l+1$ の値は単調に増加し、一方 $\gcd(b_l,b_{l+1},\dots,b_r)$ の値は単調に減少するからである。この増加と減少がちょうど交わる点を二分探索で求めればよい。DisjointSparseTableを貼って $O(N\log N\log \max a_i)$ 。ACLのセグ木で二分探索しても同じオーダーになるだろう。

E1はしばらく迷走したが何とか解けた。 $f(x)$ の値に対してそれを達成できる最大の $x$ を求める。追加の辺なしではたどり着けない頂点をリストアップし、それらの頂点だけを考えた時の直径 $d$ を求めると、 $x$ の最大値は $f(x)-\lceil d/2\rceil$ となる。 $d$ を $f(x)$ の降順に求めることを考える。毎回double sweepするとE1が解ける。実は、直前の直径の端点が $u,v$ で今頂点 $w$ を追加したとすると、直径は必ず $u-v,u-w,v-w$ のうちどれかになることがわかる。今見ている頂点たちのうちでは、 $u,v$ のどちらかが必ず最遠の頂点になるからだ。木の2頂点間の距離はLCAを求めることで高速に計算できるので、これでE2の制約でも直径の更新ができる。

55分でノーペナ全完、システスも全部通って、なんと優勝した。CFのコンテストで優勝するのは初めてな気がする。

CFのコンテストで初優勝 pic.twitter.com/TImC3dr3Lb
— こたつがめ (@kotatsugame_t) 2022年1月30日

ABCのコードゴルフについて。A問題は難しい。dcで頑張って数値比較をするよりも、精度を設定するコマンドkがちょうど $2^{31}$ 未満の非負整数しか受け付けないという性質を利用するほうが短くなるようだ。同様の性質を持つコマンドはもう一つあって、Rである。試してみると、絶対値が $2^{31}+1$ 以下の整数しか受け付けないらしい。つまり、 $N\ge 0$ に対しては $N+2$ を、 $N\lt 0$ に対しては $1-N$ を作って、それでRすることにより、条件に応じてスタックを弄ることができる。これで縮めた。ただもうちょっと縮まないかと思って、ある程度見当を付けたdcコードを生成して境界付近の $N$ でチェックするという方法でしばらくプログラムを回してみたところ、なんと1B縮んだ。 $N\lt 0$ に対しては $-N-1$ を作っているらしい。

いやそれは違うだろう。 $N=-2^{31}-1$ のとき $|-N-1|=2^{31}$ となって、Yesを出力してしまうはずだ。そう思って手元で実行してみると、信じがたい現象が発生した。どうやら、ちょうど $\pm 2^{31}$ である場合も受け付けないようだ。この問題では、境界ギリギリの値はちゃんとテストケースに含まれている一方、少し離れた値は全く含まれていないため、このようなコードでも通るらしい。 $N=-2^{31}-2$ や $N=2^{31}-2$ で落ちる。

BはOctaveよりもRakuでzipするほうが短くなった。[Z]だと、引数になるリストのリストがいったん展開（Slip）されるらしく、Rakuで65536要素以上のリストをSlipするとREになってしまうため動かない。今回はzipと[Z]が同じ文字数で助かった。ちなみにこのSlip制限の仕様は相当大きなテストケースでないと顕在化しないため、意気揚々と出したコードが謎のREを吐いて絶望することも多い。CはとりあえずPerl。DもPerlで書いたが縮められた。出力をjoinする空白ごとリストに入れるのは頭がいい。EはnetworkxがTLEしてしまい、仕方なくPythonのheapqで実装したのに、ACLの最小費用流を使うほうが短くなった。最小費用流をdijkstraの代わりに使うのは新鮮。FはLISのdpテーブルを直接Hashのキーにした。Rubyだと微妙にTLEしたのでCrystalで書いた。

GはTL 8secということで、 $O(NQ)$ を通せる。最初は区間SUMのループと区間SETのループ2つ、合計3つで書いていて、pragmaをつけて何とか通り、場合分けしてSETする値を定数にしないとTLEになるなど大変だったが、区間SETにmemsetを用いることで爆速になった。現在はClangではおまじないなしでも通っている。 $X$ との大小関係を正負で表しているので、memsetでも必要十分な代入が可能なのだ。区間SET2回のうち、片方を区間SUMのループと同時に行わせることで、700msほど遅くなった代わりにコードが縮んだ。それも許容できるくらい時間に余裕がある。

atcoder.jp