09/05(月)

午後4時過ぎ起床。布団から何とか這い出して、半からインターン先の定例会へ。

進捗報告は先週とほぼ同じで、試したことがダメだったのでまた新しい方針を実装しますというだけ。勉強会はPythonについて、3.6以降のバージョンアップに伴う新機能を紹介するものだった。このあたりでコードゴルフ的に一番インパクトがあったのは代入式、いわゆるセイウチ演算子だろう。それに関しても面白い話が聞けた。

Pythonに変数のスコープなどあってないようなものだが、リスト内包表記だけは特別で、ちゃんとスコープを作るらしい。このことはこれまでは、ループ用の変数が外の変数と被っていても外のものを書き換えないということを意味していた。ところが今、リスト内包表記で実行するループ内で新しく変数に代入する場合、それはループを抜けても保たれる。つまりスコープはもはや正しく動作していない、という話があるそうだ。

これに関係するのかどうか知らないが、リスト内包表記のリスト部分で代入式を使おうとすると文法エラーとなる。よく引っかかってしまい、おかしな制限だと思っていた。裏にこういう背景があったのかもしれないと思えば納得もできそう。

終えてからはずっと先週の日記を書いていた。ARCの残りと5hについてを書き上げればとりあえずは完成なので、これまでに比べると完成までは非常に近かった。ちゃんとそこから校閲まで済ませて、午後11時過ぎに投稿。

しばらくコードゴルフをした後、午前1時くらいに布団に入ってハーメルンを読み始めた。午前3時過ぎ寝落ち。

09/06(火)

午前8時過ぎに目を覚ました。昨夜読み始めたハーメルンを読了。「知識も無いのにポケモン世界にチート転生したが何も面白くない」。

syosetu.org

主人公にはポケモンバトルの才能という転生チートがある。しかしそれの実現方法があまり好きではなかった。ネタバレになってしまうが、主人公がチートに操られる感じだったのだ。能力に振り回されるのともまた違うとは言え、やはり基本は主人公が能力の手綱を握っていてほしかった。そういう能力を持っているが故の性格で主人公がポケモンのことをあまり顧みていないのも辛い。

眠気を待ちながら別のハーメルンを読んでいたが一向に眠れなかったので起き上がった。ゴミを出してからしばらくコードゴルフして、午後1時過ぎに学食へ。昼食を摂り、予約していたラノベを受け取って帰ってきた。

DMOJのコンテストが終わっていた。先週土曜日深夜の3時間で参加したもの。ここに感想を書いておこう。

An Animal Contest 7 - DMOJ: Modern Online Judge

P1はConnect 4を知らず問題文が読めなかった。 $w\times h$ の盤面にトークンを「落とす」というのだから実質3次元の盤面なのかと思ってしまった。張られていたWikipediaへのリンクから実際の画像を見て理解。それからもコーナーケースにはまり込んで2WAした。 $h=1$ なら先手四つ後手三つのトークンのため $w\ge 7$ が必要。 $w=1$ なら交互に積み重なるだけなのでダメ。残りは自明な条件の $h\ge 4\lor w\ge 4$ をチェックすればよい。

P2は出力する木の根を指定していないのにジャッジで先祖・子孫の関係を使うらしく、パッと見意味不明でclarでも投げようかと思った。しかしよく考えると、元の木における関係を見ることで出力の条件からどの頂点が根であるべきかは高々一意に定まる。そこまでジャッジで面倒を見てくれるのだろうと判断して解いた。

解法は深さの偶奇で木を分けるというもの。これで $K=2$ が達成できて最適、と思って書き始めたが、根と隣接している頂点を一つの木にまとめられず、もう少し考えることになった。考えた結果、根と隣接している頂点はすべて出力した木のどれかの根である必要があるということが分かったので、 $K=2$ とは限らないものの $K$ 最小は達成できている。出したら通った。

P3は $i$ を固定して $i\lt j\le N$ に対する和を一度に求める。一番近いポータルからの距離はまとめて線形時間で計算できるので、最初に求めておく。これを使うとある地点からある地点までポータルを経由して移動するための時間が計算できる。

さて、よく見ると、直接向かうよりポータルを使うほうが早く着ける地点は右端からの区間になっているため、その端点を見つければ適当な前計算で一気に和が求まる。この端点のインデックスは、直接向かうときの時間を考えることで、 $i$ が増えるにつれ単調に増加するとわかる。よって尺取り法の要領でこれまた線形で求まる。 $N\le 10^6$ でTL 1secと $\log$ を付けた解法を落としに来ている制約。最初は遅延セグメント木と二分探索を使っていたが、 $\log$ 二つで当然のようにTLEしたため書き換えた。

P4は大変。一か所にしか出現できないものと端に出現するものは確定し、それ以外は出現できる範囲が区間になる。また答えとなる数列において、注目している数より大きいか小さいかだけ考えると、最初にあったところから左右それぞれ出現範囲より一つ広い位置まで、これが交互に現れなければならない。以上の条件を実装したら通った。これ以上詳しい解説を書きたくない。assertを大量に入れつつ実装し、ランダムケースでチェックすることで何とか解けた。

P5は典型。木においてすべての頂点を通る最短パスは、直径の端点を結び、直径上の辺を1回、それ以外の辺を2回通るようなものである。今回は特に、通る頂点を順に並べたものが辞書順最小となるパスを聞かれているので、まず直径の端点となれる最もインデックスが小さい頂点を求めなければならない。全方位木dpで最も遠い頂点までの距離を管理したが、よく考えると1本直径を見つけてその端点から直径と同じだけ離れた点を列挙するほうが簡単だった。

