週記（2023/08/07-2023/08/13）

月曜日から水曜日まで、COSS2023参加のため京都にいた。この期間の日記は参加記として切り出される可能性がある。

COSS2023 Home

08/07(月)

セミがうるさすぎて目を覚ました。時刻を確認したら午前5時だったので二度寝。次は午前8時半に起き、ホスフィンと合流して昨日買っておいてもらったパンを食べた。

出発は午前9時半。ホテルから一歩出たらとんでもない音量のセミの鳴き声が叩きつけられて辟易した。河原町三条から市バスの17号系統に乗り、京大農学部前ではなくその次の北白川で降りた。ホスフィン曰くここのほうが近いらしい。午前10時半から講義開始。実は今日提出の期末レポートが終わっていないので、問題をググって解きながら聞いていた。

初日はポピュラーマッチング。ちょうどDiestelのセミナーで安定マッチングについて学んだところだったのでかなりタイムリーな話題。前半は綺麗な結果にわかりやすい証明がついていて楽しかった。補題1、2の証明が時間の関係で飛ばされたからそう思えるのかもしれないが。

昼食は東北大学から来た自分、ホスフィン、sotanishyさんに加えolpheさん、tatyamさん、tokusakuraiさんの6人で華祥という中華料理の店に入った。数理解析研究所から微妙に遠く、また料理が出てくるのも少し遅かったので昼休みを微妙にオーバーしてしまった。

講義後半、だんだん苦しくなってきた。ゼロサムゲームや混合戦略という用語が出てきて去年受けたゲーム理論の講義を思い出した。適当に選んだ講義だったが無駄にはならないものなのだなあと感動。演習問題は3まで解けて、4は解けたと思い込み、5は答えだけ出して説明ができず、6はホスフィンが構築したのを聞いた。

演習問題4の発表を聞いていたらいきなり双対を取っていてびっくりした。改めて自分のLの\mathrm{argmax}やRの\mathrm{argmin}を取ってもう一方に適用するという解法をチェックしたらL\le Rしか示せていなかった。

演習問題5を発表する人がいないようだったので、先生が解答を述べようとするところに割り込んで自分の考えた答えを述べた。正解だった。各辺の寄与を考えればよいので正しい答えにたどり着くだけなら難しくないと思っているが、正確に説明することはできない。その部分は先生に引き取っていただいた。ゴリゴリ式変形しておりこれを詰め切るのはちょっと……という気持ちになった。

終了後、学食に移動して懇親会（正確名称は意見交換会）に参加した。最初はレポートを書いていたが1時間くらいで終わったので残りはちゃんと懇親をした。ほぼ競プロerと喋っていて、自分がYouTubeに上げているコンテスト実況の話も何度か出た。後ろの方の問題に取り組んでいるシーンをたまに見るらしい。そのあたりは黙り込んで考察している時間が非常に長いため誰も見ていないだろうと考えていたからびっくりした。ありがたい限りだ。

午後8時に解散した後二次会に行った。囀という焼き鳥の店で、メンバーは東北勢3人に加えY.Y.さん、optさん、tatyamさん、おてらさん、りきぽんさん。競プロerだらけだがそこはCOSSらしく研究や進路の話が印象に残っている。後は少しだけPCを開いて期末レポートの見直しと提出もした。

会計はいつの間にかY.Y.さんに全額出してもらっていた。ありがとうございました。

地下鉄に乗ってホテルに帰ってきたら午後11時を回っていた。少しだけ週記を書き進めて、日曜日が丸々空いたまま投稿。半からCF #891 div.3に出た。

Dashboard - Codeforces Round 891 (Div. 3) - Codeforces

Aは総和が奇数なら不可能、偶数なら一つと残りでよいので可能。Bは下の桁から見て5以上なら一つ上の位に1足すという操作を繰り返し、最後に行われた操作より右の桁を0に揃える。最上位桁に0を追加しておくと楽。Cはaの最小値から決めていくと一意。Dは辺u\rightarrow vの条件がa_u-b_u\ge a_v-b_vなので、a-bの最大値を達成する頂点たちが答えになる。

Eはsに対して区間[s,x]の長さの総和を求めればよい。x\lt sとs\le xに分ければ、あとは累積和を使ったりして計算できる。Fは解と係数の関係でa_i、a_jの値が具体的に決定できる。Gは追加したすべての辺について対応する全域木のパスに含まれる辺の重みの最大値が自分未満である必要がある。辺の重みが軽いほうからUFでマージしていくと、その重みが「辺の重みの最大値」になるパスの本数を数え上げることができて解ける。

