02/14(月)

先週は週記を投稿してから比較的すぐ寝た。午前4時だった。ここ最近かなり良い生活リズムが続いている。

午前9時半起床。二度寝に失敗した。目を覚ますといつも口内に違和感がある（寝ている間の細菌の繁殖か）ため、何をするにしてもとりあえずうがいをしておきたい。しかしうがいのために冷たい水を口に含むとてきめんに眠気が失せてしまうようで、いつも二度寝に失敗しているのにはそういう理由があるのではないかと考えた。

布団から出てしばらく他の人のブログを読み、昼前に学食に向かった。今日は非常に良い天気で、道路も空いていてかなり気持ち良く原付を運転できた。食事して予約していた本を受け取り、帰宅。これで1月の初めに注文した分は全部受け取れたはず。

それからずっと勉強会のための発表スライドを作成していた。昨日の時点でpreprintを一通り読んで、どのような説明の順序にするかも考えておいたので、それに沿って情報を置いていく。とはいえ、当然のことながら元のpreprintの時点でよく考えられた構成になっているので、基本はそれに合わせるような形になった。いくらか点在する情報があったのでそれをまとめようとはしてみたものの、効果のほどはどうか……。一度読んだから情報の位置を動かしてもついていけるだけで、人に説明することを考えるとこれまた元のpreprintの状態が良いのかもしれない。

夕方までかかって何とか完成を見た。急いで進捗報告スライドを生成して、インターン先定例会に臨む。先週金曜日にちょっと進めたことを発表して終了。その後勉強会が始まった。やたら早口になっていたり、同じことを何度も繰り返したりしていた気がするものの、発表後の質問が結構多かったあたりに手ごたえを感じる。やはりみんな興味はあるのだろうが、腰を据えてpreprintを読むまではいかなかったのだろう。自分もこのような機会がなければ全く見もしなかったはずだ。

使用した発表スライドを公開することにした。先週著作権についてあれこれ心配していたものの、悪意があるわけでもなし問題にはならないだろうと楽観的に考えることにした。

勉強会0214.pdf - Google ドライブ

AlphaCodeのpreprintを読んで自分なりにまとめたスライドを公開します。https://t.co/nIEHNpHeOA
— こたつがめ (@kotatsugame_t) 2022年2月14日

勉強会の終了は午後7時だった。AtCoderのコンテストリストを見に行くと、つい昨日行われたJOI本選が過去問として解けるようになっていた。いつ公開されるかとコンテストリストを定期的に見守っていたのだ。

JOI 2021/2022 本選過去問 - AtCoder

Aは簡単で、クエリがソートされているので完全に線形時間で解ける。 $X$ でループを回して、その位置のピースを含む $A$ まで分割し、そうやって直近に分割した $A$ を変数に持っておいて出力する。最初に書いたこの方針がかなり良かったようで、Rubyに書き換えて76B、Perlに書き換えて71Bと予想よりはるかに縮んでくれた。BはTLが1secだし $N\le 3\times 10^5$ だしでlogを落としに来ているのかと考えたが、全然そんなことはなく普通に二分探索が通る。

Cは非常に難しく、小課題7が解けずに解説をチラ見してしまった。本当は解説の途中で止めて考えるつもりだったのに、小課題6まで解説と全く同じことをやっていたのでずるずる最後まで読み進めてしまったというわけ。解説はdpテーブルの必要な位置が少ないことを利用して解いているが、自分としては $Goal$ 人集めた瞬間に残りを前計算から求める方法が書きやすかった。DはTLでダブリングというキーワードを見てしまったので一瞬。E問題は解いていない。

Cの特に小課題7に2時間以上かかってしまった。急いでシャワーを浴び、午後11時半からCF #771 div.2に出た。服を着て部屋に駆け込むとコンテストが始まっていて絶望したが、実際は1分程度の遅刻だった。

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

Aは $p_i\ne i$ となっている最小の $i$ と $p_j=i$ なる $j$ を見つけて $[i,j]$ を反転するのが良い。Bは転倒数を考えると大小関係が逆転しているすべての要素が交換できる必要がある。先頭要素から順に挿入ソートしていくことを考えて、ソート済みの列の後ろから偶奇が一致する部分とその一つ先を管理することで何とか解いた。TLで偶奇それぞれが昇順ならよいということを知り、愕然。確かに……。Cは似たような問題を最近見た覚えがあったので、それを思い出しつつ解いた。2次元平面に $(i,p_i)$ をプロットしたとき、連結成分それぞれをピッタリ含むような長方形が左下から右上に連なるような形になる。左からの累積maxが右からの累積min未満であるような境界を数えればよい。

ERASEは先頭から累積minの更新点を列挙して、隣接するどの2つの更新点にも、その2つとそれぞれペアを組めるほかの1点が存在すればよい。と面倒なことを言っているが、つまり2次元平面にプロットしたときに左上と右下に完全に分割できなければよいというだけの話。
週記（2022/01/17-2022/01/23） - kotatsugameの日記

Dは操作を逆順に見るやつ。10⁶個の入出力は気が狂っている。Eは区間をsetで、色ごとに足された値を配列で管理する。色を塗り変えるときは、これまでその色自体に足されていた値を個別に足して、新しく塗られた色にもともと足されていた値を引くことになるが、この操作は区間に対して一律で行えばよいので遅延セグメント木で書ける。10⁶にlogがついてTL 4secと意味不明な制約。Fは解けず。Eまでシステスが通って16位。