あとはdfsっぽく計算。直径上にないため後から親まで戻ることが確定しているような頂点は、記録するタイミングをある程度自由にずらしてよいので、もっと小さい番号の頂点が下にあればまずそちらに降りて行く必要がある。これを忘れて3WAした。

P6はbitsetを使った愚直を書いて終了間際に最初の部分点だけ取った。合計510点で2位、レートは2475→2666(+191)でhighest。今回は何とかなったが、やはり中盤の重実装がつらい。後ろのほうにド典型が置かれていることが多いので、詰まったときもちゃんと先の問題を確認するよう心掛けたい。しかし実際のところP4の公式解説はかなり頭が良かったので、作問者から見れば別に重実装でもなんでもなかったようだ。

しばらくインターンに関するコードを書いて、午後6時から1on1に臨んだ。今回試した方針は非常によさそう。まだ試し切れていない細部の実装について画面共有しながら少しずつ手を加えてみて、平均的にかなりうまくいっている出力が得られた。これ以上はハイパラ調整に足を踏み入れることになるが、今は出力の評価を目で見るだけで行っているし、手持ちのデータも少ないので、それは今するべきことではないという結論になった。

ということでタスクが一つ完了。次は何をすればよいかと聞いて一つ紹介され、関係するコードの在処を含めてしばらく説明を受けた。以上2時間くらいのミーティング。終盤眠くなってまたしても意識を飛ばしてしまったタイミングがあり、かなり申し訳ない。今日急に新しいタスクをくださいと言ったのがミーティングを長引かせてしまった要因。眠気に耐えられないならちゃんとそう白状するべきだった。

布団に滑り込み、午後8時半から午後11時まで仮眠を取った。起きて食事し、午後11時半からCF #819 combined。

Dashboard - Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 - Codeforces

Aは $(l,r)$ として $(1,n-1),(2,n),(1,n)$ のどれかしか考えなくてよい。2乗が通る制約だが、それぞれ線形時間で計算できる。Bは最大の要素以外は同じ数を偶数個ずつ用意する必要がある。ほとんどを $1$ で埋め、 $n$ の偶奇に応じて残り一つか二つを調整する。Cは開きかっこの深さを見て、同じ深さのペアで間により浅いかっこがないものを繋ぐことになる。stackで管理。

Dは辺の数が $(n-1)+3$ 以下なので、全域木に高々 $3$ 辺追加したようなグラフ。とりあえず全域木を一つ取って赤で塗り、残りの辺を青で塗ることを考える。青い辺がループになっていなければよい。ループだった場合は、青い辺 $uv$ を適当に取り赤い辺で $u-v$ パスを作ると、そのパスは必ず長さ $2$ 以上だから、パスの適当な1辺と色を交換することでループを解消できる。3辺を乱択してループができていないかチェックする解法もあるらしい。

Eは $p_i-(p^{-1})_i$ において $i\leftarrow p_i$ とすることで $(p^2)_i-i$ が得られる。これは逆順列の定義から導けるし、 $p$ から $n$ 頂点 $n$ 辺の有向グラフを作って $(p^{-1})_i\rightarrow i\rightarrow p_i$ というパスを観察することでも言える。今 $p$ は順列だから、条件を $\forall i.\;|(p^2)_i-i|\le 1$ と書き換えることができ、ここから $p^2$ の形を観察すると各ループが $i\leftrightarrow i$ または $i\leftrightarrow i+1$ となることがわかる。

$p^2$ がそのようなループからなる $p$ とはどのようなものか。 $p$ における長さ $L$ のループは $p^2$ において、 $L$ が偶数の時長さ $L/2$ のループ2本に、奇数のとき長さ $L$ のループ1本になる。よって $p^2$ における長さ $1$ のループはもともと長さ $1$ だったか長さ $2$ が分裂したものであり、長さ $2$ のループは長さ $4$ が分裂したものである。ここまでわかれば、あとは $p^2$ における長さ $2$ のループの個数を全探索して組み合わせ計算を行うことで答えが求まる。

このような $p^2$ に関する考察は何回か見たことがあるし、特につい最近もTLで流れてきた。その時改めて自分の中で解決しておいたので内容を完璧に覚えており、今回スムーズに考察を進められた。

自己写像の(合成に関する)平方根(の存在判定・構成)ってむずいな。自己同型なら割と簡単
— Masaki Hara (@qnighy) 2022年9月5日

Fは面倒。 $c_i\leftarrow c_i+\sum_{j=1}^{i-1}d_j$ と定めることで信号間の移動時間を $0$ にしておく。実家dpを考えると、区間 $[L,R)$ で青になる信号に突入した時、点 $L$ における値は新たに計算、区間 $[L+1,R)$ の値はそのまま、残りは $\infty$ という更新ができればよい。同じ値を持つ区間をまとめれば、信号ごとに区間をいくつか削除して定数個足すことで表現できるため、更新が十分高速。点 $L$ における値はそれ以前の $\infty$ でない最も近い点を選んで遷移するだけでよい。

Gは面白い。まず最初に $a$ がすべて等しい場合を取り除いておく。これはどのような順序で操作しても条件を満たす。さて、最終的に揃える先を $A$ とする。これは $A\ge \max a$ を満たす。 $a_i\lt A$ なものを抜き出して同じ値をまとめると、そのうちで $b_i=1$ となるものは高々一つしかない。なぜなら、二つ以上ある場合、それらの間で操作後の値が食い違ってしまうから。