40分弱で全完して17位。

シャワーを浴びて一瞬インターンの作業をした。以下の件で対応が決まったので、それを実行した。どちらも手順はわかっているので出先でも問題なく行える。

インスタンスのスペックを上げるかバージョンを下げるかは使う人の判断に委ねることに。

週記（2023/07/31-2023/08/06） - kotatsugameの日記

日記を書いて午前2時前に寝た。

08/08(火)

午前7時半起床。昨日はパンを買えなかったのでフロントで近い店を聞いて買ってきた。この時間からでも空いているパン屋があるのは助かる。ホスフィンと合流し、食べて午前9時出発。昨日と全く同じルートで会場に到着し、午前10時から講義開始した。

書く：2日目前半

昼食は東北勢、olpheさん、tatyamさん、みやもりさんの6人でジェイムスキッチンに行った。自分はハンバーグのMサイズとライスのLサイズを頼んだが、漫画みたいな大盛りのライスが出てきてビビった。なんとか完食。このサイズで1000円を切っているのはかなり安いと感じる。いわゆる学生街だろうか。東北大学の川内キャンパスや青葉山キャンパスの周りには何もないので、そういう文化はフィクションだと思っていた。

書く：2日目後半

2日目終了後は大文字山に登るのが毎年恒例らしいが、自分は疲れ果てているのでパス。それに挑む人々を見送った後、残っていた自分、ホスフィン、tatyamさん、みやもりさん、T.S.さんというメンバーで飲み会に行きそうな集団についていった。しかし人数まで決めて店の予約を取っておられたらしく合流に失敗。年齢層が高く教員方の集まりに見えたのでむしろお邪魔しなくて正解だったかもしれない。代わりに京都観光に繰り出した。

ホテルに二条城で行われているイベントのチラシがあったのでそれに行ってみた。当日券1600円を買って入ったが、ちょうど今本丸御殿を修理しているらしく二条城観光としては非常に物足りない。夕方のまだ明るい時間だったのでライトアップも微妙。暗くなるまで粘ったらプロジェクションマッピングはそれなりに見れるものになった。

event.naked.works

夕食はかつくらというとんかつの店。閉店ギリギリに滑り込んだ。

食後は解散し、tatyamさんとゲーセンに行って1時間ちょっとチュウニズムでマッチングをした。曲の解禁が全然追いついておらずプレイできる譜面にあれこれ注文を付けることになってしまったのが申し訳ない。戦犯も多かったが何とかフルチェインが二つ出た。

午後11時くらいにホテル着。シャワーを浴びてしばらくTLを眺め、午前0時半には寝た。

08/09(水)

午前8時起床。ホスフィンと合流し、今日はホスフィンに買ってきてもらったパンを食べた。あとは昨日と同じスケジュールで、午前10時から講義開始。

書く：3日目前半

昼食は東北勢、olpheさん、tatyamさんでヒトデマンからお勧めされたマハカレーというカレー屋に行った。チーズナンが美味しいという話だったのでそれを注文。実はチーズはあまり食べないのだが、このチーズナンはかなり甘くてチーズっぽさが全然なく、自分でも美味しく食べることができた。しかしサラダで満腹になっていたため少しホスフィンに押し付けてしまった。

書く：3日目後半

終了後はホスフィン、tokusakuraiさん、りきぽんさん、T.S.さんとバスに乗って京都駅まで向かい、カフェでケーキを食べた。

午後7時過ぎの新幹線に乗って帰路に就いた。東京までは寝ていて、乗り換えてからはなろうを読んでいたはず。仙台駅前で立ち食いそばを食べて日付が変わったくらいに帰宅。すぐシャワーを浴びて4日分の着替えを洗濯した。

TLで流れてきた「【転生掲示板】何らかの漫画世界に転生ワイ、作品が特定できず詰む」を読了。短編。流れも面白いしオチも面白い。作品特定の難しさと博覧強記な主人公がちょうどいいバランスだった。

syosetu.org

午前2時半就寝。

08/10(木)

午前6時半に目を覚ました。二度寝できずカクヨムから「【悲報】オレ氏、人類の敵かもしれない」を読了。リアルのパートがほとんどなく完結までずっとソロでダンジョン攻略を繰り返しており、硬派で良かった。

kakuyomu.jp

その後は寝たりハーメルンを読んだりしながら午後2時半くらいまで横になっていた。いい加減に布団から出て帰省の準備を整る。持ち物は昨日まで京都に行っていたときと大して変わらないからすぐ完了し、出発。

