12/05(月)

午後4時半前に起床。

先週水曜日に出たDMOJのコンテストの期間が終了していた。順位表での並びは全完した6人中4人目になっている。どういう順序か知らないが十中八九速度順だろう。3問目で手間取ったのが痛かったか、あるいはそれどころではない差がついているのか。いずれにせよ、勝てるかなと期待していたのでちょっと悔しい。

COCI '22 Contest 1 Unofficial Mirror - DMOJ: Modern Online Judge

起きてすぐインターン先定例会。先週金曜日の1on1の時点で何も用意できていなかった状況は今も変わらない。今週は何かやりますと言って終了した。実は1on1のときにタスクが変更されていて、少し手を付けやすくなった感じがするから、さすがに何かしら進められるだろうという見込みがある。

今週の勉強会は、先週から言っていたように自分の発表。内容はアスキーアートQuineについて。午後5時半から1時間発表、1時間質疑応答だった。何かコメントを頂いたら同じくらい喋りたくなってしまい、結果質疑応答にこうも時間がかかった。

いつものようにスライドを公開しておく。

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

ABC279の賞品が届いていた。学生3位に全体での賞も合わせ、アマギフ6万円ぶん。これで貯め込んだ残高が50万円を突破した。賞金付きABCが多くて本当にありがたい。

Gまでの7完最速で9位。上に日本人学生が少なかったので賞金額が思ったより高そう。
週記（2022/11/21-2022/11/27） - kotatsugameの日記

それから週記を書いて午後10時前に投稿。校閲ができていない状態がもはやいつものことになってしまっている。その後すぐTROC #29に出た。もともとAGCと被っていたのがギリギリになって1日ずれた。

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

Aはよい。

Bはどの順番で回っても偶奇が一意になるタイプの問題だと思ったがWA。ちゃんと考察すると、 $X_i\bmod 2$ と $Y_i\bmod 2$ が一致するか異なるかでグループ分けしたとき、各グループが空でないことが必要十分条件になっていた。グループ内の移動は距離の和の偶奇を変えないため。

Cは手でいくつか試すと、一要素に $\pm 2$ したり全要素に $\pm 1$ したりがコスト0で行えるので、最後にコスト1の操作で高々1回調整するだけになる。

Dは2べきから1引いた数に揃えたい。よって $2^k\le N$ なる最大の $k$ を取り、 $2^k,2^k+1,\dots,N$ を $2^k-1,2^k-2,\dots$ と対応付けた後、残った数の最大値を新たに $N$ として計算するのが良い。オーバーフローで1WA。

Eは面白かった。直感として最大値 $M$ とそれ以外に分けたくなって、このとき達成される値が $M+1$ 以上。さて、特に制限なくグループ分けして $C_1$ 、 $C_2$ ができ、 $C_1+C_2\gt M+1$ となったとしよう。一般性を失わず $C_1\gt (M+1)/2$ としてよい。

最初のグループに割り当てられた数はすべて $C_1$ の倍数だが、 $2C_1\gt M$ よりそのような数で $M$ 以下のものは $C_1$ ただ一つしかない。さらに $A$ の要素が相異なるという条件から、最初のグループに割り当てられた数がその $C_1$ ちょうど一つだけだったことがわかる。あとはそれを全探索すれば解ける。

Fはよくわからない。できるだけ大きな素因数で割れば操作回数は多くなるが、その分相手も多く操作できるようになってしまう。そこで、相手が操作できないピースは大きな素因数で、操作できるピースは小さな素因数で割ることにして、メモ化再帰でそれっぽく操作回数を数え、比較してみた。出したら通ってびっくり。

Gは頂点1を含まないグループのサイズに対して分け方が高々一意。うまく分けられるサイズを木dpとマージテクで列挙した。各サイズに対し、そのグループをこれまでいくつ作ったかもカウントしておく。部分木のサイズを $s$ とし、その約数 $d$ について、サイズ $d$ のグループをこれまで $s/d-1$ 個作れていれば新たにもう一個作れる。それより多いことはなく、少なければ破綻しているので削除。TL 3secのところ2.3secで通った。

