02/06(月)

午後4時半に起床し、即座にインターン先定例会に出席した。

先週木曜日に書いたコードが進捗。その翌日の1on1で今週のタスクについても指示されているから、発表内容には特に困らなかった。

勉強会はAHC017の話。せっかくインターン先がスポンサーとなったコンテストだったのに初日にコードゴルフしてから何も触れられなかったので、ちょっと負い目を感じている。辺の追加・削除を処理しつつグラフの連結性を判定したくなるらしく、Dynamic Connectivityが紹介された。それが効果的だったかはともかく、名前だけ知っていたアルゴリズムの一つとしてこの機会に実装の概要を学べたのはよかった。質疑応答が盛り上がり終了は午後8時となった。

先週土曜のABC288が予選となっていたToyota Programming Contest 2023 Springについて、決勝進出メールが届いていた。夏の第三回日本最強プログラマー学生選手権と同様前泊するつもり。近辺のホテルが続々埋まっているらしいが、遠慮せず上限ギリギリの値段で探せば十分見つかるだろうと思っている。

週記を書いて午後11時に投稿。それから2時間くらいYouTubeで時間を溶かしてしまった。

MF文庫Jの2月の新刊について、表紙イラストやあらすじが公開されていた。自分が非常に楽しみにしている「Vのガワの裏ガワ」2巻も2月発売。あらすじだけでどんな話になるのだろうかとワクワクが止まらない。イラストも良い。表紙の構図は1巻とほぼ同じに見えるのに、色合いが寒色から暖色に変わると受ける印象が全然違って面白い。

mfbunkoj.jp

午前1時からセミナーの準備を開始した。前回の残りが5ページくらいあるので、追加でほどほどに準備しておけば十分そう。教科書ではしばらくちょっとした命題とその証明が連続するので、上からいくつか読んでまとめ、4ページ程度メモを作成した。午前4時終了。

布団に入って少しなろうを開いたがすぐ寝落ちした。

02/07(火)

午前9時半起床。今日は空模様が悪そうだが、降るのは雪ではなく雨らしい。積雪ももう溶け切っているようだから原付で大学に向かった。

購買で朝食を買い少し遅刻して教室に到着、セミナー開始。同級生は今回セミナー準備がうまくいかなかったらしく、すぐ自分の発表になった。前回の残り5ページを話し終えたくらいで正午になりいったん休憩。購買でパンやおにぎりを買って昼食とした。

その後すぐ自分の発表が再開したわけではなく、博士課程の方の発表が2時間ほどあった。年明け初回のセミナーで詰まっていたところからようやく少し先に進んだ気がする。1か月経っているように見えて、集中講義や博論発表会で2回ほど博士課程の方のセミナーが潰れているからそんなものかという気持ちになった。少し進んだ先でまた詰まって今日は終了。

本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

それから自分の発表の後半。昨日新たに用意した分だが、特筆することもなく1時間で話し終えてしまった。これで今日は終了、解散！かと思ったら博士課程の方が黒板に何やら書き始められ、セミナー続行。博士課程の方を中心に途中学食で夕食を摂りつつ午後8時くらいまでやっていた。発表というより証明をつけるのがメインで、自分は次の性質を示した。

累積分布関数 $F(x)$ に対しその逆関数 $F^-:(0,1)\longrightarrow\mathbb{R}$ を $F^-(y)=\inf\{x\mid F(x)\ge y\}$ と定義したとき、これは左連続になる。 $0\lt y\lt 1$ と $\varepsilon\gt 0$ が与えられたときに $\delta\gt 0$ であって $\max(y-\delta,0)\lt \forall y'\lt y.(F^-(y)-F^-(y')\lt\varepsilon)$ を真とするようなものを見つければよく、具体的に構成できる。

$z=F^-(y)-\varepsilon/2$ としたとき $F(z)\lt y$ なので $\delta=y-F(z)$ とできる。すると $y-\delta\lt y'\Leftrightarrow y'\gt F(z)$ と $F$ の単調増加性から $F^-(y')\ge z$ が言えて、 $F^-(y)-F^-(y')\le F^-(y)-z=\varepsilon/2\lt\varepsilon$ が成立する。

帰宅してすぐにもう一度外出した。ゲーセンに向かう。以下のような理由で今日明日中に16クレ程度プレイする必要があるのだ。思ったよりセミナーが長引いてしまったが、まだギリギリ今日で終わらせられると判断した。

チュウニズムデュエルがまだ結構残っており、具体的には02/08までに35クレ程度プレイする必要がある。
週記（2023/01/30-2023/02/05） - kotatsugameの日記

今日も先週と同様14+をいくつか詰めた。新規にSSS+を三つ、また「GOLDEN RULE」のAJを出した。今日はラストが押せる日だったが、AJ間際は焦って擦らなくてもよいところを擦ってしまった。ギリギリセーフ。それで赤が増えたのが気になるとは言え、1個や2個気にするような精度ではない。

GOLDEN RULE AJ pic.twitter.com/Jgr5h9PR2I
— こたつがめ (@kotatsugame_t) 2023年2月7日

閉店まで粘ってギリギリでデュエルを終わらせた。

ラスクレでギリギリ終わった…… pic.twitter.com/JdlQ9WaYao
— こたつがめ (@kotatsugame_t) 2023年2月7日

立ち食いそばを食べて帰宅。何もする気になれず長い間TLを眺めていたが、何とかシャワーを浴びて布団に入った。少しなろうを読んで午前4時くらいに寝落ち。