コードゴルフの興味深い更新があった。 $\bmod{10^9+7}$ した後の数を3で割る必要があって、巧妙な式変形で最短を取られたコードが、さらに縮んでいた。 $\bmod{3\times(10^9+7)}$ で余りを取った後直接3で割ってもよいらしい。3の倍数であることはわかっているのだから、確かにこれでうまくいくようだ。感服した。

atcoder.jp

午前4時就寝。

02/15(火)

午後4時起床。今日はうがいしたにも関わらず二度寝に成功した。よくわからないが睡眠負債がたまっていたのだろう。午後5時から1on1で、念のためそれに合わせて目覚ましをセットしておいて助かった。

しばらく布団でゴロゴロした後起き上がり、食事して1on1へ。先週金曜日からの進捗はほぼないので、いくらかの取り決めをしても30分程度で終了した。実装のアイディアはいくつも出てくるものの、どれも一長一短に感じられる。実際はやってみないとわからないのに、やる前から微妙に悲観的になって手が動かない状態にある。困った。

久しぶりにラノベを1冊読んだ。「『ずっと友達でいてね』と言っていた女友達が友達じゃなくなるまで」2巻。かなり良かった。1巻のラストがついに高校生活が始まるところだったので、どんな風になるのか期待していた。新キャラ2人以外には全く焦点が当たっていなかったが、その新キャラのうち男のほうがかなり好みの設定だった。淡々としていて何事にも動じない感じが好ましい。まあそれは本題ではない。主人公とヒロインの進展については終始外堀を埋めている感じで、次の巻でついにゴールインしそうな予感がする。あとがきでも3巻が節目の巻になると予告されているので、ぜひ続刊してほしい。

別のラノベを開いて少し読み進めた後、食事。今日は久しぶりにパスタを茹でた。調べたところ、昨年5月末以来だったらしい。パスタソースは軒並み賞味期限が切れてしまっていたものの、関係なくおいしい。食べ終えて午後10時からTROC #26に出た。

https://tlx.toki.id/contests/troc-26/

Aはよい。相変わらず提出が面倒で微妙に時間を食う。Bは一昨日のARC135-Dを解いていれば瞬殺で、市松模様に正負を割り当てて和を0にできればよい。Bにしては難しく感じる。Cは数の小さいほうから $\left\lfloor\frac{\sum A_i}2\right\rfloor$ 個を偶数番目に置くことを考えて、丁寧に条件を確認する。細かいところを詰めるのが嫌すぎてしばらく固まっていた。書き始めると意外と単純。Dは花と最短の蜂の距離を列挙して、適当に日付を更新しつつ取れるはちみつの必要なエネルギーを優先度付きキューで管理する。

Eは謎。各ノードで $1\le k\le 自分の子の数$ の場合の値を計算する。 $k$ をインクリメントしてから子でループを回し、その子がさらに $k$ 個以上の子を持っているなら計算結果を取得し、そうでないなら $A$ の値を取得して、その値と直前の値を入れ替え、最後に上位 $k$ 個の和を求める。まず入れ替えてから上位 $k$ 個の和を求める部分は、上位と下位をsetで管理すると可能になる。setの要素を下位から上位へ適宜ずらしていく感じだ。次に子のループを回す部分だが、一度 $k$ 個以上の子を持たないと分かった瞬間次のループからその子を見ないようにする。これも子をsetで管理してeraseしていくことで行う。計算量解析は貰う側ではなく渡す側で考えればよくて、各ノードは $自分の子の数+1$ 回しか計算結果を取得されないので、 $k$ のインクリメントに伴う子のループが全体で $O(N)$ となる。setを弄る部分も大体そのくらいの挿入・削除回数になる。Fはちょっと面白い。各品物に対して $A_{i,*}$ をソートし、差分を取ることで「 $mask$ に含まれる店が使えない場合はコストがさらに〇増加する」という情報が $M$ 個得られる。差分を取ったことにより、各 $mask$ に対し部分集合全体の和を取ることでコストがわかる。これはゼータ変換である。

Gはしばらく $K$ グループまでではなく1グループ $K$ 人までという問題に誤読していた。そちらはどこまでグループ分けしたかのdpになって、遷移が $dp_i=\min_{i-K\le j\lt i}\left(dp_j+(N-j)\max_{j\le k\lt i}T_k\right)$ と書ける。このうち $\max$ の部分を $x$ と置いて直線だとみなせば、傾き $N-j$ は単調減少だし値を取得する $\max$ は単調増加するのでdequeを使うCHTが使える。このdequeはセグ木に乗せることができる。取得クエリのたびに適当に先頭からpopしていき、更新は変更が一切行われずただ列を右に伸ばす感じなので、対応するノードのdequeにpushすればよい。 $dp_i$ の計算に戻ると、 $\max$ の部分が同じになる $j$ の範囲を管理し、その範囲が $[i-K,i)$ に完全に含まれるものは前計算したものを区間minで取得、中途半端に重なるもの高々1つ（これは二分探索で求める）についてはセグ木で計算することになる。今まで書いたことは全部誤読した問題の解法であって、正しい問題が分かってからは手も足も出ず。

6完最速で5位、レートは2680→2732(+52)で最高値を更新。ランキングで7位に来た。

今月分のTCB44が始まっていたので、参加した。ちょうど日曜日に終了するので、ここに詳細を書ける。今月のテーマはデータ処理らしく、答えを $Q$ 回求めたり $N$ 回求めたりする問題ばかりだった。

https://techful-programming.com/user/event/2531