ここで $a_i=\min a$ を調べると、実は $A$ が決まる。まず $b_i=0$ がある場合、対応する $a_i$ は操作しても絶対に変わらないので、 $a_i\lt\max a\le A$ より不適。よって $b_i=1$ である必要があり、先ほど見たようにそのような要素は高々一つ。特に今回はちょうど一つであり、 $A=n-1+\min a$ となる。あとは $a_i$ が同じ要素をまとめ昇順に見て、操作列に挿入することを考えればよい。挿入箇所が一意に定まるのでうまくいく。 $A=a_i$ のときだけ少し式が変わる。

Hを見て諦め、残り時間はABをlockしてHackを試みていた。結局何も落とせなかったのだが、システスでRoomのAが二つ落ちていた。 $n=2$ で壊れるコードと配列外参照。後者はともかく前者はちゃんと見つけられるべきだった。

コンテスト終了直前にGの $\min a$ に対する式が間違っているように見えて冷や汗を垂らしたが、上に書いたように答えが $0$ にならない条件がかなり厳しいので、結果的には合っていた。

システス前6位でpredictorがすごい値を出しており、心臓に悪い。ジャッジが走っている間は他のことに手を付ける余裕もなく、YouTubeを眺めたりしてただ時が過ぎるのを待っていた。結果は全問通って7完、順位が一つ上がって5位、2954→3111(+157)。レートの更新を待ってツイートした。

Codeforces Round #819
ooooooo- 5th
2954 -> 3111 (+157) highest

Legendary Grandmasterになりました pic.twitter.com/BFs2qGG52s
— こたつがめ (@kotatsugame_t) 2022年9月6日

2998を踏んでからほぼ一年となる。感慨深いタイミングだ。

4完15位で2952→2998(+46)。
週記（2021/09/27-2021/10/03） - kotatsugameの日記

しばらくリプライの返信をしつつ噛みしめていた。午前4時半に布団に倒れ込み、少しハーメルンを読んだところで寝落ちした。午前5時だった。

09/07(水)

午前8時半起床。昨日のCFで問題の剽窃が発覚し、Unratedになっていた。

Round #819 Unrated due to Problem Theft - Codeforces

unratedになっていました。今後おめでとうリプを送らないでください（単に無視します）
— こたつがめ (@kotatsugame_t) 2022年9月6日

良いタイミングだったんだけどな、とか、サークルSlackやインターン先Slackで報告したのを取り消しておかないとな、とか考えていたはず。以下に引用したツイートで述べているように、自分ではそれほど気にしているつもりもなかったが、しかしこの日は一日なんだか調子が悪かった。

悟り開いてるからなんかあんまり気にしてないな。そもそも+157って現実感ないじゃん。現実ではなかったというだけの話
— こたつがめ (@kotatsugame_t) 2022年9月7日

剽窃があったのはF問題。両隣のEとGに比べると実装が面倒で面白くないと感じる。わざわざこの問題を選んで引っ張ってきたというのは意味不明。犯人はWriter三人のうちただ一人だけ紫だった奴で、この一問しか担当していないようだ。橙二人が用意したコンテストに質の悪い一問を追加してUnratedにするのって本当に余計なことしかしていない。確か#810で剽窃した奴も紫だったな。そもそもその程度のレートで問題を提案できるシステム自体に納得いっていない。5桁に易々届く参加者数には見合っていないだろう。

しばらくハーメルンを読んで午前11時半ごろまた寝落ちした。午後10時半起床。ずっと布団でハーメルンを読んでいて、3作読了。

syosetu.org

「真顔のシングル厨がアローラ入りするお話」。原作のアローラ地方の設定が重くてびっくりした。主人公の手持ちポケモンがどれも珍しく強力で、それらが注目を集めたりするシーンは良かった。ただヒロイン二人がどちらもヤンデレなのが好きではない。そもそもヤンデレを受け付けないから。

syosetu.org

ゲームで使っていたパーティーがたまたま手に入るところから始まる。この導入時点ではポケモンたちが主人公に対してどういうスタンスなのか、同じ主人だと認識しているのかなどわからず不穏だったが、以降は面白い。パーティーに振り回されまいとちゃんと努力してはいるものの、結局勝敗についてはポケモンが強いというのが大きいし、言動も人を煽るようなものなのでSNSが炎上気味ということで刺激的だった。

syosetu.org

多分途中まで読んだ記憶がある。少なくとも最初の2話3話には見覚えがあった。最近読んでいるポケモン二次創作とは毛色が違い、バトルシーンはあまりなくほのぼのと進む。たまにはこういうのも良い。

しばらく日記を書き、朝方になってからTCO Finalsのための提出物を作り始めた。今日は自己紹介動画の撮影。わざわざこのためにスマホアームを買ったり床屋に行ったりしたのがもう2週間も前のこと。ちゃんと原稿も用意した上で、面倒すぎて放置してしまっていた。撮影の前に英語の発音やアクセントの修正を試みたもののよくわからなかったので、諦めて日本語英語で押し通すことに。

1時間程度かけて何度か撮り直しを行い、ついに完成。ちゃんと音が入るよう大きな声で話したり、頑張って口角を上げようとしてみたり、いろいろ考えることがあってそこそこ大変だった。原稿は動画時間のことを何も考えずに作ったので、実際に撮ってから制限の15秒に見事に収まっていることに気づきびっくりした。

午前8時に布団に入った。明日のセミナーが午後1時からなので、移動時間も考えて睡眠時間4時間ちょっとの予定。ここでなぜかハーメルンを開いてしまい、気づいた時には午前10時になっていたので、今日は寝ずに大学に向かうことにした。幸い起きたのが午後10時半だったから耐えられるだろうとの見込み。