連休前日の昼過ぎということもあり仙台駅は大変混雑していたが、食事時から外れていたのでレストランは空いていた。蕎麦を食べてお土産を買い、新幹線に乗った。

大宮までは読書、大宮からはハーメルン。「【悪役✕結婚】怠惰な悪役貴族の俺に、婚約破棄された悪役令嬢が嫁いだら最凶の夫婦になりました」を読了した。微妙。主人公もヒロインもそこまで好きになれなかったが、スルスル読めてまんまと最新話まで到達してしまった。

syosetu.org

富山駅からは父親の車に乗り、8時過ぎに実家に到着。今日の富山県はフェーン現象で猛烈な暑さだったらしい。それが残っていたのか知らないが、2階にある自室の気温は38.3度を記録していた。当然仙台より暑いし、何なら今週前半京都にいた間は天気が悪くそこまで暑くならなかったので、それよりも暑い。

夕食と入浴を済ませた後は本を読んだりなろうを読んだりしていた。午前1時就寝。

08/11(金)

午前9時半起床。朝食を摂って、午前中は本を読んでいた。

「ノッキンオン・ロックドドア」2巻を読了。久しぶりにミステリを読んだ。面白かった。短編なので解決編を読んだときすぐどこにあった手がかりなのか思い出せる。ものによっては読んでいるときに違和感があったことを覚えていて、ああここが伏線だったんだなあと惜しい気持ちになった。まあそこから真相まではかなり遠かったのだが。その遠さはつまり意外さで、それがたっぷり詰まった謎がたくさん収録されていた。

正午からAHC022が始まった。とりあえず問題を読んで提出だけしておいた。

RECRUIT Nihonbashi Half Marathon 2023 Summer（AtCoder Heuristic Contest 022） - AtCoder

昼食を摂った後、第四回日本最強プログラマー学生選手権決勝のホテルを予約した。会場は港区と書いてあったから金持ちのイメージでホテルも高いだろうと思っていたが、全然そういうことはない。トヨタコンで泊まった渋谷近辺と比べると一回りも二回りも下だった。後泊するので週末、しかも朝食付きで探しても渋谷で素泊まりするより安上がりなのではないだろうか。その条件でいい感じに近いホテルを選んだ。

午後4時過ぎに墓参りに行った。この時間でもうだるような暑さ。雲一つない青空がいいなと思って写真を撮った。違う方向を見れば立山連峰が聳え立っていて、そういう3000m級の山々がいつでも視界にある風景は富山ならではだったのだなと仙台に出てきてから考えている。そちらに向かって撮ればよかったなとちょっと後悔。

帰宅してからは読書を続けていた。夜になって夕食・入浴を済ませ、午後9時20分からyukicoder 401に参加した。

yukicoder contest 401 - yukicoder

Aはよい。Bは魚ごとに一番近い湖まで動かすか考える。Cは最後に追放されたのが人間か狼かわかるので、それを固定して残りは適当に場合の数を計算する。Dは手で実験したところ3のべき乗を並べるのがよさそうだった。限られた個数の重りと天秤でいろんな重さを量る話を思い出せば納得できる。

Eは、反転する・しないに関わらずR回目の移動後には同じマスにいなければならないことを考えると、[L,R]回目の移動ではLRまたはUDを繰り返すのが最適だとわかる。そのような動きが可能なマスにL-1回でたどり着けるか、またそこから残りK-R回でゴールに行けるかチェックし、頑張って復元。チェックは最短距離を求めてその偶奇があっているかを見ればよい。

Fは(4,3)と(3,4)にトゲを配置すれば達成できるので答えが1以下かを判定すればよい。まず、BFSなりをすることでO(HW)かけて答えが0かチェックできる。さらに今HW\le 2400なので、1マスにトゲを配置して先ほどのチェックをするということを繰り返せば答えが1かも判定できる。

Gは解けず、6完11位。解説を見たらかなり近いところまで考察できていたらしい。そこからうっかり別方針に執着してしまったというわけ。upsolveした。

ある数が99の倍数であるということは、9の倍数かつ11の倍数であるということである。9の倍数の判定は桁和が9の倍数か見ればよい。11の倍数の判定は偶数桁の桁和と奇数桁の桁和が\bmod{11}で等しいかをチェックする。いずれにしても桁和が重要で、求める値もそのK乗だから、d(x)に対してxを数え上げられないと解けなさそうという感じがする。