2問目は微妙に面倒。5問目は数列 $A\%M$ をソートしておき、最小値と $M-X\%M$ 以上の最小値、高々2種類を調べればよい。6問目はBITを2本作って、片方はまだ移動していない文字列を、もう片方は各文字列が移動した最後のクエリを管理する。8問目は小さいほうから $x$ 個目の値とそこまでの和が取得できればよく、実はこれはbinary trieで実装できる。二分木の各ノードにそれ以下のノードの和を持たせておく感じだ。このことに思い至るまで結構時間を使ったのと、考察ミスで小さいほうから $x$ 個目の値ではなく最小値を使ってしまったため、1ペナと30分強を費やすことになった。-26pt。そういえば以前binary trieを必要なところだけ作るセグ木と言ったことがあるが、より正確にはクエリの範囲が左端か右端を含んでいれば対応できるセグ木となるようだ。

9問目は、まず変数の正負を見るため2部グラフの判定をインクリメンタルに行う必要がある。これはUFを使う、頂点を倍加する手法で行える。次に $\log_2$ を取った値を管理することを考えて、こちらはかなり久しぶりに重み付きUFを引っ張り出してきた。基本的に自由度は連結成分数になるが、正負のチェックやループにおける $\log_2$ の値の不一致などで壊れてしまった連結成分は全部0を代入することになるので、そのような連結成分にマークをつけておいて丁寧に処理する必要があった。手間取って微妙に時間オーバーし、-2pt。10問目は最終形態の文字列にmanacherを使い、どの位置の文字を追加した瞬間に回文が増えるかを求めればよい。文字それぞれに対し、それを中心とする回文が増えるタイミングで追加される文字は最終形態の文字列における区間になるので、imos法で足せる。

日記を書いてシャワーを浴びた。すぐ寝ようとしたものの頭髪が乾いていないのでしばらく待つことにしてスマホを触っていると、Mojangからメールが来ていたのに気づいた。Minecraftを作った会社である。Minecraftのためのアカウントを、Mojang独自のものからMicrosoftアカウントに移行しろということらしい。もう数年触っていないので今更どうなろうとあまり気にしないとはいえ、気づいたからにはやっておかないと何となくすわりが悪い。ということで少し作業をして、そのあと流れでコードゴルフを始めてしまった。1時間以上経ってようやく一段落ついたので切り上げ、就寝。午前8時前だった。

02/16(水)

午後2時前に起床。どうにも眠れなさそうだったので素直に起きた。

購買に行く前に昨日のコードゴルフの続きで布団で思いついた改善を適用しようと思い、パソコンの前に座った……ところ思わず熱中し、購買の閉店に間に合わない時間になってしまった。仕方がないのでそのまま続け、仕上げに実行時間のブレを利用して微妙な解法を通したところで終了。

一念岩をも通す pic.twitter.com/xjDmWWf8Rs
— こたつがめ (@kotatsugame_t) 2022年2月16日

街に出る。ところどころ雪が残っているのが見えるが、まあ問題はないだろうということで自転車に乗って、仙台駅の反対側まで向かった。

まず駅前のヨドバシカメラでUSBケーブルを買う。先日賞品として受け取ったHHKBについて、Bluetooth接続でしばらく使ってみたものの、1台目のHHKBとまったく同じ理由でストレスを感じる。特にサブのマシンに接続しているということもあり、しばらく操作しないとキーボードの電源が切れるのは致命的だった。ケーブル長は机から下のPCまで伸ばすことを考えて1.5mを選択。巻き尺がないので必要な長さが正確に測れず、以前買った0.5mのケーブルをもとに目測で決めた値。大変悩んで、しばらく売り場で両手を広げて長さを感じてみたりと不審な行動をしていた。

使っていなかったBluetoothドングルを差して接続してみた。
週記（2022/02/07-2022/02/13） - kotatsugameの日記

USBケーブルを購入してHHKBを有線でつなぐことにした。bluetoothだとかなり不安定でよく変な挙動をするし、数分操作しないだけで電源が落ち、復帰のために数秒電源ボタンを押さなければならないのもつらい。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

ついでに、以前から音声入力の際にノイズが混じるのが気になっていたので、新しいマイクを購入した。部屋では換気扇の音が結構するのでそれが原因だと思ったが、店員さんに聞いてみるとPC内の電気信号がノイズになっている可能性もあると聞いて驚いた。環境音については指向性のマイクを、電気信号についてはUSB接続のマイクをそれぞれ使うことで対処できるらしく、両方兼ね備えたものをおススメされたのでそれを購入。2000円ちょっとだった。これまで使っていたマイクの4倍の値段がするので、まあ悪くなることはないだろう。

食事してゲーセン。ヨドバシカメラの近くのゲーセンはチュウニズムの筐体にスマホアームが用意されていた、たまに手元を撮影しに来ていた。今日もそのつもりで向かったのだが、新筐体になったのをきっかけにだろうか、アームがなくなってしまっていた。残念。こうなるとただ遠くて台数も少ないゲーセンに来る価値はなくなる。移動して、いつものセガ仙台でプレイした。

今日は午後5時半から閉店までみっちり6時間弱プレイして腰をバキバキにした。進捗としては理論値が+10譜面と、1日に出した数では過去最高に。かなり調子が良かった。数回プレイしてダメだったらさっさと別の譜面に移ったのも良かったか。13+初の理論値も決めることができたとはいえ、譜面のレベルは理論値難易度を元に設定されているわけではないので、かなり簡単で拍子抜けだった。いや拍子が抜けていないから理論値なのだが。

ウサテイ理論値
13+初理論値 pic.twitter.com/TP9fYwtRax
— こたつがめ (@kotatsugame_t) 2022年2月16日

あとは大鳥居が伸びた。14+の未鳥3譜面は本当にどうしようもなくて、たぶんこれが一番可能性があるはず。正当に難しいので、正当に頑張れば出ると思う。残りはSINister EvolutionとLove & Justiceで、どちらも鍵盤が押せない。