Hは気合い。 $i\rightarrow P_i$ という順で並べたサイクルを極大な単調減少列に分解し、それぞれの長さを2で割って切り捨てた値の和が答えになる。各単調減少列を区間を管理する要領で持てば1点更新にも対応できる。サイクルを切り開いて持つので端の処理が大変なことになりそうだったが、切り開いた後3倍にして真ん中の部分だけ見ることで解決した。

全完7位で2762→2786(+24)、highest。Fの解説には全然違うことが書いてあった。Gはグループのサイズ $d$ を決め打つと、部分木のサイズがその倍数であるような頂点が、根以外に $\lceil N/d\rceil-1=\lfloor(N-1)/d\rfloor$ 個あればよいらしい。

レートのランキングで5位になった。

インドネシアで5位です pic.twitter.com/PgnAqXZ0Pc
— こたつがめ (@kotatsugame_t) 2022年12月5日

Advent Calendar Contestの5問目を通した。色のほうでカードをまとめていくつか場合分けする。こういうタイプの問題が一発で通せたのはうれしい。

#822812 (C++14) No.2148 ひとりUNO - yukicoder

セミナー準備を始めた。先週準備したぶんの続きからだが、軽めの定理を一つ示すともうその章は終わり。その後次の章に進むのではなく、floor_sumを解説する準備を始めた。ピックの定理と競プロの関連でこういう方法があるというのを先生にお話ししてみたら、興味を持たれたらしく、次回のセミナーで話すよう言われていた。

どちらの内容も準備はすぐできて、午前2時に終了。しばらくYouTubeを見た後シャワーを浴び、ゴミを出して午前4時に布団に入った。そこからハーメルンを読んで午前5時半就寝。

12/06(火)

午前9時40分くらいに起きた。

TLに雪というワードが流れてきて一気に目が覚めた。窓の外を見ると、確かに多少降っている。ただ天気予報によれば朝のうちに止むようだし、積もっているというわけでもなかったので、今日も原付で山に登った。

午前10時を少し過ぎたあたりで教室に到着。今日も遅刻してしまったなと思っていたら、先生も少し遅れていたらしい。待つ間に生協に走ってパンを買い、腹ごしらえをした。

午前10時半からセミナー開始。最初2時間は同級生の発表だった。ここ2週間ほど議論の不備が指摘されて示せていなかった命題が、帰納法の仮定を強めることでヌルっと示せてびっくりした。

それから1時間は昼休み。生協で買ったパンやおにぎりを食べた後はハーメルンを読んでいた。

その後自分の発表。教科書の準備してきた部分は1時間半ほどで話し終わり、まだ時間に余裕があったのでfloor_sumを解説していた。式変形については納得してもらえたものと思うが、計算量を解析して高速化になっていることを確かめる部分は微妙そうだった。手で計算しようとすると繰り返しが少ない分変形が面倒になっているので、理論的な説明をするしかなく、本当に速いということを実感してもらうのは難しい。

ゼミでfloor_sumの話した（1年ぶり2回目） pic.twitter.com/GdKgXccWjW
— こたつがめ (@kotatsugame_t) 2022年12月6日

終わったのが午後4時で、それから揃って建物を移動し講演会に出席した。行列式点過程とやらの話。詳しい説明はされなかったので結局よくわからないままだが、グラフの全域木にも何か関係があるらしい。行列式と全域木と言えば行列木定理で、ちょっと聞いてみたところ見事にそれ由来だった。行列式で書けるから数え上げられるというだけでなく、このように派生することもあるのかとびっくりした。

終了後、同級生と先生と学食で食事しつつ、講演会で言及された定理について話していた。 $N\times N$ の行列 $L$ について、 $|L+E|=\sum_{X\subseteq\{1,\dots,N\}}|L_X|$ というもの。ここで $L_X$ とは $L$ から $X$ に属する行・列のみを取り出した行列で、 $|L_{\emptyset}|=1$ とする。

行列式の定義から式変形したら、特別な定理なしに示すことができた。クロネッカーのデルタを用いると $(L+E)_{i,j}=L_{i,j}+\delta_{i,j}$ と書けるので、 $|L+E|=\sum_{\sigma}{\rm sgn}(\sigma)\prod_{i=1}^N(L_{i,\sigma_i}+\delta_{i,\sigma_i})$ となる。ここで $\sigma$ は長さ $N$ の順列全体を渡る。