そしてそれは実際に可能である。偶数桁と奇数桁に分割し、まずそれぞれで桁和に対しそれを達成する数を数え上げてみる。これは多項式のべき乗でOK。その後桁和\bmod{11}で分類し、偶数桁と奇数桁でマージする。ここも多項式の積になっている。これで11の倍数に対する桁和の分布が求まったので、9の倍数だけ取り出してd(x)^Kを足し合わせればよい。

日付が変わったくらいに布団に入り、そこから3時間ほどハーメルンを読んで就寝。

08/12(土)

午前8時半起床。朝食を摂って二度寝に入り、次は正午に起きた。

車に乗って有名なそうめんの店に行った。炎天下で並ぶのは大変。雨傘を日傘の代わりにしたがないよりは百倍マシである。

帰宅してからは日記を書いていた。夕方から1時間ほど寝て、夕食・入浴・洗濯を済ませ、午後9時からABC314に参加した。

AtCoder Beginner Contest 314 - AtCoder

書く：ABC

午後11時半からはCF #892 div.2。

Dashboard - Codeforces Round 892 (Div. 2) - Codeforces

Aはaの最大値をcに、残りをbに入れるとよい。これでbが空になるならaの値はすべて等しいからどうやっても不可能。Bは各列の最小値をどこかにまとめるべき。まとめた列以外の列は2番目に小さな値だけ寄与するから、それが最小になる列を目掛けてまとめるのが最適となる。

Cは実験したら1,2,\dots,k,n,n-1,\dots,k+1となっていたのでkを全探索した。Dは区間[l,b]からbにテレポートできると限定してよい。あとは何をやってもできそうだがうまい実装方針が思いつかない。座圧し、右から順にどこまでテレポートで飛べるか計算していった。

Eは難しかったが解法はシンプル。|x|=\max(x,-x)を使ってスコアを分解すると四つの式が出てくる。このうちの最大値を使うのではなくどれを選んでもよいと読み替えれば4種類の遷移ができるが、そのコストたちはlとrに分解できるので、適当に累積MAXを取りながらdpを計算していくことができる。dpの状態として「区間の長さ」ではなく「区間外の長さ」を持つと遷移が単純になって便利。実は四つの式のうち二つは長さ1の区間としてしか現れないことが言えるものの、そこまでする必要はなかったようだ。

Fは解けず、5完19位。

しばらく日記を書いて午前3時就寝。

08/13(日)

午前8時半から午前10時まで起きてハーメルンを読んでいた。無事二度寝に成功し、次は午後0時半に起床。

昼食を摂った後、父が新調したPCでメールソフトの設定やプリンタのドライバーのインストールなどをしていた。その前の段階、つまり最初にPCを起動してからのWindowsに関する諸設定は3万円で店にやってもらったらしい。多分自分でもできたと思うから、実際どのくらいが手間賃なのかわからないが惜しいな……と思った。

荷物をまとめて午後3時に実家から出発。車で富山駅に送ってもらった。ちょうど新幹線がない時刻に着いたようで、来た時あれだけ混んでいた駐車場に今日はすんなり入ることができた。時間があったので少し富山土産を買ってもらった。

午後4時過ぎの新幹線に乗り込む。繁忙期の臨時列車らしく、かがやきより多くはくたかより遥かに少ない停車駅、かつ上野止まりといういろいろ特別な運行だった。車内では大宮以前も以後もずっと本を読んでいた。仙台駅に着いて立ち食いそばを食べ、午後8時帰宅。

シャワーを浴びてから、読んでいた本が残り数ページだったので読み切った。「叫びと祈り」。連作短編集で、特に一つ目の「砂漠を走る船の道」が最高だった。ストーリーにも謎にも異国情緒が溢れており、そこに仕掛けられたミスリードがピリリと効いてかなり強烈な読み味。同様のことが、程度の違いこそあれ他の短編にも言える。

解説を読んで知ったが、この作者は「放課後探偵団」というミステリアンソロジーに短編を1本書いていたらしい。何分読んだのが4年近く前ということもあって、タイトルを聞いても内容が全く思い出せない。実家に置いてある本なので確認することもできず残念。読み終えるのが少し遅かった……。

午後9時からAGC064に出た。

AtCoder Grand Contest 064 - AtCoder

Aは手作業。[5 4 [3 2 [1] 2 3 2 3] 4 5 4 5 4 5]と並べていくと大体いい感じになって、余っている要素を[や]のところに差し込んでいけばよい。このままだと両端の値が等しくなってしまうので、どちらか片方を取り除いて余った要素と同様に処理。ちゃんと差し込む位置は残っている。全ケースについて正しく構築できることをチェックし、提出した。問題なくAC。