大鳥居SS+。もう無理 pic.twitter.com/px42Ii05Zr
— こたつがめ (@kotatsugame_t) 2022年2月16日

立ち食い蕎麦を食べて帰宅。疲れからしばらくぐったりして、シャワーを浴びてから買ってきたマイクの動作確認をした。なかなかよさそうだったので調子に乗ってYouTubeで生配信を行った。

www.youtube.com

「アルゴリズムと数学　演習問題集」の残りの問題が4問あったので、それを通した。特に言うことはなし。以前解こうとして謎に詰まってしまった部分もただの勘違いだった。ちょっとコードゴルフをして、まだ終わりたくないと感じたので、CF #760 div.3を解いた。

Dashboard - Codeforces Round #760 (Div. 3) - Codeforces

Aは先頭3要素が答え……と思ったら、3番目を飛ばすケースもある。かなり優しいサンプルで4つ目を見て気づいた。Bはある文字列の2文字目と次の文字列の1文字目が異なっていれば間が削除されているとわかる。制約から複雑なチェックは必要なく、間を埋めるだけでよい。一度も埋める操作が行われなかった場合は、末尾に適当に文字をつけ足しておく。Cは赤で塗られるインデックスたちの集合が2通りしかないので、両方試す。赤で塗った数の最大公約数を $d$ とするのが最適で、青色についてチェックすればよい。Dは大きいほうから $2k$ 個を消すとしてよい。消す要素を入れ替えることではスコアは1しか減らない一方、残す要素を増やすと1以上増えてしまうからだ。最後に消す要素をどうペアにするかを決める。小に大を組み合わせるという考え方ではなく、値の異なる2要素をペアにすると考えれば簡単。消す要素のうち過半数を占める要素があれば、その個数から $k$ を引いた分だけスコアが増えることになる。

Eは思いつくまでが難しかった。 $S=\sum a_i$ とすると、 $b_i-b_{i-1}=S-n\times a_i$ となるらしい。差分を取ることで他の位置からの影響を取り除けるということ。 $S=\frac{\sum b_i}{n(n+1)/2}$ でもあるので、これで全要素が求まる。あとは $a_i$ が正整数になるかを調べればよい。Fは $2^{62}$ 未満の範囲で問題文に書いてある操作を繰り返したら通った。一応理屈もあって、0を追加する操作は最初の1回以外無意味なので、操作で作れる数はそんなに増えないのだ。数の上限はオーバーフローしないところを狙ったが、2回目以降の操作は桁数が増える一方ということを考えれば $2^{60}\gt 10^{18}$ で切ってもよかった。Gは $a_i$ と $b_i$ をまとめて昇順に並べ、隣接する項との間隔が $k$ 以下のところを連結すると、同じ連結成分内は自由に交換していける。各連結成分でもともと $a_i$ だった要素を数えておき、大きいほうからその個数分だけ和をとっておけば、全部合わせて最大の値が求まる。これはクエリを $k$ の昇順に並べることでどんどん更新していける。

途中から眠気が強くて大変だった。また生配信しながら問題を解くのはプレッシャーがかかってかなり緊張すると分かった。今日は何とか全完できたので助かった。配信を終え、アーカイブをちょっと見直しただけでも、やはりマイクを変えた影響はかなり大きく感じられる。まず音量が大きいし、ノイズも全然ない。対して以前の配信の、あまりの聞きにくさに衝撃を受けた。第二回日本最強プログラマー学生選手権のエキシビションなど、かなり多くの人が視聴してくれたのにこの音質だったとは……。恥ずかしい限り。

午前6時就寝。

02/17(木)

午後2時過ぎ起床。ゲーセンから帰るときは腰がバキバキだったが、一夜明けて肩がバキバキになっていた。

非常に眠いところを何とか布団から這い出して、購買に向かった。食事を手に入れようとしたのだ。しかし閉店間際ということもありパン類・ごはん類がものの見事に売り切れており、仕方なくカップ麺を買うことになった。追加で注文していた本を受け取り、帰宅。

atgolferを動かしているサーバーはさくらのレンタルサーバーを利用している。毎月650円弱がちびちび口座から出て行っているが、いちいちメールが来たり通帳の1行を埋めたりするのが煩わしく感じられたので、1年分を一度に払う方法に変更した。契約当初は適当なところですぐ止められるようにという配慮で月ごとの支払いにしたはず。ただ、もう2年近くbotを動かしてきて、今更止めることなど考えられない状態にある。

無理やり起きたのでまだ眠気も残っているし、今日はゆっくりしつつ細かなタスクを終わらせようと思って、とりあえずテスター作業に取り組んだ。当然詳しくは書けないのだが、諸々すべて終わってみると日付が変わりそうな時間になっていた。その後失った時間を取り戻そうとするかのように、朝方まで起きてラノベを2冊読了した。

1冊目、「護衛のメソッド」2巻。面白かった。イラストも良い。2巻になって新キャラが出るも、相変わらず誰が黒幕なのかはっきりしなくてところどころ不穏な雰囲気がある。そんな中でも一切動じない主人公が格好いい。取り巻くヒロインの事情は前巻である程度明らかになったので、その部分はまあ安心して読めた。いちいち可愛らしくてこれも良かった。最後までたどり着いて、満足しつつあとがきを読んだら、この2巻でシリーズ完結と書いてあってびっくりした。まだ明らかにされていないことも多いし、ぶん投げた感じが否めない。作者さんは別作品が売れているので、そちらに注力したかったのだろうか。残念。