積を分解すると $\prod_{i=1}^N(L_{i,\sigma_i}+\delta_{i,\sigma_i})=\sum_{X\subseteq\{1,\dots,N\}}\left(\prod_{i\in X}L_{i,\sigma_i}\prod_{i\notin X}\delta_{i,\sigma_i}\right)$ となる。ここで二つの $\sum$ を入れ替え、 $\prod_{i\notin X}\delta_{i,\sigma_i}=1$ なるケースのみを考えることで、 $|L+E|=\sum_{X\subseteq\{1,\dots,N\}}\sum_{\sigma\;s.t.\;\forall i\notin X.\sigma_i=i}{\rm sgn}(\sigma)\prod_{i\in X}L_{i,\sigma_i}$ と書ける。

内側の $\sigma$ は $X$ 以外の添え字で値が変わらないので、 $X$ の順列だと思ってもよい。このとき ${\rm sgn}(\sigma)$ が変化しないことが確かめられる。したがって $X=\emptyset$ の場合も含め $\sum_{\sigma\;s.t.\;\forall i\notin X.\sigma_i=i}{\rm sgn}(\sigma)\prod_{i\in X}L_{i,\sigma_i}=|L_X|$ と書ける。証明終。

和の取り方を入れ替えたり、 ${\rm sgn}(\sigma)$ の議論で転倒数を考えたりと競プロチックで楽しかった。特に前者については、セミナーにおけるfloor_sumの説明でも使ったテクニックなので、良いタイミングだったなと感じた。

来週のセミナーについても話した。再来週は自分が集中講義のため参加できない。よって来週が年内最後になりそうで、2回行うことになった。今のところ火・木の予定。

解散して午後8時前に帰宅。ちょうどJOI一次予選（第3回）の問題が公開されたので急いで解いた。

JOI 2022/2023 一次予選 (第3回) 過去問 - AtCoder

AはdcでもVimでも4Bで、30秒ほど負け。Bは $\left\lfloor\sqrt{\lfloor 30/(A+7B)\rfloor}\right\rfloor$ を出力したら通った。Cはsed。DはOctaveで自分より小さな値を数えた。今のところA以外の最短を取れている。

午後9時に再度外出し、ゲーセンに向かった。チュウニズムのグッズキャンペーン用のポイントを稼ぎに行く。

チュウニズムのグッズキャンペーン的には12/07までにあと13回プレイする必要がある。
週記（2022/11/28-2022/12/04） - kotatsugameの日記

ゲーセンに到着した時点で閉店まで2時間ほどしかなかったため、理論値を狙いつつ大量に捨てゲーして無理やり間に合わせた。結果的に今日は15クレプレイできた。一方理論値は一つしか出ていない。手元動画を八つほど撮った。以下のリプライツリーに連なっている。

Armageddon 15-1-0 手元 pic.twitter.com/VsNEDko17A
— こたつがめ (@kotatsugame_t) 2022年12月6日

立ち食いそばを食べ日付が変わったあたりで帰宅。動画をツイートした後は疲れ果てて長い間YouTubeを眺めていた。

シャワーを浴びて布団に入り、ハーメルンを読んだ。1作読了。「めしくい・ざ・ろっく！」。半同棲の設定が良い。主人公は単なるぼっちではないらしく、その点について自己評価と他者からの見られ方に結構違いがあるのも良かった。「ひとり」や「ふたり」を人名だと認識するのが少し難しかった。

syosetu.org

午前6時前に就寝。

12/07(水)

午後5時に目を覚ました。ちょうどCFで5hが始まる時間だったが、今日が提出期限のレポートがあるため見送った。そのレポートのため布団で講義資料を読んでいたら、午後7時前に寝落ちしたらしい。

起きたら午後9時半になっていた。布団から脱出してレポートに取り掛かる。生命情報システム科学の課題で、これまで2回ほど提出したが毎回非常に苦しみながら捻り出している。そのくせ単位を取得しても修了要件には含められないらしい。そういう理由からやる気が全然出なくて、1時間ほどYouTubeを見てしまった。

それから一念発起してそれっぽいものを生成しはじめたら、無事日付が変わる前に提出できた。今回も出来は悪い。