正午くらいに布団から出て準備を始めた。外は雨が降っており、川内の生協に寄るのが面倒だったので、とっとと山に登ってしまって山の上の生協で昼食を調達したい。そこは今12時45分までしか開いていないので、いつもより早めに家を出る必要があった。何とか間に合って無事総菜パンなどを購入。教室で食べた。

午後1時からセミナー。まず最初の2時間は同級生の発表だった。前回のことを比較的覚えていたので、今日はかなり集中して聞けたと思う。変数や関数の型を丁寧に確認することで添え字でもあまり混乱しない、が、その代わり本当に丁寧に見ないと厳しい。今は $D_{i+1}=(D_i\rightarrow D_i)$ と定められた型の話が続いている。 $D_{i+2}=(D_{i+1}\rightarrow D_{i+1})=(D_{i+1}\rightarrow(D_i\rightarrow D_i))$ くらいまで展開されると勘違いしやすく、2重になったラムダ式の型で今日も引っかかってしまった。

続いて博士課程の方のセミナー。もう何度か同じ内容の説明を受けているが、今日はぐんと理解が進んだと感じる。話されていることに対する知識がついたので英語もより聞き取れるし、何より対面＋黒板発表というのがいい。板書の最中に疑問が生じたらすぐさま質問できて、そのとき英語だけでなく身振り手振りでコミュニケーションが取れる。これまではスライドとオンラインが多かった。

午後6時帰宅。疲れ果てているがしばらくコードゴルフをして、午後9時くらいに仮眠に入った。ここで日記の日付も変えておこう。

09/08(木)

午後11時半起床。すぐECR135に出た。

Dashboard - Educational Codeforces Round 135 (Rated for Div. 2) - Codeforces

Aの題意が把握できず少し迷走した。最大値を取るインデックスを出力すればよい。

Bは最後の操作で $x\lt p_n\le n$ のもと $x+p_n$ を最大化するのが最適。これは $x=n-1$ と $p_n=n$ で達成できる。さらに $p_{n-1}=n-1$ とすると、 $p_{n-2}$ までで $x=0$ とするだけで条件を満たせる。残りは $n-2,n-1,\dots,1$ と並べればよいと思った。しかしサンプルでWA。よく見ると $x\ne 0$ と $x=0$ が交互に現れるため、 $n$ が奇数の時は少し変える必要がある。単に先頭に $1$ を持ってくればよい。

Cは $a$ と $b$ をそれぞれpriority_queueに入れ、大きいものから比較していく。ダメだったら $f$ を適用して戻す。 $f$ は値を急激に小さくするので十分高速、くらいの考察はしたが、 $f$ を2回適用すると $1$ になるというところまでは考えなかった。Dは区間dp。Aliceの操作とBobの操作を一組にして遷移を計算した。かなり面倒。prependではなくappendだと思ってしまい1WA。

Eは難しい。最初にすべて赤のほうに揃えておき、いくつ黒にするかを考えることにする。 $Y$ 個だったなら $b_i-a_i$ の大きいほうから $Y$ 個選んで赤から黒に切り替えるのが最適。この $Y$ をうまく全探索する問題だと思って、 $x_j\mid(n-Y)$ や $y_j\mid Y$ から考えていたが、結局別のところから解いた。

$x\cdot x_j+y\cdot y_j=n$ の解となる整数 $x,y$ を拡張ユークリッドの互除法によって一つ求める。なければ $-1$ 。求めた解を $(x_0,y_0)$ とすれば、すべての解は $g=\gcd(x_j,y_j)$ として $(x_0+ky_j/g,y_0-kx_j/g)$ と書ける。今、 $Y$ の変化に対する答えの値の変化は上に凸であるため、 $Y=y\cdot y_j$ としては頂点に近い位置を探索すれば十分。 $x_jy_j/g$ ずつしか変化しないのに注意して、定数時間で頂点の左右の点を取得することができる。

Fが全く分からなかったのでGに進んだ。 $m$ が小さいので $O(2^m)$ くらいかける方向で考えてみる。最初からあるランタンのpowerの決め方であって、地点の特定の部分集合のみを照らせるようなものが数え上げられると嬉しいだろうか。結局答えを求めるときにもう一度 $O(2^m)$ かける必要がありそうに見えるが、あらかじめゼータ変換か何かしておけば $O(m)$ にできる。新しいランタンのpowerを適当に決めた時、それによって照らせる地点の集合が $O(m)$ 通りしか存在せず、それぞれに対応する場合の数がこの前計算で求まっているから。

あとは最初の決め方の計算。条件を緩めて数え上げた後、包除原理でピッタリの値を求めることにする。「この地点は絶対に照らさない」という集合を決め打って数え上げることができた。照らさないと決めた地点であって隣接するものを取ると、その間にある各ランタンのpowerの上限が決まる。よってそれらを掛け合わせればよい。地点のペアすべてについてその間のランタンの分だけあらかじめ計算しておくと、この部分は $O(m2^m)$ で計算できる。包除原理についてもメビウス変換で書けた。ゼータ変換かもしれないが、とにかくその類の計算が適用できることだけが重要。

Fに戻った。結局最小重み二部マッチングになりそう。マッチング先の頂点は必要になったら生成することにすればよい。しかし頑張って実装したものの合わず、コンテスト終了。方針としては合っているようだったので、マッチングをずらすときマッチ先の頂点の値がずらす前より増える一方だと思い込んだのが間違っていたのだろう。結果はF以外の6完で9位。

DはBobが絶対に勝てないらしい。正直これも証明がつけられていないが、さらに解説のコメント欄ではDrawとなる文字列が $A+B+{\rm rev}(A)$ 、ただし $B$ は先頭から2文字ずつ同じ文字が現れる、という形に限ることまで議論されていた。