この作品の主人公もそうだが、俗世を知らない設定のキャラとか、あるいは冷静な知的キャラとかが結構好みの設定である。これは恐らく、主人公が何らかの外的要因に影響を与えられる展開が好みでないということに通じるのだろう。細かいところだと、主人公がからかわれて赤面するみたいなシーンもあまり好きではない。皮肉が通じずに相手がぐぬぬとなるか、あるいはドンと構えて余裕の言葉を返すみたいな行動に憧れを抱いている。

2冊目、「純白と黄金」。これも面白かった。最強のヤンキーがテーマということで、チームとかストリートとかの話が好きな自分としては興味を惹かれて購入した。とはいえこういうテーマにはリンチシーンがありがちで、それだけは苦手なんだよなあと思いつつ読んでみると、実際はほとんど超人バトルみたいな様相を呈していてびっくりした。主人公は自分の実力を隠したいといいつつ全然隠せていないので、周囲に強さを見せつけるシーンがちょくちょく挟まって快感だった。文中の形容詞の一部がヤンキーっぽく、口が悪くなっていて笑った。

午前8時半就寝。

02/18(金)

午後2時半、目覚ましで起床。

午後3時からインターン先の業務に関わるミーティングを、メンターさんに加えてもう一方を交えて行った。詳細は当然ぼかすが非常に有意義な時間だった。いろいろご意見を伺えたこともそうだし、何より自分の作ったものを今からでも使えそうだと評価して頂けたのが嬉しい。メンターさんと話している間はまだ改善点がたくさんありますねという感じだったので、急にゴールが目前に来たような錯覚を覚えた。もちろん改善点は改善点で当然これから実装していくことにはなる。それを終えて、続けざまに少しだけ1on1をした。進捗はないので先ほどのミーティングに関して少し確認して終わり。

サークルのバチャに出た。Python（もしくはPyPy3）で全問通した。どれも見覚えのある問題とは言え、順当に通せて一安心。6問目のguruguruは区間に一次関数を足せればよくて、遅延セグ木でぶん殴ろうとして冷静になり、差分を取ってimos法をした。7問目はすごいことをしたような記憶があって怯んでいたが、書いてみるとかなりシンプルになった。

https://kenkoooo.com/atcoder/#/contest/show/a13007e5-73d2-4500-91e9-c0405d293e89

しばらくテスター作業をしていた。TLにハーメルンの「アラサーがVtuberになった話。」の書籍化情報が流れてきてびっくり。最近Vtuberもののラノベが多い。

【お知らせ】
拙作「アラサーがVtuberになった話。」ですが、書籍化されることになりました。
出版社等の情報は許可出れば追ってこちらからお知らせします。
読者の皆さんがのおかげで連載続けられました。
感謝です。
現実世界のVTuber人気って凄い！って言葉に尽きますね。
— とくめい@アラサーV重版＆続刊決定 (@hameln_tokumei) 2022年2月18日

syosetu.org

夜はずっと日記を書いていた。その後またしばらくテスター作業をし、シャワーを浴びたりして午前4時過ぎに布団に入った。ラノベを読もうとしたが、思ったより眠気が強かったので、素直に寝ることにした。午前5時就寝。

02/19(土)

午後3時起床。1時間くらいゴロゴロした後また寝て、次に午後5時に起床。届いた生協の冷凍弁当を受け取ってまた眠ろうとしたがどうにも眠れず、ゴロゴロしているうちにこれ以上は生活リズムの崩壊が致命的になると考えて起き上がった。午後6時半だった。食事してからラノベを読んで、午後9時からAGBC239に出た。

Denso Create Programming Contest 2022(AtCoder Beginner Contest 239) - AtCoder

Aはdc。答えが小数になるのを見落として1WA。Bはdcでどう書いたものかかなり悩み、とりあえずRubyで通してから10Bの解を思いついた。CはC++で全探索。このあたりでAがさらに縮むことに気づいて愕然とした。Dも全探索で、これは素数判定を書くのが面倒なのでRubyを持ち出した。その後10分程度Rakuでコードゴルフしていた。残りはずっとC++。Eは上位20個だけ持つ。列のマージは毎回マージソートみたいな要領で行った。全部まとめてからソートしてもよかったらしい。Fは連結成分ごとに新たに辺を生やさなければならない頂点を管理して、その個数が最少の連結成分と最大の連結成分を繋ぐことを繰り返した。この貪欲っぽい操作の証明を考えているうちに、新たに辺を生やさなければならない頂点がただ1つしかない連結成分が常にないとダメだということに気づいた。コードには特に反映されていない。Gは問題文に最小カットと書いてある。ACLのmaxflowが最小カットも求められたことを覚えていたので、それを利用してコーディングした。辺を双方向に張っておらず1WA。

Exは、見た目的に $\lfloor M/k\rfloor$ を列挙して頑張るんだろうなと思った。 $M$ 状態のdpで遷移を愚直に行うコードを書いて実験してみると、確かにその商の値が一致していればdpの値も一致するらしい。これで、とりあえずdpの状態数が $O(\sqrt M)$ になった。遷移は、dpの各状態に対してそこに遷移できるサイコロの出目の範囲を求めることでこれも $O(\sqrt M)$ になる。まとめて $O(M)$ の解法ができて、出力は合うもののループ内部で割り算などしているため最大ケースでは8sec強とかなり時間がかかってしまった。ここでふと、dpのある状態を見てサイコロの出目の範囲を求めた後、それより1大きな出目で遷移することになるdpの状態を二分探索で求めることにしたら、なんと1.3secくらいになった。恐る恐る提出してAC。