02/08(水)

午後3時くらいに目を覚まし、なろうを読みながらAmazonの配達を待っていた。先週日曜日に注文した本棚が今日届く予定。玄関先に置かれると持ち運べないので、是が非でも部屋の中まで入れてもらいたかった。無事受け取り、午後4時半くらいに寝た。

午後7時起床。すぐに本棚の組み立てを開始した。3時間くらいかけてとりあえず形にはなった。

本棚組み立て・男子シングルス pic.twitter.com/0ew4kvLgZ6
— こたつがめ (@kotatsugame_t) 2023年2月8日

上半分と下半分をそれぞれ組み立て、途中で合体させる。ここはどう考えても二人必要そうに見えるし実際二人以上で作業するよう説明書に書かれてもいるが、一人でもなんとかなった。つまり上半分を持ち上げることさえできればよいのだ。そんなにガッシリした本棚ではないようで思ったより軽かった。

合体にはカムロックなるボルトとナットの組み合わせが使われていた。ユルユルなように見えて締めてみると案外しっかりしている。興味深い部品だった。

ツイートの写真からさらに棚板を入れたところで時間になり、Codechef February Cook-Off 2023 div.1に出た。2022/09/23以来ということで久しぶりのCodechef div.1だ。

https://www.codechef.com/COOK144A

TAKENOTLESSは $A$ の最大値がちょうど一つなら先手勝ちというところから考察を進めていった。同様に最大値が奇数個あれば先手勝ちだが、偶数個ある場合どうなるか考えてみると、どうやら2番目に大きな値に判定が移るらしい。まとめるとどれかの数が奇数個存在するのが先手勝ちの必要十分条件になった。

DUMBLEDOREは $ans_{i,i}$ から降順に考えていくとわかりやすかった。 $ans_{i,i}$ だけかかってしまう人を適当に一人選び、その人のタスクで $T$ 最大のものを1個取り除いた状態が $ans_{i,i-1}$ を達成する。以下同様。これは逆に、タスク $T_{i_1},\dots,T_{i_k}$ を持っている人は $ans=T_{i_1},T_{i_1}+T_{i_2},\dots,T_{i_1}+\dots+T_{i_k}$ となる瞬間がそれぞれ1回ずつあるということになって、差分更新が非常に簡単に書ける。半信半疑で提出したら通った。

MINIMIZESINはダメダメだった。累積和 $\bmod{180}$ を考えるまでは良かったが、その後bitsetを遅延セグ木に乗せようとして1時間ほど溶かしてしまった。気合いを入れると値のインデックスの取得もできるように思ったのだ。書き上げるも全然うまく動かず、ここでようやく正気に戻った。

鳩ノ巣原理から区間の長さが180以上なら必ず累積和2か所の値が一致し、その間の区間和が180の倍数になる。そういう区間が見つかるまで探索して、見つからなければあきらめて $\bmod{180}$ 後の最小値を調べる。どちらもクエリあたり180の定数倍ステップの計算しかしないので間に合う。

POTTERCYCLESはひたすら実験するも解けず、3完46位。レートは2889→2855(-34)。コンテスト後に以下のツイートを見ながらupsolveした。

n: 奇数で奇置換なら無理、それ以外できる

奇置換ならとりあえず偶置換に直す
a_i -> i に辺を貼ったグラフを作る
このサイクル順に頂点突っ込んだ vector の逆順で操作するとデカいサイクル一個 + 1 頂点沢山になる
1 頂点 -> デカいサイクル逆順
で同じことすると大きいサイクル一つになる
できる
— のいみ (@noimi_kyopro) 2023年2月8日

何も考えずfunctional graphのほうに進んでしまい、置換の符号を考えるのを完全に忘れていた。長さ奇数のサイクル1個と1頂点がたくさんならサイクルを逆順に辿れば2手でできることは分かっていたが、それを作ろうという発想にならなかった。揃えるのに5手以上必要なケースもあると思い、最短手数を必死に探していた。

言われてみれば、サイクルを順に辿った列をつなぎ合わせてソートするとサイクルごとに1頂点を残して全部合うし、残ったものはそれ自体が一つの大きなサイクルになる。そして置換の符号を調整しておけば、そのサイクルの長さは必ず奇数になるのだ。ここまで高々2手なのでこの後の2手と合わせ制約ピッタリになる。

コンテスト後は新しい本棚に本を入れていた。買った順番でバラバラに入っている状態が好みだが、さすがに使いづらいのでソートした。もっぱら配置決めに時間を使い、朝方にようやく完成した。部屋にある文庫サイズのライトノベルは全部ここに入れてある。古い本棚には大きなサイズの本と一般の文庫が残された。

ハァハァハァハァ pic.twitter.com/Wo5PnHC1Ci
— こたつがめ (@kotatsugame_t) 2023年2月8日

古い本棚がかなり空いたので別の用途に使いたい。とりあえず棚板をずらそう、と思ったら1本ダボが抜けず非常に苦労した。指で必死につまんで引っ張っていたが、ただただ爪が食い込んで痛いばかり。まったく抜ける気配がないため、明日大家さんからペンチを借りようと思う。

明日は家飲みで1日潰れる予定だから、金曜日の1on1に向けてインターンの進捗を産んでおく必要がある。腰が重くずっとなろうを読んでウダウダしていたが何とか午前10時前に完成した。布団に入ってまたなろうを読み、午前11時過ぎ就寝。