Eは $x_j$ と $y_j$ のうち大きいほうで探索することで通せるらしい。このときクエリごとに $O(n/\max(x_j,y_j))$ かかる。 $\max(x_j,y_j)=k$ となるペアが $c_k$ 個あるとすれば、重複を取り除いて $c_k\le 2k-1$ が言えて、さらに $\sum_k c_k=m$ でもある。この元で $k$ が小さいものをたくさん集めると $\sum_k n/k\times c_k$ が最大化され、最悪ケースになる。そのとき $k\le\sqrt m$ では $c_k=2k-1$ 、以降は $c_k=0$ となるから、計算量は $O\left(\sum_k n/k\times c_k\right)=O\left(\sum_{k=1}^{\sqrt m}n/k\times k\right)=O(n\sqrt m)$ で確かに間に合っている。

TCO Finalsに向けた提出物は、最後にアンケートが残っている。09/09締め切り。とりあえず質問をザッと確認してみて、回答必須のものが思ったより少ないことに安堵した。しかし最後に自分の写真を添付する必要があってびっくり。明日ホスフィンと旅行に行く予定なので、旅先で撮ってくることにしよう。

旅行のために今日は早く寝なければならないと思い、午前3時頃には布団に入った。しかしそこから読み始めたハーメルンが章のクライマックスで非常に面白く、結局就寝は午前5時過ぎになった。

09/09(金)

午前7時、執念の起床。軽く持ち物を用意して出発。

今日は青春18切符で平泉に行く。仙台で暮らして5年目になるが、いつも新幹線と地下鉄にしか乗らないので、初めて仙台駅の在来線ホームに立ち入り感動した。途中の駅で宮沢賢治作品モチーフのステンドしおり2種類を購入しつつ、午前10時半ごろに平泉駅に到着した。

すぐ横のレンタサイクルで電動自転車を借り、今日は一日これで動き回る。初めて電動自転車に乗ったがかなり快適だった。金鶏山周辺の道は坂ばかりだったし、達谷窟毘沙門堂はそれなりに遠かったので、たった100円をケチって普通の自転車を選ぶようなことはしなくて大正解。

まず中尊寺に向かった。参道が急でかなり恐怖感があった。ここでは本堂や金色堂の他にもありとあらゆるお堂を練り歩き、昼過ぎまで過ごした。本堂本尊の写真を貼っておこう。金色堂をはじめ結構な数のお堂は撮影禁止だったが、これは特に何も書かれていなかった。調べた感じ、最近作られた仏像だからという理由がありそう。

あとは、お堂にペタペタ貼られているお札が千社札と呼ばれることを知り、それにも注目していた。これまたほとんどのお堂では貼り付け禁止になっている中、特に書かれていないお堂もあって、そこの柱にはお札だけでなく筆やペンによるサインもたくさんあった。平成終わりごろの日付のものがいくつもあったが、令和に入ってからのものは見つけられなかった。

金色堂覆堂の前でホスフィンに写真を撮ってもらった。アングルも含め昔よく読んでいた本に描かれていた景色で、非常に既視感がある。ただ絵面がパッとしない。そもそも中尊寺は撮影可能な場所も少ないし、写真映えを求めるスポットではなかった。

日本にのこるなぞのミイラ | 株式会社理論社 | おとながこどもにかえる本、こどもがおとなにそだつ本

下山して駐車場の周りの食事処で昼食。次は毛越寺に行く予定で、途中に金鶏山があるので寄ってみた。しかしここはシンボルとして有名なだけで、登っても何も面白いものはない。麓に廃寺があったらしいが見逃し、急な山道を必死に歩いて山頂に着いてみたら、ただ塚があるだけで周りは鬱蒼としており見通しもよくない。意気消沈して下りた。足を滑らせたらそのまま転がっていきそうなほどの勾配で、登るより下りるほうが格段に怖かった。

毛越寺。「夏草や　兵どもが　夢の跡」という有名な句の、新渡戸稲造による英訳の碑があった。「The summer grass / 'Tis all that's left / Of ancient warriors' dreams.」。'Tisという単語を知らず、調べてIt isの省略形であることを知った。庭園の池をぐるっと一回りして、甘味処でかき氷を食べて出た。

次は20分ちょっと自転車を漕ぎ、達谷窟毘沙門堂へ。ここはフォトジェニックでよかったので、またホスフィンに写真を撮ってもらった。自分でも撮ったので一枚貼っておこう。サムネ用。全体を収めるためには横向きで撮りたくなるが、これだと画面の上まで崖で覆われて窮屈さを強く感じる。そこで縦向きで撮ると、せり出した崖の上の部分まで見えて、圧迫感が自然の雄大さにすり替わってくれる、気がする。

本当は温泉に入る予定だったが、レンタサイクルの閉店時間に追われながらは嬉しくないので、いっそ帰ってから銭湯に行こうということになった。電車に乗って仙台へ。乗り換えで立ち寄った一ノ関駅にピカチュウのポケモントレインの顔出し看板があって、そこでもホスフィンに写真を撮ってもらった。以上3種類のどれかを選んでアンケートに添付しよう。

今日の行き帰りの電車では昨日のハーメルンを続けて読んでいた。1作読了。「自分はかつて主人公だった」。

syosetu.org

主人公自身が強いし、手持ちポケモンが伝説ばっかりで最高。かつての力やパーティーを取り戻すという展開で、序盤の少し弱くなった主人公描写に耐えたぶんクライマックスは非常に興奮した。ストーリーとしても面白い。人間的成長という一見ふわふわした話が主人公の実力とダイレクトに連動している。だから昨日睡眠時間を削ってでも一気読みしたし、今日も電車の中で寝るつもりがずっと読んでしまったのだ。