全完24位。Exのdpの値が一致する話は、解説のようにdpのキーを $k$ ではなく $\lfloor M/k\rfloor$ とするとわかりやすかった。商の値が一致していればそこからさらに同じ数で割っても常に同じ値になるということ。また、遷移に必要な状態を1つずつ見るのではなく二分探索で飛ばし飛ばし見ると速くなったというのは、 $\lfloor M/k\rfloor$ が小さい場合に影響が大きくて、関係する $O\left(\sqrt{\lfloor M/k\rfloor}\right)$ 個の状態だけをうまく抜き出せたことによる。

コードゴルフ。Aはコンテスト中に気づいた改善が開始1分ちょっとで提出されており、大敗。Bはコンテスト中のdc 13Bが最短になっている。スタックに-9、0、1を積んだ状態で入力を読み、掛け算と足し算を行う。 $X\ge 0$ の場合は $X\times 1+0$ が得られ、これを10で割ることで答えになる。 $X\lt 0$ の場合は $|X|\times(-1)+(-9)$ が得られ、これも10で割ることで答えになる。Cは $( (x_1-x_2)^2+(y_1-y_2)^2)/2$ が $\{0,1,2,5,8,9,10\}$ の要素であればよい。テストケースハックをすると、集合を $\{0,1,2,3,5,6,7,8,9,10\}=\{0,\dots,10\}\setminus\{4\}$ に広げてもACできることがわかるので、AWKと正規表現で書いた。DはRaku。初めにgrepなどで書いたところをanyやらallやらのJunctionで書き換えていくと結構短くなった。Junctionの入れ子が便利で、 $A\le \forall x\le B.(C\le \exists y\le D.P(x+y))$ みたいな式をそのまま表現できる。

EはRubyで縮めていたら取られた。maxメソッドに引数を与えると上位 $n$ 個を抜き出してくれる仕様は、効くところではめちゃくちゃ効くという印象。ただ稀にしか目にしないので今日は忘れていた。GはPythonとnetworkx。minimum_cutというそのものそのままなメソッドがあって、コストと一緒にカットによって分割されたグラフをsetで返してくれる。頂点を倍加した状態で、source側のsetに頂点の入口が、sink側のsetに頂点の出口がそれぞれ入っていれば元の頂点を答えに含めることになる。各頂点について判定するのではなく、setの内容を弄った後に集合としての共通部分を取る方法にすると短くなった。FとExは手つかず。

午前2時からSRM824に出た。

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

Easyは成功に $F$ を、失敗に $-S$ を割り当ててZero-Sum Rangesをする。 $N$ の最大値が5e5で怖いなと思いつつmapで実装。結構後になって、値とインデックスのペアでソートした後計算する方法なら定数倍が軽くなったと気づいた。リサブはしなかった。Medは現在達成しているdifferenceをbitで表して、それと最後に出た目を持つdpを行う。bitを降順に見れば、それぞれのbitに対してdpの値 $D$ 個が $D$ 元の連立方程式で表せるので、解く。一応すべての $N$ を試してみたが、どれもちゃんと解けるようだった。Hardは何もわからず。

EM2完速めで7位、レートは2525→2587(+62)。highestから1だけ小さい。Hardは不可能枠だと思っていた。まず、相異なる行き先が決まったら互いに干渉せずたどり着ける操作列が存在することが示せるらしい。コンテスト中からそうだろうなとは思っていたものの、構成的に証明できないと実装できなかった。次に、ナイトがあるマスから別のマスへ進むときの最短手数が定数時間で求められるらしい。これは知らなかった。最後に、そのような手数をコストとして初期位置と最終位置の間の最小重み最大マッチングを求めると、最適な行き先が決定できる。

ナイトの移動の最短手数について。無限に広い盤面においてナイトが $(0,0)$ から $(x,y)$ （ただし $x,y\ge 0$ ）まで進むときの最短手数は、 $(x,y)=(1,0),(0,1)$ の時は3手、 $(x,y)=(2,2)$ の時は4手、それ以外は $c=\max(\lceil x/2\rceil,\lceil y/2\rceil,\lceil (x+y)/3\rceil)$ として、 $c+( (c-(x+y))\bmod 2)$ 手となるらしい。足しているのは $x+y$ の偶奇性に関する条件から出る値である。 $c$ の値は3種類の単純な下界を表していて、それがほぼ達成可能というのは驚き。証明を探したが見つからなかったので、自分で少し考えていた。

$c\ge 2$ なら $c$ を1手で必ず1減らせる。 $x\ge y$ なら $(x-2,y-1)$ に、そうでないなら $(x-1,y-2)$ に進めばよい。こうすると $\lceil (x+y)/3\rceil$ は必ず1減るし、 $\lceil x/2\rceil$ と $\lceil y/2\rceil$ のうち大きいほうも1減る。この操作で $c$ の値が減らないとしたら、それは $x=y$ かつ $x,y$ が偶数だった場合に限られるが、その場合 $\lceil x/2\rceil=\lceil y/2\rceil\lt\lceil (x+y)/3\rceil$ となっているので問題ない。 $x-1$ が負の数になる場合は、代わりに $x+1$ に進んでもよい。 $x=0$ ならば $c\ge 2$ より $y\ge 3$ で、 $\lceil 1/2\rceil\le\lceil (y-1)/3\rceil\le\lceil(y-2)/2\rceil$ であることからわかる。 $y-1$ についても同様。

そのように進んだときコーナーケースとなるマスに突入する場合は、突入する1歩手前で別の移動先を選ぶことで回避できる。このことは小さい範囲を実際に計算してみることで確認できる。 $c\lt 2$ の場合も同様に確認できるため、これで下界が達成可能ということが分かった。