解放感を感じつつハーメルンを読んでいた。午前3時に1作読了。

syosetu.org

「TS逆行したら才能に満ち溢れてた」。逆行転生して配信者になる話で、まず設定が好き。展開も非常に順調で良かった。

1点、4歳でIMO代表になるという話において「前世で博士課程後期だったからこのくらいは」みたいなことが書かれていたのが気になる。数オリと博士課程後期、それも物理だと能力的に全くの無関係に見えるし、「数オリ専用の知識が必要」と書いてあるのでそのことは作者もわかっているものと思う。主人公は前世から非常に頭が良かったらしいので、そう書いておくだけで良かったのではと考えてしまう。

別の講義のスライドを読み始めた。スライド中にいくつか問題があって、それらから三つ選んで年度末にレポートとして提出するタイプ。この講義の単位はちゃんと修了要件に含められるためしっかり取っておきたくて、さすがにそろそろ手を付けないとまずいと考えたのだ。序盤は内容も問題も簡単だったので、とりあえず二つ解いてレポートも作っておいた。こうも簡単だと本当に三つでよいのか気になるところ。

スライド中の式番号を参照する部分がうまくいっていないものがあり、少し読むのに苦労した。多分TeXを1回しかコンパイルしていないのだろう。これに関して以下のようなツイートをしたが、RT先で2回どころか何回コンパイルしても出力が一定にならない例について話されていて面白かった。

latexのコンパイルが冪等じゃないのあり得なさ過ぎて面白い
— こたつがめ (@kotatsugame_t) 2022年12月8日

また、それに並行してICPCのチーム紹介ドキュメントの仕上げをしていた。アスキーアートQuineにいろいろ意味のある文字列を埋め込んで完成させた後、チームメイトやコーチに確認を取り、午前9時頃に提出した。

午前10時からまたハーメルンを読んでいた。1作読了。「サイコバグなお兄ちゃん、Vtuberになる。」。主人公がハイスペックで楽しい。特に悪いことをしたわけでもないのにタイミング等の関係でデビューと同時に大炎上するという展開は何作か読んだことがあるが、これはひとまずの終息までがかなり速く、ストレスを感じるシーンがすぐ終わってくれた。

syosetu.org

午後2時就寝。

12/08(木)

目を覚ましたら午後8時だった。先週の日記にも書いたように、今週はTAをしている講義が休講になる代わりに大学院の何かのオンライン説明会があった。それに盛大に寝坊してしまったらしい。どうしようもないので綺麗さっぱり忘れることにした。

布団でずっとカクヨムを読んでいた。4か月ほどページを開いておらず更新がかなり溜まっていたため、今日はそのうち「Vtuberってめんどくせえ！」を読み進めていた。

kakuyomu.jp

午前1時頃寝落ち。

12/09(金)

午前5時半起床。またカクヨムを開き、今日は昨日読んでいたものの短編集と「自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった」を読み進めた。

kakuyomu.jp

それぞれ最新話にたどり着いたところで布団から脱出した。

シャワーを浴びて午前11時過ぎに外出。原付への給油、昼食、散髪を済ませて午後1時頃帰宅し、またシャワーを浴びた。いくら頭を洗ってもらったところで首筋の細かい髪の毛は取れず、ずっとチクチクするのが耐えられない。

少しコーディングして午後2時から1on1。書いたものを説明していたらまたしてもバグりまくっているのに気付いたので、今日もいろいろ確認を取りながら書き直すペアプログラミングになった。

それが一段落した後はこれからのタスクについて。現状自分に任せるものがないらしい。ちょうど自分も来週はセミナー2回、再来週は集中講義と立て込んでいるので、少しの間インターン関連では何もしないことになった。来週の1on1の日程だけ決めて解散。1時間程度で終了した。

しばらく講義スライドを読んだ後、午後4時半前にまた外出。午後4時40分から大学でサークルバチャに参加した。

https://kenkoooo.com/atcoder/#/contest/show/739fe3f0-29f9-458b-a358-5daafacc649e