02/09(木)

午後3時過ぎ起床。筋肉痛で足腰が満遍なく痛いし、ダボをつまんだ指先も痛い。

大家さんに連絡してペンチを貸していただいた。昨日の苦労が何だったのかと思うくらい簡単に抜け、拍子も抜けた。

その後外出。ホスフィンと合流し、微妙な時間の食事を摂ってドンキで買い物して帰宅した。家飲み開始。

飲酒します pic.twitter.com/LzcDaEFIdp
— こたつがめ (@kotatsugame_t) 2023年2月9日

今日はホスフィンが持ってきた日本酒3本だった。どれも宮城県のお酒で、飲み比べしようとのこと。日本酒の良さを知ろうと無理やり口内に留めて味わったら苦さを感じるばかりだったが、ホスフィンに香りや喉越しなど味以外の観点も教えてもらって、無理に味わわないようにしたら幾分か飲みやすくなった。2本まではそのまま飲み、最後の1本はジュースで割って飲んでいた。

お酒を飲んでいる間、動画は見ずにずっとボードゲームをしていた。新しく買ったものは「バトルライン」「ヨメン」「Blade Rondo」。それぞれ感想を書く。

「バトルライン」は9並列でポーカーみたいなことをするゲーム。結構楽しかった。「偵察」という戦術カードの効果には「部隊・戦術カードの山札から好きな組み合わせで3枚のカードを手札に加えます。……」と書かれている。自分とホスフィンはこれを「自由に3枚サーチできる」と解釈しプレイしていた。あまりに強すぎて使った側が必勝のゲームになり、さすがに変だと思って調べたところ、山札の上から合計3枚ドローするカードだと判明した。

「ヨメン」は前回プレイした「タギロン」の続編みたいな位置付けのゲームらしい。立体配置を考える必要があるし質問の自由度も高くてより難しくなっている。ところで自分の感じる難しさと面白さにはあまり関係がない。2回くらいしかプレイしなかったが、あまり好きではないと感じた。

「Blade Rondo」は限られたカードプールから7枚ずつ手札を持って対戦するカードゲーム。一目見てイラストに惚れ込んだ。実際にプレイしても非常に面白かったので、総合してこれまで購入したボドゲの中では一番のお気に入りとなった。同シリーズの後継作品があと四つあるらしい。今すぐにでも全部買ってしまいたいが、家飲みの度に一つ二つ買ってじっくり楽しみたい気持ちもある。

自分は「フレアビスカス」とレスポンスカード・使い切りのカードで手札を固め、中盤から4コスで6ダメージの魔法攻撃を繰り返す戦法をよく使っていた。ホスフィンは「マナティックルピナス」と「トリビュートリリィ」で一気にダメージを稼ぐことが多かったように思う。二人ともプレイするうちに物理攻撃をあまり使わなくなっていった。

www.dominagames.com

お茶を挟まずにお酒ばかり飲んでいたのが悪かったのだろう、午前2時くらいに急激に吐き気が来た。しかし嘔吐の経験がないので便器を前にしても何も出せず、それはそれでつらい。少し持ち直したところで布団に倒れこみ、寝た。

02/10(金)

午前6時過ぎに意識を取り戻した。ホスフィンも仮眠していたらしく、まだ部屋にいた。自分が潰れた後も飲んでいたのかお酒が全部なくなっていてびっくりした。まさか二人で飲み切ってしまうとは思わなかった。少し片づけをして、ホスフィンが帰るのを見送り、また寝た。

午後1時過ぎ起床。今セメスターで応用数理総論を担当されていた先生の最終講義にオンラインで参加しつつ、届いていた新春TCB2023の賞品を開封した。

大変お世話になっております。
次回のTCBにもぜひご参加ください！
引き続きTechFULをよろしくお願いいたします。
TechFULサポートチーム pic.twitter.com/bwbGFs74cu
— こたつがめ (@kotatsugame_t) 2023年2月10日

カイリキーのPCデスクになった pic.twitter.com/sbWWJDVOdz
— こたつがめ (@kotatsugame_t) 2023年2月10日

2021年の新春TCBでもほぼ同じ機種を貰っておりこれで二つ目。HHKBも2台、PCも2台あるのでバランスがよい。そして、このキーボードとマウスはすべて競プロで得た賞品となる。
週記（2023/01/23-2023/01/29） - kotatsugameの日記

1時間程度で終了し直後から1on1。通常の進捗報告やタスク設定のほかに、サーバを立ててプログラムを動かすことになったのでその話もした。サーバの設定をやらせてもらえることになり、見守って頂きながらしばらく格闘していたが、全然うまくいかない。最終的には既存のサーバの設定ファイルをほぼコピペしてくるような形になった。それでも良い経験になったと思う。今のところは期待通りの挙動をしている。

結構長引いて午後5時くらいに終了。今日はこの後競プロサークルの追いコンがあるので、シャワーを浴びて外に出た。雪がかなり降っている。この時点ですでに遅刻が確定しており、さらにゆうちょ銀行を探すのに手間取って集合時刻から20分ほど遅れてしまった。直接お店に向かって合流した。

今日は武屋食堂というコロナ禍前に確定新歓でよく使っていたお店で飲み放題付きのコース。出てきた料理はすべて写真を撮り、以下のツイートのツリーにまとめてある。