Bは両端点に関する条件を一度に満たせる辺は貪欲に使っても良いだろうというのが最初のステップ。そうやってすでに条件を満たした頂点とまだ満たしていない辺を結ぶ頂点を辺で結ぶことで、条件を満たした頂点を増やしていく。まだ条件を満たしていない辺は常に孤立点だからループを考えず貪欲に増やしていける。BFSで実装すればよい。

この方法で条件を満たせれば、あとは全域木になるように適当に辺を追加すればよい。ダメだった場合は実は答えもNoとなる。なぜなら最初のステップを終えた後は1本の辺で高々一つの頂点の条件しか満たせないという状況になっており、孤立点だけを結ぶ木を作ると必ず一つ以上の頂点が条件を満たせないまま取り残されてしまうからだ。

順位表を見るとすでにDにACが出ていたため、そちらに進んだ。まず末尾のBのすぐ左にあるRは無視してもよい。これを繰り返すことでSの末尾をB2文字にできる。ここからR*BB、BR*BB、RBR*BBで実験してみた。特に後ろ二つの比較から先頭にRを1文字足すのがどこに効いてくるかをチェックするといい感じの方針が立った。正直、以降は公式解説と同じである。

数え上げる対象の列をBとその後ろ（下）に続くRへと分解する。先頭にあるRたちと末尾にあるBは無視。するとそれぞれのBが引き連れているRの個数の列からチップの列が復元できるので、以降はRの個数の列を数え上げればよい。先ほどの比較で気づいたのは、このRの個数は対応するBより左にあるRの個数以下になっている必要があるということだった。

より正確に述べれば、Sの先頭にあるBから順にどれだけの個数のRを引き連れるか決定する際、それは自分より左に「残っている」Rの個数以下でなければならず、またその個数分残っていたRを消費するということになる。

あとはそうやって決めたRの個数が列の中でどこに位置するかということを決めなければならないが、これは何でもよいと信じることにした。つまりBは（Nマス目にあった1枚を除き）どんな順番にでも積み重ねられるとした。

ここまで決めるとdpが書ける。Rの個数の列を決めたとき、Sの先頭にあるBから順に小さい要素を対応させていくのがよいから、「これまでいくつBを使ったか」「これまでいくつRを使ったか」を状態に持つ。列の数え上げは多項係数になるから、要素は小さいものから順に同じ値になるものを一気に決めていく必要がある。

状態数も遷移もO(N^2)に見えたが、ランダムケースが十分高速だったので出した。WAが出たので愚直と比較し、修正して2回目の提出でAC。実行時間は問題にならなかった。

この時点で1ページ目にいたため勝ったな……！という気持ちになりつつ、C問題に臨んだ。まずは操作の観察。区間[l,r)があったとき、操作後も区間のままで、具体的には[\lfloor(l+c)/2\rfloor,\lfloor(r+c)/2\rfloor)になるようだ。ここでcは偶数を削除した場合0、奇数を削除した場合1となる変数。

k回の操作が行われ、それぞれc_1\dots c_kが選ばれた場合を考える。このとき区間がどうなっているかをかなりシンプルに記述することができた。C=c_k c_{k-1}\dots c_1を2進数で解釈した数値としたとき、[l,r)\mapsto[\lfloor(l+C)/2^k\rfloor,\lfloor(r+C)/2^k\rfloor)となる。

もともと区間の端点は\lfloor l/2^k\rfloorか\lceil l/2^k\rceilの2通りしかなかったが、このように記述できるとさらにCが2^k-(l\bmod{2^k})未満か以上かで分類できるとわかる。そのように分類されるなら、N個の区間を全部見た時のバリエーションもO(N)個になりそう。

実験で確かめられたのでメモ化再帰を書いた。最初は単純に区間を全部キーにしていたが、これは手元で2secを微妙に超える。さすがに怖いのでhashを使うことに。以下の記事中にあったコードを少し改変してvector<pair<long,long> >のhashを求めて使ったら手元で1.6secくらいになった。提出したら756msでAC。ちなみに後から区間を全部キーにするものを出してみたら1053msだった。

俺のunordered_mapがこんなにpair型をキーにできないわけがない - Qiita

残り20分はEとFを読んだだけで終了。4完14位でパフォーマンス3444、レートは2839→2916(+77)となった。パフォーマンスもレートもhighestである。

www.youtube.com

しばらくTLを眺め、午前3時半就寝。