午後6時半ごろ仙台駅に到着。たいぺーとも合流して地下鉄に乗り、サンピアの湯というスーパー銭湯に向かった。久しぶりの大きな風呂で非常に良い。サウナに入った後水風呂に浸かったら、今日一日ずっとあった眠気が一瞬だけ完全に吹き飛んで非常に爽快だった。その分風呂から出て併設のレストランで食事しているときには一気に眠気が来て大変だった。

その後寝転べる場所に移動して2時間ほど漫画を読んでいた。虚構推理の1巻と、転スラの10巻から15巻あたり。前者は小説版を積んでおり、序盤を漫画で確認することで読む意欲を高めようとした。無事高まったものの本当に小説版を読むかは不明。後者については、神之怒のシーンが大好きなので探していた。無事見つかってよかった。

午後11時過ぎに銭湯を出て、日付が変わったあたりで帰宅した。また少し汗をかいてしまったのでシャワーを浴び、布団へ。旅行で撮ってきた写真を一度にツイートした。

今日
・中尊寺本堂
・中尊寺本堂内部
・金色堂覆堂
・達谷窟毘沙門堂 pic.twitter.com/63EU3szYZI
— こたつがめ (@kotatsugame_t) 2022年9月9日

今日2
・平泉の郵便ポスト
・中尊寺本堂の千社札
・達谷窟毘沙門堂と崖の境界
・達谷窟の鐘楼の床に開けられた穴 pic.twitter.com/bIan5mbdhv
— こたつがめ (@kotatsugame_t) 2022年9月9日

鐘楼の床に穴を開けるのは何故だろうか。音の響きをよくするためという理由が思いつくが、調べてもヒットせずよくわからないままである。

午前1時就寝。

09/10(土)

午前7時半起床。ABC264の賞金が届いていた。

kotatsugame 様

先日はfreee プログラミングコンテスト2022（AtCoder Beginner Contest 264）にご参加いただきありがとうございました。

そして見事総合順位3位と学生順位2位の受賞おめでとうございます！賞金としてAmazonギフト券を進呈いたします。

￥45,000
Amazonギフト券
— こたつがめ (@kotatsugame_t) 2022年9月9日

少しハーメルンを読んで午前9時過ぎに布団を脱出。睡眠時間が足りていないので、夕方また仮眠するつもりである。

しばらくコードゴルフした後、昼頃にTCO Finalsのアンケートを書いた。写真は一ノ関駅で撮ったものを使った。提出時刻はアメリカのタイムゾーンではギリギリ09/09なので、締め切りに間に合ったと言えるだろう。このためにわざわざ朝から起きていたのだ。

- 日本のcoolなところを教えてください。
- 日本人は現金支払いのとき、常に手持ちの硬貨の枚数を最小化しようとします。これは典型的な競プロの問題です。
— こたつがめ (@kotatsugame_t) 2022年9月10日

布団に戻って仮眠の体勢に。しかしダラダラハーメルンを読んでしまって、結局寝入ったのは午後4時前だった。次に午後8時起床。あと30分くらい眠れるかなと思ったのにTLを見ていたら寝損ねた。

最初から午後8時半に目覚ましを設定するのは怖いのに、午後8時からもう30分寝るのが怖くないのは一体なぜだろうか。恐らく後者は、その時の眠気が強すぎてとにかく寝たいという気持ちでいっぱいなのだろう。実際このせいで寝過ごしたことが何度かある。

食事して午後9時からABC268に出た。

UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder

AはRaku。Bはsed。Cは少し難しい。テーブルが $k/N$ 周回っているとき喜ぶのは $(p_i-i-k)\bmod N$ が $-1,0,+1$ であるような人 $i$ だから、 $(p_i-i)\bmod N$ をカウントしておくことで $k$ ごとに人数が定数時間で求まる。

Dはdfsで全探索。計算量を考えずに提出したら、そもそも $N$ と $M$ を取り違えていてTLEやREを出してしまい、もしかして間に合わないのかと震え上がった。バグに気づいて提出しなおし、WA。 $|X|\ge 3$ をチェックし忘れていた。この条件いる？

Eは気合いで差分更新。Fは各 $S$ についてそれだけ考えた時のスコア、数字の和、Xの個数の三つを計算すると、これらの組み合わせで全体のスコアが計算できる。式を見ることで、二つの $S$ の結合順序を入れ替えたときにスコアが上がる条件が求まる。ちゃんと順序になっているので、それを比較関数にして $S$ をソートすればよい。

Gは各 $S$ に対する答えが、 $i=1\dots N$ について $S_i$ が辞書順で $S$ 以下となる確率を足し合わせたものになる。 $S_i$ と $S$ のどちらかがもう一方の接頭辞となる場合は関係が確定するので、それ以外を考えたい。これは先頭から見て初めて食い違う位置の文字の順序における大小関係から定まって、冷静になると大小どちらも $26!/2$ 通りずつである。なので最初に弾いた接頭辞の部分だけ真面目に計算すれば十分で、Trie木で求まる。

Exはよくわからない。そのまま残してはいけない区間を列挙できれば、貪欲法で答えが求まる。その区間自体も $S$ に $T$ たちを連結した文字列のSuffix ArrayとLCP Arrayを使うことで計算できそうだが、自分が考えた方法では各 $T$ に対して $S$ の位置を見ていたので、 $S$ も $T$ も全部同じ文字というような最悪ケースでは間に合わなさそうだった。そこでGのコードを流用して、別の $T$ が接頭辞となっているものを無視することにした。これだととりあえず先ほどのケースはうまくいくし、考えてもそうひどいケースが見つからない。信じて提出したら1100msくらいで通った。