5問目まではよい。6問目は、最近あった模擬地区予選2022Lに関して見聞きした話を思い出すと、木の中心から同じ距離にある頂点しか同じ色で塗れないことがわかる。またそれは実際に達成可能。実装上は各頂点・各辺を中心だと思って計算し、最小値を求めることで、中心を具体的に求める必要がなくなる。

7問目は解いたことのない問題だった。 $A_i\lt A_j$ なる $(i,j)$ を固定し、各 $(x,y)$ について $2^Q$ 通りの操作のうちいくつで $(i,j)\rightarrow(x,y)$ になるかdpで求めればとりあえず解ける。当然間に合わないので一旦この方針から離れ、操作によって変化する転倒数を考えていたが、うまくいかない。元の方針に戻ってきたら、このdpが全 $(i,j)$ に対して同時に行え、かつ操作1回に対する更新が $O(N)$ で書けることに気づいた。そのままAC。

30分くらい余ったので解説チェックをしていた。その後感想戦。6問目で具体的に中心を求めなくても間に合うのは温情かと思っていたが、求めたとしてもそれに接続する辺を見るケースで結局候補が $O(N)$ 通りになるため、計算量的にはどちらも変わらないらしい。しかも、そもそも $N\le 100$ は葉の数がオーバーフローしないための制約だった。 $\bmod$ を取ると最小値が分からなくなってしまう。

午後7時に解散し、学食で夕食を摂って帰宅。YouTubeを開いたら「科学の力使いまくって隠居生活」が投稿されていたので視聴した。

www.youtube.com

そのまましばらくYouTubeを見ていたら午後9時。yukicoderのコンテスト開始を待ちながらAdvent Calendar Contestの7、9問目を通した。単なるdpとbit dpですぐ解けた。

午後9時20分からyukicoder 371に出た。星は多めだがコンテスト情報にある想定diffは低めでよくわからない。

yukicoder contest 371 (Asakatsu Presents) - yukicoder

Aはよい。Bはimos法で、区間の向きが逆なことに注意。Cは毎回作れる色を全部持ってよい。Dは組み合わせ的な計算をしたくなるが実はdpが行列累乗で書ける。

Eは答えを二分探索して、判定は $O(NM)$ 。TLが6secなので十分間に合いはするが、入力サイズも大きいしなかなか攻めているなと思った。解説曰く判定に $\log$ を付ける解法を落としたかったらしい。

Fは、「各グループでこれまで出題されたことのある問題数」だけわかっていれば直近 $K$ 日の出題状況も計算できて、その日あり得るセットとその確率がわかる。よってそれを状態としてメモ化再帰すればよい。状態数が $\prod_i(P_i+1)$ 通りで遷移に $O(N2^N)$ かかるが、制約が小さいため十分間に合う。

$\sum_i t_i\gt 60$ となるケースは絶対に全完できないので先に弾いておく。それ以外のケースはいつか必ず全完できる。

30分で全完して優勝。Fみたいな問題はほとんど見ないので、星4と言われても青diffと言われてもそうなのかと思える。そういう意味では難易度調整には成功していそう。

余った時間でDMOJの1900↓ratedのコンテストに参加した。終了が来週なので、ここには特に感想など書けない。

2022 Bayview Secondary School Programming Contest - DMOJ: Modern Online Judge

9月末にホスフィンとたいぺーと飲酒したときの余りを飲みながら、しばらくYouTubeやTLを眺めていた。

午前2時からは日記を書いていた。下書き保存ではなくうっかり投稿してしまったりしつつ、午前4時前に切り上げて布団へ。

少しだけハーメルンを読んだ。「転生チートオリ主が芋ジャージ女を養うまで」を読了。タイトル通り主人公が転生チート持ちなので面白そう。まだ3話までしか連載されていないので、これ以上特に言えることはない。

syosetu.org

午前4時半ごろ寝落ち。

12/10(土)

午前10時起床。準備して半からHTTF2023本選のオープンコンテストに出た。

HACK TO THE FUTURE 2023 Final (Open Contest) - AtCoder

出たといってもコードゴルフだけ。しばらく日記を書いた後布団に入り、少しハーメルンを読んで正午くらいにまた寝た。