ラノベを1冊読了。「今日も生きててえらい！」。前半はヒロインが主人公を全力で甘やかす話で、そういうヒモ願望が自分にない以上、ヒロインの好意が信じきれない主人公のほうに共感して正直気味悪がりながら読んでいた。しかし後半になって事情は一転。ヒロインと主人公がデートしている盗撮画像が校内で出回った話から、いかに主人公がヒロインに見合う人物になるかという話が展開されて、こちらは好みの話題だったので非常に楽しんで読めた。もともとヒロインの取り巻きをしていた人が、主人公が外見を整える前後で対応をガラッと変えるとかではなく、無関心だったのが興味を持ち始めるという描かれ方で、嫌にリアルで恐ろしいなと思った。

日記を書いて布団に入り、しばらくラノベを読んで就寝。午前10時だった。

02/20(日)

午後5時起床。しばらく布団でゴロゴロしてから起き上がる。ずっとテスター作業をして、午後9時からABC240に出た。

https://atcoder.jp/contests/abc240

Aはdcで1WA。人はなぜ。BはRaku。CはRubyの多倍長整数をbitsetのように使う。ここからはC++で書いた。Dはstackでシミュレート。Eはまず部分木に含まれる葉の個数を数えた後、もう一度dfsして区間の始点を求めた。Fはランレングス圧縮されたそれぞれの区間内における値の変化が二次関数になるので、頂点を求めたりして範囲内の最大値を調べる。多く調べて悪くなることは何もないため、範囲の両端と頂点の左右を毎回全部調べる感じになった。

Gは、 $X,Y,Z\ge 0$ となるように符号を反転した後、 $t=\frac{N-X-Y-Z}2$ を求める。この値が非負整数でなければ答えは0。非負整数だったなら $0\le i,j,k$ かつ $i+j+k=t$ となるようなすべての組 $(i,j,k)$ に対して $\frac{N!}{(X+i)!i!(Y+j)!j!(Z+k)!k!}$ の和を求めればよい。 $k=t-i-j$ は後からどうにでもなるので $i$ と $j$ について考える。値が2つの列の畳み込みの形になっているためそれができればよいのだが、列の長さがそれぞれ $t+1$ であるため、畳み込むと長さ $2t+1$ になる。この値は最大で $10^7+1$ になりうるところ、 $\bmod 998244353$ での畳み込みは長さ $2^{23}\lt 10^7$ までしか対応できないため、そのままでは計算できない。そこで、列を前半と後半に分けることにした。後半をインデックス $\lfloor t/2\rfloor+1$ 以降とすると、その要素2つの積に対応する畳み込み後のインデックスの値は $i+j\gt t$ となるため、答えには関係なくなる。よって前半×前半、前半×後半、後半×前半の3回畳み込みを計算すれば必要十分である。実装してから最大ケースとして適当にいくつか試したところ、どれも答えが1になってしまってよくわからない。とりあえず提出したら1900msで通って、ああ想定解ではなかったんだなあと思った。

Exはsuffix arrayを求めてその順番でdpしてみたりするもよくわからず、諦めてしまった。7完16位。Gの2次元版の問題を $O(1)$ で解く方法は以前知って感心した覚えがある。まあいくら感心してもコンテスト中に使えなければ無意味。ちなみに手元で試したら答えが1になったのは、本当はtime echo [INPUT] | ./a.exeとするべきところをecho time [INPUT] | ./a.exeとしていたかららしい。どうしようもない。

コードゴルフ。Aは $(a-b)^2\bmod 10$ でRコマンドを実行する16Bの解を思いついていたところ、 $a-b$ を9で割った余りでRする15Bに負けて呆然。コンテスト中に出したWAは、この余りを取る除数を8にしていたものだった。これは $a-b=-8$ で壊れてしまう。それにしても最近全然A問題の最短が取れない。Copilot対策だかでちょっとひねった問題が出るようになって以来、やけに苦手意識がある気がする。BはRakuで18B。wordsをSetにして要素数を見るだけ。問題を見て自明な最短コードだと思い、即座に飛びついた。取れてよかった。

CもRakuで、達成可能な数の集合を直接管理した。Setにすると要素への一律加算が簡単に書けなくなるので、uniqueで重複を省く。そうして作った集合に $X$ が含まれるかを見るのではなく、逆に $X$ から値を引いて行って $0$ が含まれるか見るほうが、いろいろうまくいって縮んだ。DはAWKで頑張る。EはRubyで頑張っていたらPerlに大幅に負けた。コンテスト中に2回dfsをしたところは1回で良い。これまでに見た葉の個数をグローバル変数で持って、部分木に入る前の値と部分木から出てきたときの値がそれぞれ $L-1$ と $R$ になる。

FもRuby。取られたものを取り返した。二次関数の頂点付近の値として見るべき位置は $\left\lfloor \frac b{-x}\right\rfloor$ になる。0除算を回避するため、 $x\ge 0$ の時は $-x$ の代わりに $-x-1$ を使う。その方法も、 $|x|\le 4$ であることを利用して入力文字列中の空白文字の位置を参照することで実現されていて、唸らされた。この値を $1$ と $y$ でclampして、あとは $x\ge 0$ の場合のために位置 $y$ も調べておけば十分らしい。基本的に頂点以外では位置 $0$ と位置 $y$ を調べたくて、位置 $0$ は直前の位置 $y$ と一致する。ただし最初だけ位置 $0$ が許されていないため位置 $1$ を調べることになるが、その場合 $b=0$ なのでclampした値が $1$ になってくれるということ。Gは手つかず。

午後11時半からCR #772 div.2に出た。全完4位。

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