食事 pic.twitter.com/zKIt82LKKW
— こたつがめ (@kotatsugame_t) 2023年2月10日

午後9時過ぎに店を出て二次会でカラオケに移動した。ボドゲを持ってきていたので1戦だけ行ったが、会話が不可能なのでびっくりするくらい楽しくない。その後は普通に歌を歌って楽しんだ。

自分が歌ったのは「大地讃頌」「君の知らない物語」「フォニイ」。大地讃頌は音もリズムも覚えておらず何もできなかった。フォニイはその辺りちゃんと覚えてこそいるものの、シンプルに難しくてボロボロだった。君の知らない物語だけは辛うじてまともに歌えたと思う。

午後11時に解散し、閉店間際のゲーセンで1クレだけ遊んで帰宅。昨日空けた酒瓶等をゴミ捨て場に出した後シャワーを浴びて、それからずっと日記を書いていた。午前8時前に就寝。

02/11(土)

午後2時ちょっと前になんとか起床。すぐUniversal Cup 3回目に参加した。今日のセットはPoland由来らしい。

The 2022 Polish Collegiate Programming Contest (AMPPZ 2022) - Dashboard - Contest - QOJ.ac

チームでCGDAMKBELを解いた。自分はCDABEの実装を担当した。

先頭から順番に読む担当だったので最初にA問題を開いたが、TL 42secと書いてあって目を疑った。ほかの問題もかなりダイナミックにTL・MLが変更されている。感想戦の時に聞いた話ではこれはPoland典型で、ほかのセットもそんな感じだったようだ。

コンテスト開始早々にたくさん問題が通され始めた。そのうちCGDAはポンポンと通って、一瞬一位になった瞬間があったような気もする。Cは自明。Gはかっつさん。Dは親子で部分木のサイズを比較し答えにならない $d$ に対してimos法でチェックする。これがすぐ思いつけたのは良かったし少し面白いとも感じた。Aは $a+b+c\le 5$ で全探索し、見つからなかったら $(a,b,c)=(0,0,6)$ が必ず答えになる。TL 42secにビビっていたがなんて事のない簡単枠だった。

ここから少し時間が空いた。通されていたのはMKBIで、Mはぷらさんが、Kはかっつさんが通した。自分はその間にBとIを読み、多く解かれていたIを考えていた。

$k+1$ 個以下の連続部分列に分けてそれぞれの転倒数の総和を最小化する問題に帰着できる。ここで $k$ の制約を忘れてしまい、解けたものと思って実装に割り込んだ。サンプルが合わず正気に戻った。 $n\times k$ のテーブルをin-placeに更新していくことを考えると、行に対する加算と列の最小値取得クエリに対応できればよい。しかしそのようなデータ構造を知らない。

行に対する加算について、上の行ほど大きな値が加わるという事実から何かできそう。例えば列ごとに見ると三分探索できるんじゃないかとか、最小値を取る行は単調増加じゃないかとか。しかし詳しいことはわからなかった。

Bの考察に入っていたぷらさんに呼ばれたので見に行った。両端と $p$ 最大はかならず開業すべきらしい。これを発展させると、開業させる $p$ の列は最大値までが単調増加、そこから単調減少になる。対称性から単調増加の部分だけ考察すればよい。

$p_i\le p_j\le p_k$ がこの順で開業しているなら、 $[i,k]$ のみを考えたときの収益は $(p_i+p_j)(j-i)+(p_j+p_k)(k-j)$ となる。 $p_j$ の開業を取りやめた場合は $(p_i+p_k)(k-i)$ となる。前者が後者より大きいという式を立てて整理すると、 $(p_j-p_i)/(j-i)\gt(p_k-p_j)/(k-j)$ となった。

実はこれは $(i,p_i),(j,p_j),(k,p_k)$ という3点の並びが上に凸となることを表す。ここで凸包を取るアイディアが思い浮かんだ。詳しい証明はできないもののいかにもそれっぽそう。ぷらさんは凸包の実装に自信がないということで、自分が奪い取って書いた。出したら通ってラッキー。

ぷらさんにIの考察を説明し、それっぽいという同意が得られたので実装してもらい自分はEに進んだ。TL 30secでML 8MBという意味不明な問題。最初に作れるのは $2x-y$ と $2y-x$ のみだから、片方しか作れないケース、つまり $2x-y\le 0$ のケースを考えた。

実験すると $k\in\mathbb{Z}_{\ge 0}$ に対して $(k+1)y-kx$ という形の数しか作れないことがわかり、ここから条件が $x\mid y$ と出る。個数を式で書けば $\sum_{x=1}^n(\lfloor n/x\rfloor-1)$ で、商列挙でカウントできる。

次は $2x-y\gt 0$ のケースについて。 $d=y-x$ と置いてこちらも実験すると $k\in\mathbb{Z}$ に対して $x+kd$ という形の数のみが全部作れると分かった。正確には正である必要もある。ここから $d\mid x$ が条件だと思い込んでしまい、割り込んで実装した。当然サンプルが合わない。

$g=\gcd(x,y)$ と置くと $x\equiv g\pmod d$ が条件。 $g$ とその倍数 $d$ を固定したとき、求めるペア $(x,y)=(x,x+d)$ は $\lfloor (n-g-d)/d\rfloor$ 個ある。 $d=kg$ と置くと $1\le k\le (n-g)/g$ に対する $\lfloor (n-g-d)/d\rfloor=\lfloor\lfloor (n-g)/g\rfloor/k\rfloor-1$ の総和が求めたいものとなった。