午後3時から1時間おきに目覚ましで起きていたものの、冷凍弁当の受け取りに失敗した。午後5時に起きたとき不在着信があったのに気づいて分かった。インターホンの履歴を確認するとどうやら午後4時ちょうどに鳴らされたらしい。もしかしたら目覚ましの音で聞こえなかったのかもしれない。こちらから電話をかけなおし、週明け月曜日の夕方に届けてもらうことになった。

しばらくハーメルンを読んでいた。「出世レースに負けた私が殺戮サークルの姫になるまで」読了。主人公最強なのは当然良いとして、周りのキャラも個性的で好ましい。掛け合いが面白い。

syosetu.org

午後6時半からまた2時間ほど寝ていた。起きたらHTTFが終了していた。無事最短コードを取れたらしい。

冷凍弁当はないためカロリーメイトを食べ、午後9時からABC281に出た。

AtCoder Beginner Contest 281 - AtCoder

Aは降順のrangeを生成する問題で、Rakuの...という演算子が使える。逆に自分の知る限り、これ以外のどの言語・どの方法でも、昇順のrangeをreverseするか公差に $-1$ を指定する必要がある。ところが終点を1にしたり文字列のrangeを作ったりで2WA。

https://docs.raku.org/language/operators#infix_...

Bはsed。2文字目が0になるのを許してしまい1WA。Cは $T\leftarrow T\bmod{\sum A}$ として計算。Dはdp。

Eはsetを二つ持ち、値を追加したり削除したりするたびにset間で要素を移動させて、片方の中身が必ず下位 $K$ 個になるようにした。うっかり上位 $K$ 個を求めるコードを書いてしまったので値に負号をつけて対応した。

Fは上位bitから見て値を分類しながら再帰的に解く。binary trie木っぽいが実際に木を作る必要はない。

Gもdp。頂点1から近い順に距離を確定させていく。同じ距離にある頂点をまとめて決めるので、遷移は $O(N)$ 。それより1小さい距離にある頂点がいくつあるかわかれば遷移の係数が求まるから、dpの状態はその数とこれまでいくつ距離を確定させたかで $O(N^2)$ となり、間に合う。任意modなので二項係数は漸化式で求めておく。

Exはとりあえずdpを書いて形式的べき級数に言い換えた。 $i\ge 2$ について $dp_i=[x^i]\left(\left(\sum_{j=1}^N\binom A j x^j\right)\prod_{j=2}^{i-1}(1+dp_j x)\right)$ となる。この後きっと何かすごいことをするんだと思い諦めてBのコードゴルフを始めてしまったが、戻ってきたら解けた。

$F_i=\left(\sum_{j=1}^N\binom A j x^j\right)\prod_{j=2}^{i-1}(1+dp_j x)$ と置き、更新 $F_{i+1}=F_i\times(1+dp_i x)$ を平方分割してみた。 $F_i=f_ig_i$ と分けて管理する。 $f_2=\sum_{j=1}^N\binom A j x^j$ 、 $g_2=1$ であり、更新は $g$ のほうに1次式を掛ける。このとき $g$ の次数が適当なしきい値 $W$ を超えたら $(f,g)\leftarrow (fg,1)$ と置きなおす。

こうすると、毎回の更新も $[x^i](f_ig_i)$ の計算も $O(W)$ で行える。また置きなおしは $N/W$ 回発生するが、それぞれ畳み込みで $O(N\log N)$ になる。合わせると全体の計算量は $O(N/W\times N\log N+NW)$ 。 $W=\sqrt{N\log N}$ とすることで $O(N\sqrt{N\log N})$ を達成できる。2secで通った。

全完4位。Exの速度順では3番目で、ペナ差で負けている。まあ賞金がないコンテストなのでどうでもよい。CあたりからGまで特に詰まることなく駆け抜けられて爽快だった。

コードゴルフ。AはやはりRaku。Bは正規表現で判定するのはよくて、文字集合をわざわざ書かなければならないsedより適当なエスケープシーケンスが存在する言語のほうが短くなった。具体的にはPerlとVimで、入出力の差からVimが最短になっている。Cはdc。FはRuby。Exは今のところ自分のC++が最短になっている。他は手付かず。

昼までほぼずっと日記を書いていた。朝方完全に集中が切れたあたりで購読しているほかのはてなブログの更新を読みに行って、AOJ-ICPC Advent Calendarのために投稿された記事で扱われた問題2問に取り組んだ。どちらも結構すんなり通せてうれしい。