全完18位。AのFAだった。Dの計算時間は、そもそも $M+1$ 個候補を生成すれば必ず見つかるし、全通り生成しても十分高速らしい。Gは $P$ としてa-z、z-aの二通りのみを考え、その平均を取ったものが答えになるようだ。言われてみればそう。Exは $S$ の位置に対して $T$ 、特に $|T|$ が最短のものを探すと全体で線形時間になるため、接頭辞云々で枝刈りする必要はなかった。

コードゴルフについて。これは以降二つのコンテストの前後でやっていた結果も含む。AはFAだったRakuのコードがそのまま最短。BはsedよりVimのほうが4Bも短くてひっくり返ってしまった。CはPerl。Fは数字の和とXの個数を複素数の形で持つと偏角ソートしたものが求める順序になって、かなり縮んでくれた。Gは上で触れた、二通りの $P$ に対して計算する方法。他は手付かず。

午前0時からSRM837。

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

最初15分くらいエラーで提出できず、Unratedになった。普段と違う時間にコンテストを開催してエラーが起こるというのは昔AtCoderでもあった記憶がある。その時はジャッジサーバが起動しておらず、序盤の提出を捌けていなかったはず。同じ原因かはともかく、これは同情できる。ただしUnratedの理由が「As the disruption is taking longer than we hoped」だったのは信じられない。もしかして数分で復旧したら続行するつもりだったのか？

そういうことがありながらもちゃんと全問解いておいた。Easyは $H$ の昇順にソートして使う。 $W_i\times H_i\gt 1$ という制約が何なのか不安になったが、通常のcubeと同じサイズのブロックがあると、それを他のブロックの上に置けないかどうかはどう決めたってややこしいので、避けた形だろうか。

Medはdp。バケットごとに使うバックアップの個数を決め打つと、できるだけ偏らないように分割するべきなので、かかるコストが閉じた式で計算できる。状態数 $O(HT)$ 、遷移が $O(T)$ なので十分間に合う。バックアップは使い切るべきだと思っていたが、念のため何個使うか全探索して答えとした。実はバックアップを一切使わないケースというのもあるらしく、それで落ちていた人がいた。

Hardは気合い。文字列のインデックスと、そこまでに使ったupperBoundsの集合を持ってdpする。遷移は特に工夫せず丁寧にチェックするだけでよい。問題はgoodとbadの区別。ある分割がgoodであるとは、分割後に隣り合う二つの文字列 $a,b$ が $a+b\ge b+a$ を満たすことである。なので、dpするとともにgoodに対してそれを達成する $a$ を列挙しておき、新しく $b$ を足したときgoodのままかbadになるかチェックするという方法を考えた。特に上の比較はちゃんと順序になっているので、 $a$ としては最小と最大しか保存しなくてよい。

チャレンジフェーズは何もせず。システスは無事全部通って全完5位となった。

午前2時からMHC R1が始まったので出た。24時間で終了するのでここに感想を書く。

Meta Hacker Cup - 2022 - Round 1

A1は簡単、どれくらいrotateしなければならないか決まるので $K=0$ に気を付けつつチェック……と思ったらvalidationで落ちた。冷静になるといろいろコーナーケースがある。まず $K=0$ の場合rotateできないのはサンプルにもある。次に $K=1$ のとき、これは逆に必ずrotateしなければならないので、最初から $A=B$ だった場合はダメ。

以降 $K\ge 2$ として、rotateできる範囲が $[K,(N-1)K]$ なので、 $(N-1)K-K+1\ge N$ ならどんな状態も達成できる。式変形すると $N\ge\frac{2K-1}{K-1}=2+\frac 1{K-1}\gt 2$ 、つまり $N\ge 3$ ならOKだが $N=2$ はコーナーとなっている。実際このとき、rotateする幅と $K$ の偶奇が等しい必要がある。以上を実装して提出。A2は $B+A+A$ に対してZ-algorithmを適用することでrotate幅を全探索できる。

Bはいつもの。縦横分割し適当にソートすれば求まる。B1とB2で同じコードを出した。Cはしばらく考えても糸口がつかめなかったので諦めた。

ハーメルンを1作読了。「東方神殺伝～八雲紫の師～【リメイク】」。

syosetu.org

「俺の家が幻想郷」の作者の別作品。中二臭さがかなり好みだったのでこちらも好きだろうと思って読み始めたが、実際かなり良かった。原作キャラより圧倒的に強いオリキャラたち、オリジナル能力、二つ名……。一方、せっかく幻想郷にいるのにオリキャラばかり出てきて原作キャラの出番がどんどん減ってしまったので、それはちょっと好みから外れていた。リメイク前はオリキャラたちのインフレがもっと激しかったらしいのでそちらも少し気になる。

朝からは日記を書いていた。午後2時くらいに切り上げて布団に入り、1時間ちょっとラノベを読んでから寝た。

09/11(日)

午後8時半起床。食事して午後9時からARC148に出た。

AtCoder Regular Contest 148 - AtCoder

Aは $M=2$ で多くとも2通りが達成できるので、1通りが達成できるか調べる問題になる。つまり $A_i\bmod M$ がすべて同じ値になればよく、ここから $M\mid(A_i-A_j)$ が出る。よって $M\mid\gcd(A_2-A_1,A_3-A_2,\dots,A_N-A_{N-1})$ で、 $\gcd$ が $\pm 1$ かどうかを調べればよい。 $0$ になりうることを見落として1WA。