よく見ると $n\leftarrow\lfloor (n-g)/g\rfloor$ とした上で $2x-y\le 0$ のケースの個数を求めたのと同じ形をしているが、別に再帰的に解くわけではなく、ここでも商列挙をしてしまえば終わり。しかし試すと間に合わない。メモリ制限ギリギリの $n\le 1.5\times 10^6$ まで前計算したら通った。この前計算も愚直にやると間に合わないので、倍数列挙で値の差分を計算した後累積和を取って求めている。

後から聞いた話では切り捨て除算を整数ではなく浮動小数点数で行うと速いらしい。今の制約なら誤差も出ないようだ。これで $O(n^{3/4})$ が通るとの話。しかし自分の解法もちゃんと解析すると同じ計算量のはずなのに、試してみてもやっぱり通らなかった。商列挙を一つのループにまとめようとすると、平方根で処理を分けるより割り算の回数が増えてしまうので、その辺りが悪いのだろう。

素数カウント( $\mathrm{O}(\frac{N^{\frac{3}{4}}}{\log N})$・高速化版) | Nyaan’s Library

Lはかっつさんが単独で通した。Iはぷらさんといろいろ試していたものの上に書いていたことがすべてうまくいかず、結局通らなかった。9完71位。

感想戦。Gは泥棒の移動を無視して捕まるまでの時間を二分探索で求めるらしい。非常に頭が良いと感じた。Mはコンテスト中に自分もちょっと考えたが、ぷらさんによって後ろから見るというアイディアが出た段階で離れた。実際それでうまくいくようだ。復元は敵かどうかのフラグを下ろしながら見ていくと簡単そう。

Kは古代のARCのちょっとした一般化だったとのことで、ひたすら面倒そうなので通してもらえて助かったという感想。Lは必要条件を集めたら十分条件になっていたようだ。構築が重み降順でよいのはエスパーだったそうだが、感想戦の時に示すことができた。手数が多そうなのにほぼ最後までしっかり詰めているの偉すぎるという気持ちに。

C - 五目並べチェッカー

自分のEの説明が嫌になるくらいへなちょこで心残り。ポイントは $\lfloor (n-g)/(kg)\rfloor=\lfloor\lfloor (n-g)/g\rfloor/k\rfloor$ と分解したところだと思っていたので、それを強調しようとしたが、導入する変数がちょっと多くて話しながら迷子になりかけた。するとフィラーも多くなるし、頻繁に人の理解を確認したくなって、説明が途切れ途切れになってしまう。感想戦の前に、日記にそのまま書けるくらいにはまとめておきたい。

午後8時過ぎ解散。手元を撮影する準備を整えて午後9時からABC289に出た。先週は机の上にラノベを積みその上にWebカメラを置いていたが、スマホアームが使えることに気づいた。

競プロYouTuberです pic.twitter.com/TT63VEKgaJ
— こたつがめ (@kotatsugame_t) 2023年2月11日

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289） - AtCoder

Aは見た瞬間tr 01 10。Bは問題文がいかついがレ点の説明をしているだけだった。連結成分の取得は毎回右側に伸ばせるだけ伸ばせばよい。Cはbit全探索。集合の個数を $M$ ではなく $N$ にしていて1WA。Dは $N\le 10$ に気づけば終わり。Eは二人がいる頂点をペアで持つdpを書くと、状態数 $O(N^2)$ 、遷移が合計 $O(M^2)$ なので間に合う。

Fは $(x,y)$ から $(X_1,Y_1)$ と $(X_2,Y_2)$ で2回操作すると $(x+2(X_2-X_1),y+2(Y_2-Y_1))$ に移動する。このことから $a\lt b$ 、 $c\lt d$ なら各座標 $\pm 2$ ずつ調整することが可能で、座標の偶奇さえ合っていればどこにでも行けると分かった。そもそも操作で座標の偶奇は変化しないので、これは必要条件でもある。 $a=b$ または $c=d$ の場合は最初に $(a,c)$ で操作するかどうか試せばよい。操作回数の偶奇を両方試していることに相当する。

Gは商品ごとに独立に解いてよい。 $P$ を中途半端にする理由はないので、 $P=B_i+C$ となる $i$ が存在するべき。このとき $B$ が昇順ソートされているとすると、 $i$ が0-indexedとして購入者は $N-i$ 人だから、売り上げは $(N-i)(B_i+C)=(N-i)B_i+NC-iC$ と計算できる。 $NC$ は定数項なので $(N-i)B_i-iC$ という $C$ についての一次関数を最大化する問題になった。

ライブラリを窃盗すればすぐ通せるが、せっかく動画を撮っているので自分で実装することにした。まず傾きの単調性を利用して最大値を取りうる直線だけ記録。 $C$ ごとにその上で三分探索する方法は本当に正しく求まるか自信がなかったので、 $C$ もソートしてどんどん見る直線をずらすように実装した。

Exは何もわからず。3人の距離を2変数において変化を確かめても綺麗な形にならなかった。2変数の形式的べき級数に書き直してもみたが、そこから先は経験がない。

7完30位。Aはコンテスト開始9秒でFAを取れた。久しぶりのFAだし一桁秒でのACはこれまでで初めてのはず。