Aは全要素のbitwise ORを1要素にまとめるのが最適。Bは左端からlocal maximumを潰していく。潰すときは3つ組のうち一番右の要素を変更する。このとき、真ん中の値に合わせるのではなく、もう一つ右の要素に合わせることで別のlocal maximumも一緒に潰せてお得な場合がある。サンプルにあったので助かった。Cは、数列の末尾に行くにしたがって変更できる操作が少なくなるので、末尾から順に考える。まず $a_{n-1}\gt a_n$ だとどうしようもないのでダメ。そうでないなら $i$ の降順に $a_i\leftarrow a_{i+1}-a_n$ としていくと、どんどん差が負の方向に広がっていきそうで良いと気付いたので、実装して提出した。しかしサンプルでWA。 $a_n\lt 0$ の場合、差が負の方向に広がらないらしい。そもそも $a_n\lt 0$ の場合は全要素が負になるしかなくて、どんな操作をしても $a_x=a_y-a_z\gt a_y$ となるため広義単調増加にはならない。よって最初からOKかそうでないかをチェックすればよい。この場合分けを実装してAC。

Dは、数をbit列とみなすと、 $y$ に対して $2y+1$ が右端に1を追加する操作、 $4y$ が右端に00を追加する操作とみなせる。数列 $a$ の要素それぞれに対し操作を逆向きに行っていって、数列の別の要素と一致した場合、操作していた数を削除する。これで同じ数を生成する値が存在しないようにできるので、あとはそれぞれの要素が $2^p$ 未満の範囲で何回操作できるかを数えて足し合わせればよい。つまり2進表現において桁数を1または2増やす操作を好きな回数繰り返す方法が、 $p$ 桁に至るまでに何通り存在するかわかればよくて、これは増やしてよい桁数に対する値を前計算できる。

Eは面倒。まず与えられた関係で辺を張って、連結成分ごとに考える。関係で結ばれた2つの車の向きは必ず異なるので、得られたグラフは二部グラフでないといけない。連結成分ごとに1つ車の向きを自由に決めてよいため、適当に塗り分けたものを車の向きとしてよく、これと関係から座標の大小関係を表す有向グラフが作れるので、それをトポロジカルソートする。閉路が存在したらこれもまたダメ。無事ソートできたら、座標としては適当に連番を振っておけば完成。一発で通ってハッピー。

Fは難しかった。いろいろ考察していたが、結局「 $i\lt k\lt j$ かつ『 $w_k\le w_i$ または $w_k\le w_j$ 』なる $k$ が存在するようなペア $(i,j)$ は答えにならない」というのが本質で、僕はそれをもうちょっと複雑な形で考えていた。解法は次のようになる： $j$ を全探索して、ペアにする意味のある各 $i$ に対してweighted distanceを計算し、セグ木の $i$ 番目に保存しておく。クエリは $j=r$ を処理した瞬間にセグ木に対して $[l,r)$ の区間MINを求めることで答えられる。ペアにする意味のある $i$ は、まず $i_0=j-1$ を試して、次に $w_i\lt w_{i_0}$ かつ $i$ が最大であるような $i_1=i$ を試して……というように、 $w_{i_k}\lt w_j$ になるまで探索していくのが必要十分。これはstackでインデックスを管理することで高速に求められる。 $w_i\ge w_j$ である間 $i$ をpopした後 $j$ をpushするという実装から、このような計算が全体で $O(N)$ 回しか行われないことがわかる。かなり綺麗になって感動した。

TCB44が終了していた。5位。WAのペナルティが大きすぎる。

ラノベを2冊読了。1冊目は「初恋のお姉さんを今度養うことになりまして」。昨日読んだラノベとは逆で、主人公がヒロインを甘やかす話。この本の作者はラノベ書きとしてはベテランであるという認識で、実際ラノベらしい展開が続くというか、スッと読める感じがした。その分特に何か思うこともなく、総じて印象に残らなかった。

2冊目は「最強魔術師の弟子は冒険者ギルドの始祖となる」。面白かった。何か大きな組織を立ち上げるというのは、自分の好きな設定である「組織のトップに立つという要素」「歴史を作るという要素」を両方兼ね備えていて最強に見える。さすがにラノベ1巻では始動後数日間分までしか描かれなかったので特に大きな組織というわけではないが、立ち上げるにあたっての困難を主人公たちが何とか解決していく様が描かれてそれはそれで良かった。将来全国的に広がっていく様子を空想するのも楽しいものだ。

主人公は師匠の権力的にも実力的にもかなり強いので、最終的にはそれで解決した問題もある。何かを始めるに当たって、強力なメンバーが必要不可欠であるというのは頷かれる。一方、十分に成長した組織においては個人の実力に何かを依存するのはできるだけ避けなければならない、というのもよくある話で、こちらはラノベらしく主人公を活躍させるには何とも難しい制約に思える。そのあたり学術的な正しさとラノベ的な面白さのどちらを取るかの程度問題になるはずで、僕なんかは何かを著すならできるだけ正しくありたいと考えてしまうものだけれど、面白さを優先する状況だっていくらでも考えられるのだ。実際、僕も読むなら面白いものを読みたい。

1か月ほど前に自分で自分の提出をHackした後ずっと放置していた問題、ECR121-Eをついに解いた。整理してみると、結局各頂点が「黒である」「黒に隣接している」「黒にたどり着ける」のどれかであると分かればよくて、3つ目の判定としては「自分を根としたとき、黒の頂点を部分木に2つ以上持つ子が存在して、その子が3状態のどれかである」かを調べればよい。部分木における黒の頂点の個数を全頂点に対して求めるのは、かなり単純な部類の全方位木dpになる。

Submission #147117599 - Codeforces

朝まではずっと日記を書いていた。