まず700点のEulerian Flight Tour。

AOJ 1393 - Eulerian Flight Tour - かっつのメモ帳

グラフに辺を追加して、単純・連結かつ次数がすべて偶数なものにしたい。最初は次数の条件を満たした後連結にすることを考えていたが、場合分けが面倒そうだったので方針を切り替え、まず完全グラフを作ることにした。 $n$ が奇数ならばそれでよい。

偶数の場合、入力のグラフに対する補グラフの辺のみを使って各頂点の次数を1ずつ減らしたい。補グラフの各連結成分が偶数個の頂点を持つことを確認した後、連結成分内で適当にペアにして二つを結ぶパスを取り、奇数個のパスに出現する辺を取り除けばよいと考えた。しかしこれだとサンプルで落ちてしまう。連結性が満たされないケースがあるようだ。

連結性が満たされない場合、取り除いた辺がウニグラフのようになっていると考えた。この場合、ウニの中心に接続する辺以外で入力に存在しなかった辺を一つ選び、その辺とウニの中心で作る三角形上の辺の状態を切り替えると、次数の偶奇を変えずに連結性を満たせる。入力のグラフが完全グラフ＋1点だった場合はどうやってもダメなので、これで十分な構築ができているはず。出したら通った。

しかし本当にウニグラフになっているかどうかがよくわからない。そこで、使う辺を補グラフ全体ではなくその中で固定した森から選ぶことにした。具体的には補グラフの連結成分ごとにdfs木を考えて、その上の辺だけ使ってペアを作る。こうすると取り除く辺の数が高々 $n-1$ 本になるので、もし残りのグラフが非連結になっていたら、ウニグラフを取り除いたということが示せる。dfs木を考えるのは上に貼ったブログを参考にした。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7161934

次に900点のAnimal Companion in Maze。

Animal Companion in Maze (AOJ 1374) - あああああ

無向辺を有向辺2本に分解し、辺を状態としてメモ化再帰することでとりあえず答えが出せる。途中でループを検出したら即座にInfiniteを出力すればよい。ところがこれだと値の取得のため行先の頂点に接続する辺をすべて見る必要があり、TLEしてしまう。

そこで値の取得をセグ木で行うことにした。各頂点についてそこから出る辺を適当に並べ、セグ木を作る。さらに値が確定していない辺のみを集めた列も作っておいて、必要な値がすべて出そろうまでこの列の要素を削除しながら再帰的に解いた。再帰する前に大きな値をセットしておき、それを取得することがあったらループしたと判定できる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7161973

辺に値をメモする方法は、全方位木dpを知らなかったころにそれが想定の問題を何とか解こうとして編み出したことを覚えている。結局その時はTLEしてしまったのだが、原因は上に書いたものと同じだった。リベンジみたいな感じになって嬉しい。

Submission #1214159 - square869120Contest #4

午前11時半就寝。

12/11(日)

午後7時半起床。今日の昼間に行われたJOI二次予選の問題がもう公開されていたので、取り組んだ。

JOI 2022/2023 二次予選過去問 - AtCoder

Aは $\max A-A_i$ と $A_i-\min A$ のうち大きいほうを答えればよい。 $\max$ や $\min$ を達成するインデックスが一致してしまうケースでも、もう片方が答えになるため問題ない。

Bは誰が4人のうち最も身長が高い人になるか決め打つ。残りは各クラスに対し身長がその人以下で最も高い人を選べばよく、これは決め打つ人を身長の昇順に見ることにすると一緒に計算できる。

Cはどの連結成分のマスを指定するか全探索する。見ている連結成分に隣接する連結成分を列挙し、どの色が最もマスの数が多いか調べ、その色で元の連結成分を塗りつぶすのが良い。

Dは面白かった。どの駅の貨物を駅1に輸送するか決めると、遠いほうから $W$ 個ごと一気に持ってくるのが最適。なので、これまで選んだ貨物の個数 $\bmod W$ と燃料の残りを状態とし、遠くの駅から順に輸送するかどうか決めるようなdpが思い浮かぶ。しかし計算量は $O(NWD)$ となり、実質 $O(N^4)$ なので間に合わない。