コードゴルフ。AはFAの提出がそのまま最短。Bはstackを持って出力する方法があるらしく、このstackを関数の再帰で表現した以下のPerlコードが美しく短いと感じる。自分のコードではないし縮みもしない。CはRubyで再帰。以降は手付かず。

atcoder.jp

午後11時からTROC #31に出た。

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

Aは $S+T$ 。Bは最も近いところに貪欲に移動してよい。Cは $f=0$ となるのが $\lfloor N/M\rfloor$ 人で、次に小さい $f$ が $1/M$ なので、 $\lfloor N/M\rfloor/N\ge 1/M$ が必要。ここから必要条件 $M\mid N$ が出て、これが十分であることもほぼ明らか。

Dは $W$ をいくつか選びデクリメントによってdistinctにして、対応する $P$ の総和を最大化する問題。 $W$ の降順に見て $P$ を優先度付きキューで管理し、都度最大値を取得していけばよい。

Eはそれぞれの辺についてそれがessentialとなる座り方を数える。つまり、その辺を取り除いてできる二つの連結成分から人が交互に座る場合の数だ。 $K$ が奇数の場合はそもそもありえないので答えは0。偶数の場合は各連結成分から $K/2$ 人ずつ選んで並べる方法なので、簡単なcombinationで書ける。

Fはそれぞれが次に着地する柱の番号を持つ $N^2$ 状態のdp。同じ番号の柱に着地するのは $N$ 状態しかないので、それぞれ $O(N)$ かけてジャンプ距離の候補を列挙し一致するものを採用しても間に合う。そうでない状態はより小さい番号の柱にいるキャラクターをジャンプさせる。このときより大きい番号の柱ならどこにでも着地させられるので行または列全体への遷移となり、行全体・列全体を表す変数に配って毎回貰うようにすれば定数時間で実現できる。

Gは累積XORを取って桁ごとに考える。先頭の0も含めた $N+1$ 個のうち $2^k$ のbitが立っているものを $c$ 個とすると、 $S$ には $c(N+1-c)\times 2^k$ だけ寄与する。 $k$ ごとに各 $c$ を達成する場合の数を求め、先ほどの寄与をインデックスにしてすべての $k$ について畳み込めばよい。場合の数は多項式を考えて求めることにした。

直前の累積XORでbitが立っているかどうかも必要なので、多項式は二つ持つ。よって $A$ を一つずつ見ていく遷移が1次式を要素に持つ $2\times 2$ 行列になる。そのような行列全体の積を半分ずつに分けて計算していくコードを書いたら通った。そもそも寄与の値は0の次に小さいのが $c=1,N$ のときの $N\times 2^k$ で、これが $S$ 以下にならないなら $c=0$ だけ確認すればよい。よって $N$ が小さいか計算すべき $k$ が少なくなって、思ったより高速。

Hは解けず。場合の数を微調整しながら進んでいくdpを考えていたが、思ったより必要な情報が多く間に合いそうな形にまとめきれなかった。

Gまではかなり良く7完最速で6位、2771→2799(+28)。Bの元ネタがおそらくチュウニズムでびっくりした。

ABCの動画を公開した。撮ったものをそのままアップロードしてYouTube上で前後を切り落としたが、アップロード後の動画処理を待った後さらに切り落とした後にも同じくらいの待ち時間が発生して大変だった。横着せず手元で完成させたほうがいい。

動画の途中で「蟻本の式が間違っている」ということを口走ってしまったが、最後のほうでちゃんとチェックして正しいことを確認している。悪影響を与えるといけないため、このことは概要欄にも記載しておいた。

www.youtube.com

朝まで日記を書いていた。午前9時頃布団に入り、1時間ほどラノベを読んで就寝。

02/12(日)

午後5時起床。

応用数理総論の期末レポートの評価が出ていた。なんと満点！以前日記で言及した以下の部分は順序数の足し算に関する話で、具体的に書くと、より小さい順序数の足し算に帰着した後適当に「帰納的に示される」と述べて終わったのだった。解説を読んでこれがいわゆる超限帰納法だったことを知った。

かなりそれっぽい式変形を行えたがその後のステップがわからない。もう元気がないので適当にまとめてレポートを完成させてしまった。
週記（2023/01/30-2023/02/05） - kotatsugameの日記

「素数が無限個存在する」、つまり「どんな数にもそれより大きな素数が存在する」ことを表す $\Pi_1$ 文を書く問題の解説がよくわからなかった。 $x$ より大きな素数を見つけるのに上から $x!+1$ で押さえると広義の $\Pi_1$ 文で、ベルトラン＝チェビシェフの定理を使って $2x+2$ （ $x=0$ を考慮）で押さえると厳密な $\Pi_1$ 文になるらしい。そもそも広義云々というのは講義に出てきていないし違いがよくわからない。どちらも再帰的に計算できる上界という意味で変わりないと感じている。

午後5時半からCF #852 div.2に出た。

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

Aはまず $m+1$ キロごとに貪欲に買って、最後に余った部分を調整すればよい。変なケースがあると思って少し考え込んだ。

Bはlocal maximumとlocal minimumを一つずつ作るのにその差の2倍だけ長さが必要になる感じなので、それぞれ $x$ と $y$ だけ用意すれば十分。具体的には $x,x-1,\dots,y+1,y,y+1,\dots,x-1$ でよい。制約に $x-y$ の最大値が書かれていないように見えて、出すのは勇気を要した。Outputの欄に書いてある $\sum n\le 2\times 10^5$ がそういう意味だったのだろう。