Bは $S$ における最初のpの出現位置からスタートする部分文字列をひっくり返すのが最適なので、候補が $O(N)$ 通りになって全探索できる。そもそもpが出現しないならひっくり返さなくてよい。

Cは最初、クエリごとに必要な頂点だけ取り出して圧縮した木を作ることを考えたが、あまりに面倒だったのでもうちょっと考察してみたらスマートに解けた。ある頂点のコインをひっくり返すときは、まずその頂点のボタンを押す必要がある。するとその子以下もすべてひっくり返ってしまうので、特にひっくり返したくない子があった場合はそれらのボタンも押す必要がある。逆にひっくり返したかった子のボタンを押す手間を省いたとも見なせる。

これをまとめると、クエリ $i$ の答えは、まず $v\in S_i$ に対して $v$ と $v$ の子の個数を求めて和を取り、そこから $v\in S_i$ であってその親 $u$ も $u\in S_i$ を満たすような $v$ ごとに $2$ だけ引いたものとなる。

Dは、まず $A$ に同じ値が二つ含まれていた場合、それらを取り除いてよいことがわかる。この操作をした後に $A$ の要素が残るか残らないか見れば答えになると思い、提出。WA。もうちょっと真面目に考える。二人の和がそれぞれ $X,Y$ で、黒板に書かれた数の残りが $x,y$ であるとする。この下でBobが勝つ場合、 $X+x\equiv Y+y\pmod M$ かつ $X+y\equiv Y+x\pmod M$ である。式変形することで $2(x-y)\equiv 0\pmod M$ がわかるため、 $M$ が偶数の時は $M\leftarrow M/2$ として上で述べたことをチェックするのがよいと思った。またWA。

よく考えると、 $2(x-y)\equiv 0\pmod M$ かつ $x-y\not\equiv 0\pmod M$ なる $(x,y)$ は偶数個使わないと和が一致してくれない。よって、最初に同じ値二つを削除するのを繰り返した後、残った個数が4の倍数で、かつ $\bmod{M/2}$ で一致する値のペアを消していくと全部消えるというのが条件だと考えた。出したら通った。

Eは難しかった。 $A$ の要素は最初全部区別しておいて、後から適当に割ることにする。列にどんどん挿入していくことを考える。 $A$ の要素を昇順に見るのも降順に見るのもうまくいかなかったが、 $K/2$ で分割するとうまくいった。

列の両端に $K$ が置かれているとみなして、新たに要素を配置できる隙間を管理しつつ、 $K/2$ 未満の数を昇順に見る。 $a\lt K/2$ を見ている時点で $a$ 未満と $K-a$ 以上の要素がすべて配置済みとなるようにしておく。隙間を一か所選んで $a$ を配置すると、その両隣には残った $K-a$ 未満の要素が配置できないから、単に隙間を一つ減らすという効果になる。 $a$ を配置する前に $K-a$ 以上の要素を使い切るときは、隙間を一か所選んで挿入すると、その両隣は構成から必ず $K-a$ 以上となっているため、新たに隙間が二か所できる。

$a$ を次の数に進めても、挿入できる位置は増えも減りもしない。こうやって隙間の数を簡単に管理できることが重要で、これを満たすために $K/2$ で分割して昇順と降順を分けている。あとは毎回の挿入位置を考えて組み合わせ計算するだけ。ところが2REしてしまった。combinationのライブラリは引数に符号なし整数を取るように作ったので、隙間の数がうっかり負になったとき、バカデカい値を計算しようとしてしまう。

1時間残してFへ。得意そうな見た目をしていたが、結局解けなかった。モンゴメリ乗算にはたどり着いたものの、リダクションの最後、if文による調整の部分が書けない。結果は5完5ペナで13位。ペナルティが多すぎる。Eは冷静になると隙間の数を答えに掛けながらインクリメント・デクリメントするだけでよく、わざわざライブラリを持ち出す必要がなかった。

コードゴルフ。AはRakuが間に合う。ずらして隣接項の差を取るのではなく全部の項から $A_1$ を引くと高速になったし、[gcd]というreduce用メタ演算子の性質が効いて縮んだ。

もともとgcd演算子は正の数を返すようなので、これが $1$ であるか判定するだけでよいと思っていた。$a gcd $b gcd $cという式が[gcd] $a,$b,$cと書けることを利用して全体の $\gcd$ を求め、判定。ところが[gcd] $aと1要素しかない場合、メタ演算子の仕様上$aがそのまま返ってきてしまう。$aがちょうど $-1$ だった場合にはうまく判定できないのだ。全部の項から $A_1$ を引く方法だと必ず2要素以上になるので、正しく正の数が返ってくる。

BはPerl。ひっくり返す部分文字列が先頭のpの後に何文字続いているかを全探索し、正規表現で検出した。最も先頭の出現にマッチするので正しく動く。最初はわざわざpのインデックスを求めてsubstrで切り出していたが、この方法でかなり短くなった。以降は手付かず。

午前2時にMHC R1が終了した。提出したA1A2B1B2は全部通って76位、スコアが十分あるので当然通過。Cは座標の範囲が $[0,a)\times[0,a)$ に制限されていると格子点からなる凸包には $O(a^{2/3})$ 点しか乗らないらしい。言われてみれば昔聞いたことがあるかもしれないが、すっかり忘れていた。それでも $V=35000$ 頂点のdijkstraを解くことになる。これはpriority_queueを使わない方法で $O(V^2)$ が達成できるので、確かに間に合いそう。

朝まで日記を書いていたが、急激に眠くなったので布団に移動。午前7時就寝。