ここで、そもそもすべての貨物を輸送できるケースが多そうだと気づいた。どのくらい燃料が必要か見積もってみる。駅 $N-W+1\dots N$ の貨物を輸送するために $2N$ 、駅 $N-2W+1\dots N-W$ の貨物を輸送するために $2(N-W)$ 、……となるため、すべて足すと $O(N^2/W)$ になりそう。この値を $D$ が上回っていれば、答えが直ちにわかるのだ。

逆にそうでない場合 $D=O(N^2/W)$ である。この場合 $O(NWD)=O(N^3)$ となるため、上のdpを実際に計算しても十分高速。これで解けている。

Eは解けず。各区画について、それより標高の高い区画かつ最も近くにあるものを西・東それぞれ見つけておく。見つけた区画の標高が自分以下になったタイミング以降ならいつでも、その方向からの嵐で標高が減少するはずと考えた。タイミングを特定するのは二分探索。内部で、区簡に対してある値未満の要素を数えるデータ構造を使っており、合わせると $\log$ が三つついてしまった。

何とか実装しきったもののサンプルすら合わない。なんと、ある方向からの嵐で標高が減少した場合に、これまで逆向きの嵐に曝されていたのが隠れてしまうケースがあるらしい。当たり前すぎる。しかも、一方向からのみ嵐が来る小課題4は解けるだろうと思って出したらTLEしてしまった。

そういう困ったことが起こるのは標高が最も高い区画の近辺だけだろうと考え、そういう位置より先に嵐が到達しないよう最初に $X$ を書き換えてみた。この時見る標高は当然真面目に計算できるわけもないので、隠れているかどうかを考えずに計算した値を使った。出してみると小課題2と3も通るようになった。ただし小課題2はTLEが一つ取れない。

最後に小課題1の愚直を書いて53点が最高スコア。これをひねり出しているうちにもう日付が変わる時間になってしまった。

コードゴルフはAとBのみ。AはOctaveでそのまま、BはRuby。

午前0時半からCF #837 div.2に出た。

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

Aは最大と最小を選ぶ。 $a$ が全部同じ値のケースに注意。Bは区間の右端を固定して数える。Cは $\sqrt{10^9}$ 以下の素数が3000個ちょっとしかないらしいので、ギリギリ素因数分解できる。あとは同じ素因数を持つ数のペアが取れるか調べればよい。素数を列挙するのに失敗して1ペナ。

Dはパスの端点の組を状態とするdp。求める回文の長さが奇数の場合は真ん中の文字に対応する頂点のみのパスからスタートする。偶数の場合、真ん中二つの文字は必ず隣接しているから、それを結ぶ辺からスタートする。

パスを伸ばす方向にしか遷移できないので、例えば $(u,v)$ という状態から頂点 $u$ をそれに隣接する別の頂点に変化させるとき、 $u$ から $v$ の方向に1歩進んだ頂点は選べない。そういう頂点は $O(n^2)$ かけて前計算できる。

片方の頂点を変化させるケースと、両方の頂点を一気に変化させつつ回文を伸ばすケースが存在する。状態をパスの長さの昇順に見たかったため、012BFS、正確には12BFSとして実装した。

Eは上端下端と左の縦棒の列を決めた。 $O(n^2m)$ 。上端下端を決めたタイミングで、どの列なら縦棒を配置する余裕があるかとか、どの列から横棒を伸ばすとどこまでいけるかが決まるので、前計算しておく。この前計算も普通にやると $O(nm)$ かかってしまうので、下端を下にずらしながら更新していく必要がある。

そうやって必要な値が求まれば、あとは右の縦棒の列としてどこまで遠い列が使えるかを毎回求めればよい。ここは尺取りっぽくできるので計算量に $\log$ がつかない。

FはZobrist Hashを使いそうだがメモリが厳しい。 $a$ の要素は重複を省くと $2^{18}$ 種類くらいあるものと考えられて、これを小さいほうから $2^{10}$ 個ずつブロックに分け、それぞれでZobrist Hashを使い奇数回出現する要素があるかチェックしてみた。そのような要素が存在する最初のブロックを探すと $2^{10}$ 要素が候補になるので、それぞれ個別に確かめる。