Cは各 $l$ に対する $r$ の最小値、また各 $r$ に対する $l$ の最大値が求まる。これを使って一度数え上げ問題を解いてしまった。実装まで終えてからサンプルを見て間違いに気づいたが、修正は簡単だった。

Dは順列に対してありうるMEXとそれを達成するのに必要な区間の制約が列挙できるので、両方の順列に対して計算しMEXを全探索することで答えが求まる。

Eで3WAした後、順位表を見てたくさん解かれていたFに進んだ。何も考えずMoを書いたらクエリ処理にsetが必要で当然TLE。高速化も不可能だったので別の方針を考えた。区間の $r$ を昇順に見ることを考えると、毎回すべての $l\lt r$ に対し $|a_l-a_r|$ を計算してセグ木のインデックス $l$ に乗せることで答えが求められる。

ここで特に、 $l$ を降順に見ている場合はこれまで計算した値より $|a_l-a_r|$ が小さくなるものしか新たに計算する必要がない。 $a$ をインデックスとして位置をセグ木に乗せ、区間MAXを取得することで次に計算するべき $l$ が高速に手に入る。今 $a$ は順列だから、実はこのようにした場合考えるべき $(l,r)$ のペアが十分少ないのではないかと考えた。証明はできなかったがまずいケースも思いつかなかい。提出したら通った。

E。 $m$ 人満足させるとき達成可能な $k$ の最大値を求められればよい。満足する人は $a$ が小さいほうから $m$ 人としてよい。同じ本を読んだ人の中に満足した人としていない人が混在する場合を忘れて同じ本を読んだ人は全員満足させようとしていたのが3WAの原因だが、まずその実装を説明する。

$a$ をソートしておく。 $m$ 人満足させる、特に $a_m$ に対応する人を満足させようとしたとき、 $a_{m-a_m+1},\dots,a_m$ に同じ本を読ませるのが今の場合最適で、問題は $m-a_m$ のケースに帰着される。人数が多い分には問題ないのでこの値は $m-a_m$ 以下なら何でもよい。いずれにしても $m\ge a_m$ なら $m$ 人全員を満足させられて、残りの $n-m$ 人はバラバラの本を読ませておくと $k$ を最大化できる。

忘れていたケースを付け加える。満足した人としていない人が混在する場合、そのような本は高々1種類で、そこで満足した人の $a$ はできる限り大きくするべきと分かった。よって先ほどの計算をおおむね流用できる。 $m$ 人を満足させるときの $k$ の最大値としては、 $a_1,\dots,a_m$ が読む本の種類数に加えて残り $n-m$ 人が読むバラバラの本がある。

これを発展させて $i$ （ $\gt m$ ）人を満足させてみる。バラバラの本を読んでいる人のうち $a_i$ 人に同じ本を読ませて $a_{m+1},\dots,a_i$ を満足させるのが良いだろう。 $n-m\ge a_i$ と $i-m\le a_i$ が条件として必要で、種類数は $-a_i+1$ される。種類数の差分が一定なので、条件を満たす $m$ から種類数最大のものを探すことで求める新たな種類数が得られる。以上のことをセグ木で実装したらすんなり通った。

全完22位。Fは $a_l$ と $a_r$ の大小関係を固定すると「これまで計算した値より $|a_l-a_r|$ が小さくなる」という部分がより強く「半分未満になる」と言えるらしい。この事実には順列という条件は特に使われていない。

食事してAGCまで落ち着かない時間を過ごした。今回も録画する準備を整え、午後9時からAGC061。

AtCoder Grand Contest 061 - AtCoder

Aは置換を考えてもよくわからなかったがどんなswapが行われるか観察するとかなり見通しが良くなった。操作する区間の幅が2増えるごとに大規模なキャンセルが起こり、1と2、3と4のようなペアの間でしか意味のあるswapが発生しないらしい。このあたりで実験コードを書いて確かめた。

$N$ が偶数の場合はこれで答えが2通りになるし、奇数の場合も4通りには収まりそう。だから全探索してチェックするという方針が取れる。あとは $N$ が偶数のときに特定の2数がswapされるか高速に判定できればよい。

どこでswapが行われるかを $N\le 16$ くらいまで手で確かめると、シェルピンスキーのギャスケットが見えてきた。そういえば「上の段をずらして重ね合わせる」のは二項係数の計算だったから、その偶奇がこういう模様になっているのだ。巨大な二項係数の偶奇はLucasの定理で一発。 $\binom n k$ の $n$ と $k$ を丁寧に確認して実装し、先ほど書いた実験コードで確かめたところ $N\le 33$ までの正答が確かめられた。

提出して無事AC。30分ちょっとかかってしまった。

この後Bに1時間、Cに残りの時間を費やしたがどちらも何もわからなかった。1完172位でパフォーマンス2489、レートは2875→2842(-33)。順位がちょうど100位となってギリギリ銅冠は剥奪されなかった。せっかく撮った録画だがさすがに情けなさすぎるため削除した。

Bは手で試して $N=3,4$ の場合の構築を見つけ、 $N=5$ で力尽きた。コンテスト後のTLを眺めていると、 $N\times(N+1)$ のマス目を書いて1マス1辺に対応させその上でジグザグの線を描いている人が多く、自分も試してみると $N$ 奇数の場合の構築が分かってしまった。残念。 $N$ 偶数は試していない。

Cは解いた人のツイートなどを少し読んで、dpを微修正しながら進んでいくというコンテスト中に頑張っていた方針が間違っていなかったことを確認した。しかし改めて考えてみても本当に何もわからなかった。まさに手も足も出ない問題。

ラノベ「隣の席の美少女をナンパから助けたら、なぜかクラス委員を一緒にやることになった件」を読了。こんなタイトルをしていて、実は主人公は勇者として異世界を救った帰りという設定。異世界で手に入れたスキルやコミュ力で青春を無双する話は好みだと思って読んだ。しかし微妙だった。主人公が目立つという好みのシーンはちゃんと用意されていたが、そういう加点要素より主人公のセリフ回しとか陰キャ時代の唯一の友達が登場だけしてほとんどクローズアップされなかったところとか、減点要素が大きいと感じてしまった。

AGCがあまりにも不完全燃焼だったので、出る予定のなかったJOI本選のオープンコンテストに午前3時から4時間で参加した。

第22回日本情報オリンピック本選オンラインコンテスト

このコンテストの言及解禁は月曜日の午後7時だが、それまでに週記は投稿できないだろうからここに全部書いておく。結果をまとめておくと、1・2・4問目が満点、3問目が86点、5問目が62点で合計448点だった。

1問目は同じ色の連続する碁石をまとめて保存しておくとよい。色を表す数値が過剰に大きいのは嫌がらせ要素か。

2問目は結構難しかったし結局よくわからないまま通した。住人 $i$ が本を手に入れれば住人 $j$ も買う、という関係を $i\rightarrow j$ と書く。各 $j$ について $i\rightarrow j$ を満たす $i$ のうち数直線上で最も近い $i$ を左右それぞれ探して実際に $i\rightarrow j$ の辺を張り、そうして作った有向グラフをSCCして入次数が0の強連結成分数を答えたら通った。

なぜ上のような辺だけしか考えなくてよかったのかはよくわからない。左右それぞれ辺が存在するならそのうち1本張られていれば十分だったのかもしれないと考えている。

3問目は謎。ハンコを押す度、それによって白く塗られたマスのうちまだ訪れていないマスのみを高速に列挙できれば解ける。

例えばこれは矩形領域三つの和だから、2次元累積和を使うとある程度まとめて $O(RC)$ で求まる。BFSするのとハンコを1回押すのを答えが見つかるまで交互に繰り返すと、毎回の計算量が $O(RC)$ で、答えの最大値が $O(C/N)$ となるから計算量は $O(RC^2/N)$ 。

あるいは行方向だけ全列挙して列方向はsetなりbitsetなりを使うとよいかもしれない。1マス当たり $O(N)$ 行見る必要があるので $O(RCN)$ と見積もった。正確にはマス目の探索でもっとかかりそうだがよくわからない。

この時点で $O(\min(RC^2/N,RCN))$ が達成できたと考えた。 $N\le R\le C$ なので実は $O(RC^{3/2})$ ではなく $O(RC^{4/3})$ になっているはず。ギリギリ間に合うと信じて提出したら小課題6以降が通らず67点だった。5問目まで取り組んだ後戻ってきて格闘したら小課題6は何とか通ったが、それで終わりだった。

4問目は簡単だった。最も高いタワーに障害物を置くと、そのタワーを取り除いた後の連結成分のどれかに移動し、以降はその連結成分内でしか動けない。だから逆に、タワーの高さの昇順に見て行って連結成分をマージしながら解くことができる。

マージの際、移動する連結成分は全探索できる。そして連結成分の中で次に移動するのは最も高いタワーだとしても損しない。そのタワーに移動しないようにするためには障害物を置いておく必要があり、以降の動きは一度訪れてからでも全く同じことができる。

UFで連結成分と同時に最も高いタワーを管理し、dpした。木の上の距離を $O(N)$ 回求める必要があるので、LCAを使って毎回 $O(\log N)$ かけて処理した。

5問目はさすがに難しくてほとんど何もわからなかった。実験するとスタート位置の左にあるRと右にあるBの個数が重要で、ボールが取り除かれた後は適当な範囲が一気にRまたはBになっていると分かった。つまり区間に対するR・Bのカウントと、それを見て二分探索で求めた区間への一様な代入でボタンを押すシミュレーションが書ける。遅延セグ木で $O(QM\log N)$ となり、小課題3まで通る。

小課題4と5は全く別方針。この二つはどちらも $C$ の左からいくつかがR、残りがBという形をしている。こういう分割はどこにボールを置いたとしてもずっと成り立ち続けるようだ。境目を問題文と同様 $t$ とし丁寧に実験してみると、タイル $A$ の上にボールが置かれたとして、 $t\lt A$ なら $t\leftarrow(t+A+1)\bmod{(N+1)}$ 、 $t\ge A$ なら $t\leftarrow(t+A)\bmod{(N+1)}$ となると分かった。

平方分割してブロックごとに $t$ の変化を全通り求めておくことにした。この計算は $t$ を $O(N)$ 通り試さないといけないように見えるが、ある区間に対しては常に全く同じ増分となるため、その区間を検出しながら繰り返すことでそこそこ高速に全て求まる。ブロックサイズを $B$ とすれば区間はおそらく $O(B)$ 個となるはず。よって前計算 $O(M/B\times(B^2+N))$ 、クエリ当たり $O(B+M/B)$ で答えが出る。