週記(2023/05/22-2023/05/28)

05/22(月)

午後3時くらいに目を覚ましたような記憶がある。布団に転がってスマホを触りつつ、インターン先定例会までのわずかな時間で二度寝をするかしまいか考えていた。

ところがその定例会が急に午後4時開始に早められたため、布団から脱出した。何分急な話であるから参加可能な人だけで良いとは言われていたが、起きているのに出席しないのも心苦しい。

先週の進捗もあってないようなもの。今日は改めて何をやっているのか確認することでスライドを埋めた。

勉強会はゲート型量子コンピュータのシミュレータについてだった。n量子ビットをシミュレートする場合、どれがどの値かという2^n状態それぞれの確率をベクトルで持つことで古典コンピュータでシミュレーションを行うらしい。正確には「絶対値の2乗が確率となるような複素数」を持っているので、様々な量子ゲートが再現できるとのこと。

各ゲートが物理的にどういうものなのかは全然知らないが、結局2^n\times 2^n行列で表現されるのでその計算を追えば挙動は確認できる。ゲートの組み合わせがどういう効果をもたらすか、一見不思議に見えてもよくよく考えると納得いく解釈が得られたりして楽しかった。

その後はずっと週記を書き続け午後11時になって投稿した。シャワーを浴び、日付が変わって午前0時からSRM846に参加。およそ3か月ぶりらしい。Appletから接続するためにはConnectionをDirectからHTTP Tunnel Aに変える必要があるようで勘弁してくれという気持ちになった。

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

Easyから乱数で入力を生成する問題が出てきていかつい。整理すると1次関数たちの最大値取得に見えたのでCHTが頭を過ったが、冷静になればADそれぞれ最大の要素だけが候補となる。タイブレークは多少気を遣う必要があって面倒。

Medは半分全列挙。ずっと226で何かする方針を考えていたためこの発想に至るまで少し時間がかかってしまった。ただこうすると決めてしまえばあとは式変形をちょちょいとやるだけで問題なくマージできる形に持ち込める。

Hardはカス。読解を終えた時点で実装をひたすら頑張る問題だということは分かっていたが、残り時間30分以上を費やしてもサンプルを合わせるところまで持ち込めなかった。

チャレンジフェーズはしばらくしてもあんまり落ちていないのを見て早々に諦め、Hardと格闘していた。追加10分くらいでサンプルが合った。手元だと一回プログラムを走らせたら全ケース実行してしまうようになっているから、初期化に漏れがあった場合問題ないのに間違っていると思い込まされてしまう。まあバグはそれだけではなかったのだが。

Medまでが微妙に遅かったためパッとしない順位にいたものの、システスでEasyやMedが結構落ちて7位に浮上した。特にEasyはサンプルが弱すぎてタイブレークを間違えている人がたくさんいたようだ。

レートは2830→2824(-6)。結果的にはなかなかいい順位になったと感じていたので、レートが下がってびっくりした。

Hardの解法について。方針はL\cup\{W\}のprefixを全列挙して状態とするもの。追加であと何手残っているか、さらに直前の操作が文字の削除か否か・削除したならどの文字だったかを持つから、状態数は結構多い。遷移先は基本的に残り手数に依らないため、ほぼ全部前計算しておいた。この部分でmap<string,int>を使い倒し、実際の遷移時には状態を常に整数の組で表せるようにしておいた。

L\cup\{W\}のprefixでなくなるような文字の追加については、それが削除されるまでをひと固まりの遷移として計算した。その間は文字の追加・削除しか行えないので、合わせた操作回数を決め打てば場合の数はカタラン数に26のべき乗を掛けたようなものになる。ただし最初に追加する文字だけはprefixでなくなるという条件によって種類数が限られている。

午前4時前にラノベを1冊読了。「「キスなんてできないでしょ?」と挑発する生意気な幼馴染をわからせてやったら、予想以上にデレた」。面白かった。高校生までずっと仲睦まじく過ごしてきたという設定が嬉しい。一度疎遠になったが物語中で急接近する、みたいなわざとらしさがない自然な幼馴染関係が読めた。あとがきで言われていた「二人の日常を切り取った短編集」の雰囲気は確かに存在すると感じる。

しばらくTLを眺めた後、ゴミを出して布団に入った。午前6時半ごろ就寝。

05/23(火)

午後4時過ぎ起床。今日はサークル活動の日。今から大学に行くと4限終わりの混雑に巻き込まれてしまうため、念入りに布団でゴロゴロしておいた。

あまりに念入りにやりすぎたため家を出て学食に到着したのが5限終了の少し前になってしまった。夕食は15分弱で腹に詰め込んだが、その間に外まで行列ができていてゾッとした。大型連休を乗り越えたこの時期、この時間にここまで並ぶとは……。これからも授業終わりの時間帯には気を付けたい。

サークルバチャにはほんの少し遅刻して参加した。今日のセットは特に何ということもない。10問目でとりゐさんがハマっているのを見て辛そうだなと思っていたが、後から聞いたところ本当に謎のエラーを踏み抜いていてびっくりした。

https://kenkoooo.com/atcoder/#/contest/show/b93781ce-8706-4252-98b0-0f1abc29473d

PyPyではREになるコードが、Pythonで出したら通ってしまう。手元にREのケースを落としてもらい試してみたところ、周りにデバッグ用のコードを仕込んだり、変数の初期値を-1から-2Noneに変えるだけでも正しく動作した。まあ最適化周りのバグだろうなとは思うが、詳しくはお手上げ。

午後8時過ぎに解散しその足でゲーセンに向かい閉店まで遊んだ。今日もひたすら新曲埋め。

閉店後に立ち食い蕎麦を食べて日付が変わるくらいに帰宅。シャワーを浴びてからメールで案内の来ていた奨学金について少し調べていたが、インターンで収入を得ている自分が対象者となるのか微妙に不安になる記述があった。募集要項と申請用紙の内容に食い違いも見つけたので、それも含めて問い合わせておいた。

朝までずっとラノベを読んでいた。午前6時過ぎ、昨日のSRMがpractice roomに追加されたことに気づいてHardを提出してみた。何事もなく通ってびっくり。計算量を正確に見積もっておらず、TLEするかも、と考えていた。

午前8時半就寝。

05/24(水)

午後4時起床。ABC302優勝の賞品が届いていた。

大学生協に行ってお菓子やラノベを買ってきた後、ホスフィンと合流して街に出た。今日はサークルの確定新歓の日だった。

ホスフィンと話していることが多くなってしまったが、それなりに交流もできて腹もいっぱいになって、非常に満足のいく会だった。焼けた肉はトングで掴まず箸で取って食べるというのはもちろん徹底していた。これにやられて救急車を呼んだことを忘れてはいない。

生肉を網に移したのと同じトングで焼けた肉を皿に移すのもいけない。知ってはいたのだが、自分がこれにやられることはないだろうと思ってこの日も特に頓着していなかった。

日記(2020/11/06)あるいは僕が深夜に救急車を呼んだ話 - kotatsugameの日記

午後8時に解散して、それから閉店までゲーセンで遊んでいた。今日はオンゲキとmaimaiの連動楽曲を解禁して詰めた。

オンゲキでは15の「LAMIA」が解禁できる。2プレイ目でラストのスライドが抜け鳥寸、3プレイ目で出た。終盤はどうしようもないのだが、それ以外は譜面動画を見て考えていたよりも押せたなという印象。

maimaiでは14+の「雷切-RAIKIRI-」が解禁できる。少し粘着してAJを出した。これも思っていたより押せた。二つとも特に運指など組んではいなかった。

帰宅してシャワーを浴びた後、思い立って他の人の欲しいものリストからいくつか買ってみることにした。せっかく大きな収入があったしおすそ分けという感じ。誰に何を買うかまではすぐ決められたが、メッセージをどうするかで迷って結構時間をかけた。

朝までかけてラノベを2冊読了。

1冊目、「黄金の経験値」2巻。非常に面白かった。1巻から完全に取り除かれていたブランの話がこっちに来て、さらにその後ライラとも出会うため、サブタイトルの「進撃マルチプレイ」がピッタリになっていて感動した。書籍化に当たっての組み替え方が上手い。ブラン視点が一気に読めるのも快適。

2巻序盤には主人公の敗北シーンがあった。なろう版と同じ位置である。物語の重要なシーンとなるため書籍化にあたって削除するなんてことはできないわけで、回避できない衝撃が読む前から少々怖かった。しかしこれも話の展開の順番が巧みで、それほど大きなショックは受けなかった。なろう版を確認したら同じ順番だったから、ここについては別に話を組み替えたわけではないらしい。

序盤の衝撃を乗り越えたら、あとはもうずっと面白い。やはり主人公レアの格好良さ・可愛らしさが際立つ。文章からも十分感じ取れるがイラストが付くと別格だった。格好良さという点では口絵が頭一つ抜けているかと思う。カラーだし。可愛らしさについては223ページのイラストが強烈に印象に残った。そんな描写は本文中に一切ないのに、こういうポーズ取ってそう……!感が匂い立つ。

2冊目、「放課後はケンカ最強のギャルに連れこまれる生活」。主人公が強くて爽快だった。勉強の出来はもっと良いという設定にしてくれたほうが個人的に嬉しい。本文中で説明されたような成績で人に勉強を教えたり、その勉強会でふざけようとするヒロインたちに圧力をかけたりしても、「でもこいつもそれほど頭が良くないんだよな……」みたいな見方をしてしまう。

折り込みチラシで「魔王2099」のアニメ化を知りひっくり返った。2巻が出てから2年近く新刊がなく打ち切りだと思っていたところ、最近3巻が出ると聞いて非常に嬉しく思っていたが、それどころの話ではなかった。実は3巻発売とアニメ化はほぼ同時に発表されたらしく、自分がアニメに関して全くアンテナを立てていないから情報を知るタイミングがずれたようだ。

2099.world

ほんの少しだけインターン関連の作業をした。先週の宣言は嘘にはならなかった。

今やっていることは1週間後までに必ず終わらせますと宣言した。

週記(2023/05/15-2023/05/21) - kotatsugameの日記

布団に入ってハーメルンを読んだ。4時間ほど熱中して正午くらいに寝落ち。

05/25(木)

午後5時ちょっと前に起床。すぐ1on1に臨んだ。

ついに長いこと放置されていたドキュメント整備が終了し、次何をするかという話になったが、コードを書くタスクとして明確な形になっているものは特にないらしくまたドキュメント整備になりそう。しかし今回は自分が以前書いたコードについてREADMEを充実させるというものだから、いやというわけではなくむしろ気が楽である。あとは少しリファクタリングもしたい。

コードにフォーマッタを適用するべきという話があって、その設定のために1on1の時間をしばらく消費した。VimからプラグインとしてBlackを呼び出す方法があるようだが、自分はそもそもプラグインの導入から詳しくない。その場でドキュメントを読んだりして頑張るもなかなか動かなかった。Vim上でのインストールだけでなくpipでもBlackを導入すべきとの助言を頂きようやく使えるようになった。

1on1終了後すぐに学食に向かい夕食を摂った。ミールカードの本日分を使い切るためサラダを5個食べたらそれだけで腹がいっぱいになってしまった。普段から3個食べているので2個増やすくらい全く問題ないと思っていた。

帰宅してハーメルンを読み耽り、午後9時くらいに「チート持ってウマ娘なるものに転生した、芝生える」を読了。

syosetu.org

主人公陣営が全員最強で非常に良い。他の作品でやらないような現実感の全くないらしいローテーションは読んでいて楽しかった。主人公のトレーナーという立ち位置とそのチートっぷりの組み合わせも、おそらくこの作品のクライマックスとなるであろうチームのエースとのレースについて妄想が広がってワクワクする。問題はそこにたどり着く前にエタってしまったということだけ……。

ここからセミナー準備を始めた。午後11時半からはECR149に出た。

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

Aは1手で+xするか2手で+1+(x-1)すればよい。

Bは連続する同じ不等号の数を数えて、その最大値+1が答え。コンテスト開始からしばらくは最大値そのものが答えになっていたため、+1するコードとしないコードを両方提出しておいた。コンテスト中にリジャッジされたがこれによるタイムロスは最小限に抑えられたと思う。

Cは文字列のcostが文字列中に存在する10の個数と一致する。観察から導いて、いかにもそれっぽかったので証明せず突き進んだ。実装も実は?を直前の文字と同じにするだけでよい。先頭は0にする。

Dはまず()の数が一致している必要がある。逆にこれが成り立つ場合、それぞれの文字を\pm 1に置き換えて累積和を取った列を0の位置で切ると、各区間は正しい括弧列かその反転になっている。それぞれに1色使うことで高々2色で塗り分けられる。

Eは再帰的に定められる。初戦で負けるチームの番号は2^{k-1}+1\dots 2^kであるから、これらが2^{k-1}試合に1チームずつ現れるように並べる方法を数え上げる。残りは初戦の段階ならどう決めてもよいから再帰で次の試合に丸投げする。

Fは結構簡単だった。答えで二分探索し二人が列を分割する位置を全探索する。すると分割の左右それぞれについて、総和がチェック中の値を超えないように要素をできるだけ多く選んだ時の個数を求め、足したものがk以上になるか判定することになる。priority_queueで選んだ値を管理しながら差分更新することですべての分割に対し前計算できる。

計算量はO(n\log n\log\sum a)で2000ms近くかかった。また途中までマルチテストケースなのにnの総和の制約が書かれていなかったらしい。何も気づいていなかった。単なる書き忘れだったので命拾い。

40分弱で全完し2位。コンテスト終了直後に動画を投稿した。

www.youtube.com

セミナー準備に戻り、ハーメルンに気を取られつつも午前6時までかけて完成させた。今日用意したのはDiestel 6.5章分。構築のアイディア自体は結構わかりやすいと感じたものの、細かい議論……というかその準備が大変だった。特に\vec{e^{\ast}}\vec{e}^{\ast}をちゃんと使い分ける必要があって説明は煩雑になりそう。うまくイメージを伝えられれば良いのだが。

準備中も読み続けていたハーメルン、「YOU MAKE LIFE(夢喰らい)」を読了。主人公が悪役というのはウマ娘の二次創作では初めて見た。世界観とは合わないはずだが、描写が上手いのかあまり違和感なく読めた。主人公の圧倒的な能力を前にしてもレースに対する熱意を失わないウマ娘が描かれるから、それほど悪いことをしている感じにはならない。しかしよくよく読むとサラッと「心を折って引退させた」とか書かれている。

syosetu.org

しばらく日記を書き、購買の開店を待って大学に向かった。大学前の道が大混雑していて移動にかなり時間がかかった。ラノベと菓子パン類を買い込んですぐ帰宅した。

シャワーを浴びて布団でハーメルンを読み、正午くらいに寝落ち。

05/26(金)

午後4時半起床。すぐ大学に向かい、午後5時からのセミナーに出席した。

書く

午後9時半くらいに家にたどり着き、すぐyukicoder 390に出た。

yukicoder contest 390 - yukicoder

遅刻したので先頭から解いても点数は低いだろうなと思い、EFGHDCBAの順で解いた。結局途中でかなり詰まってしまったのであまり意味があったようには見えない。

Eは素因数分解したときの指数の列を状態としてメモ化再帰。遷移先をdfsで列挙した。遷移の係数に指数そのものが登場するため、整数に直さず列のまま扱ったほうが楽なはず。まあ正確には整数に直すことに一切思い至らなかっただけなのだが。

Fは隣接する頂点の情報が欲しいので、見るべき辺をO(\sqrt M)本にすればよいだろうと考えた。その方法として最近よく「辺を次数が小さい方から大きい方に向き付ける」ということを使っており、今日もこれをしてから考え始めたが、大失敗だった。

クエリについて、Xから出ている辺の先の頂点は毎回O(\sqrt M)かけて見ればよい。Xに入ってくる辺については、始点がどのワールドにいるかをmultisetなりで持っておけば、更新コストを始点側に押し付けることができる。ところがこれは計算量O(Q\sqrt M\log N)であり、何度も何度もTLEしてしまった。

最終的にはunordered_mapを使ってカウントし1500ms。ランダムケースでは差が付かないのにちゃんと落ちるので大変だった。次数のしきい値で分けておけば始点の情報を持つべき頂点が十分少なく、配列で対処できるというのが想定解だったようだ。またbitsetでも解けるとのこと。どちらも思いつけなくて残念。

Gは燃やす埋める。Hは(L,R)L-1\leftrightarrow Rの辺に読み替えること自体は最初から考えていて、うまく詰められなかったので適当なdpを書き数回WAを出した後、その方針でそれっぽく書いたら通った。理解しておらず既視感だけで押し切ったような感じであり、解けたとはあまり言えない。

残りは消化試合。Dはdp、CはUF、Bは中央値、Aはやるだけ。全完して10位だった。

火曜日送った奨学金に関しての問い合わせに回答が返ってきていた。自分にも受給資格があるようだ。せっかくだから申し込みたいと考えている。

シャワーを浴びて食事し、しばらく日記を書いたあと、ハーメルンを読んだ。「転生したらまさかの馬!?」を読了。

syosetu.org

書く

布団に移動してもう1作読み始めた。非常に面白く、ここ最近睡眠時間が足りていないのにそれをさらに削って熱中してしまった。午前10時くらいに寝落ち。

05/27(土)

午後1時45分起床。非常に眠いがハーメルンが面白かったので仕方ない。

水曜日に買ったものがさっそく届いたようだ。うしさんの欲しいものリストには最近食品類が四つ追加されていたので、それを一つずつ注文しておいた。それぞれラッピングするのは値段が馬鹿にならないので省略させてもらった。

午後2時からUniversal Cup 18回目に出た。今日はShenzhenセット。

The 1st Universal Cup. Stage 18: Shenzhen - Dashboard - Contest - QOJ.ac

書く

しばらくハーメルンを読んで過ごし、午後9時からABC303に出た。

NS Solutions Corporation Programming Contest 2023(AtCoder Beginner Contest 303) - AtCoder

Aは問題文にある1l0oが異なる文字であることに気づけず、十秒くらい固まっていた。指定されたペアをどちらか片方の文字に寄せてから普通の一致判定をすればよい。

Bは全部チェックするだけ。ここで制約の(物理的な)行間が普段より広いことに気づいた。Cは書いてあることを書いてある通りに細大漏らさず実装する。結構不安だったが一発で通った。DはCapsLockのオンオフも状態に持ってdp。

Eはレベル2の星を見つけるのが難しい。次数3以上の頂点を探し、そこからdfsで上手く切り分けていくことを考えていた。もしそのような頂点がない場合は最初レベル2の星しかなかったということで、頂点数を見ることでN/3個と特定できる。

複雑で面倒な解法だからあまり実装したくない。別の方法がないか少し考えてみたところ、閃いた。まず次数3以上の頂点を列挙することでレベル3以上の星を決定しておく。それらの星が消費する頂点数を数えてNから引くと、残りがレベル2の星による頂点数と一致する。先ほどと同様3で割れば個数が求まる。

Fは大変だった。二分探索を考える。Tターンで倒せるか調べるためには、残りT\dots 1ターンの時点で唱える呪文をそれぞれ決め、減らした体力の合計がH以上かチェックすることになる。ここで、残りiターンのとき唱える呪文は\min(t,i)\times dが最大となるものである。

残りターン数に対する唱える呪文の関係を逆にする、つまり各呪文を唱えるべき残りターン数を考えてみると、必ず区間になることがわかる。だからその区間を決定することで上に書いた判定がO(N)で行える。まず区間が空でない呪文を区間の降順に列挙して、その後隣接する呪文を比較することで区間の端点を計算した。

順番については、まずt\times dの降順に並べ、次にdが累積MAXを更新する点だけ抜き出せばうまくいった。十分ターンが残っている場合はt\times dが最大の呪文を唱えるべきであり、そこから残りターン数が少なくなるに従ってdが大きい(ただしtが小さい)呪文が最適になっていくという感じ。

正しく列挙できれば区間の端点を求めるのは単なる算数である。区間が対応する呪文のtを必ず含むため、これをassertで確かめながら計算した。二分探索の判定では\sum_{i=l}^r\min(i,t)\times dO(1)で求めなければならないため多少の場合分けが必要となる。この値は非常に大きくなり得るから、オーバーフロー回避のため__int128を持ち出した。

何とか一発で通った。コンテスト後に知ったことだが、単に区間の昇順に使っていくだけでよく、二分探索の必要はなかった。

Gは区間dp。公式解説と全く同じだった。区間の幅がiで左端がjであるような状態から二つ目の遷移を行うと、取得するのは幅i-Bで左端が[j,j+B]であるような状態たちである。ここを[j,j+B)だと勘違いして1WA。

Exは次数を決め打ったときのケイリーの公式を知っているかという問題。微妙に忘れていたがググったらすぐ出てきたので助かった。これさえ認めればあとはf=\sum_{d\in S}\frac{x^{d-1}}{(d-1)!}とおいて(N-2)![x^{N-2}]f^Nを求める問題になる。二分累乗法でO(N(\log N)^2)

Cayley の定理と、頂点次数制約のついた全域木の数え上げ - けんちょんの競プロ精進記録

全完6位。Gの1ペナがなくても順位は変わらなかったようだ。日本内では5位なので賞金1万円となる。コードゴルフはAのみで、Vim。文字を揃えるのをtrで行った後は一致判定というよくある問題なので過去問から丸々引っ張ってきた。

動画を投稿した。

www.youtube.com

今日これから予定されていたCF div.1はサーバートラブルで延期になったらしい。

Codeforces Round 875 is Rescheduled - Codeforces

布団に入ってスマホを触ろうとしたら、即座に寝落ちした。午前0時半過ぎだったはず。

05/28(日)

午前6時から4時間ほど、起きてハーメルンを読んでいた。また二度寝して今度は午後1時起床。

午後1時半からMMA Contest 015に参加した。電通大のサークルが主催するコンテストで、今日はオンサイト会場もあるらしい。

MMA Contest 015 - yukicoder

Aはよい。BはXORになる。Cは基本的にy\equiv f\times x^{-1}であり、x\equiv 0のときだけ別に処理する。

Dはクエリ2の答えを全部前計算しておく。この値をソートしておけば二分探索でクエリ1にも回答できる。EはN!が含む素因数Pの数を数えた後N!^{N!}倍する。

Fは難しい。固定された要素同士の転倒数は(N-M)!倍されて寄与する。固定されていない要素同士の転倒数はN-M\ge 2とすれば合計で(N-M)!/2である。片方が固定されているケースは、固定されていない要素を昇順に見て、どの位置にあればどれだけ転倒数に寄与するかを逐一管理した。固定された要素との大小関係が逆転する度区間ADDで更新できるので遅延セグ木に乗せた。

Gは8近傍への移動で区画を横切るための最短コストを求めるやつ。Hは半分全列挙。Iは操作の回数に対する追加スコアの総和を求めたい。C_i=B_jのとき操作回数i-A_jに対してY_j加算されるが、これは各色について畳み込みで一気に計算できる。

Jは始点を固定し、外積の和を最大化しながら4点辿って、最後に始点との外積を足したものの最大値を求めた。しかしWA。四角形が捻った感じになるとまずいかと思って凸包上の頂点だけ辿ることにしたら、今度は凸包が三角形のケースで落としてしまった。そのケースだけ凸包+1点を全探索してAC。

最初の提出が落ちたのは、同じ点を2回連続で使うことを許してしまったからのようだ。ここを修正すると通った。四角形が捻った感じになる場合は外積の値は増えないので問題にならない。

Kはdp。遷移できる区間はZ-algorithmで求まる。遷移コストは一次関数なので、直線ではなく線分の追加ができるLi Chao Treeを窃盗した。

Dynamic-Li-Chao-Tree | Luzhiled’s Library

Lは区間を必要なだけ分割しておけば後はよくあるセグ木の問題になる。分割位置はAが変化する点に加え、0-indexedでx-1xl-1rになる。クエリを先読みして求める。

1時間40分くらいで全完し4位となった。

水曜日に買ったのはうしさんに送ったものだけではない。もう一人(?)、kyopro_friendsさんにはサーバルキャットのぬいぐるみを送っていた。

欲しいものリストにあったぬいぐるみの中で、以下のツイートで一番に名前が挙がっていたのがサーバルだったからこれに決めた。安易なけもフレグッズではなく元となった動物のぬいぐるみが列挙されているのは、グッズは自分で買うという決意の表れだろうか。けものフレンズというコンテンツに対する真摯さを感じる。

かなりリアルなぬいぐるみなので初めて商品写真を見たときはギョッとしたが、これはこれで愛嬌があって良いのではないか。

シャワーを浴びたあとまたハーメルンを読んでいた。「転生赤毛バは凱旋門の夢を見る」を読了。

syosetu.org

書く

1時間ほど日記を書いていたが非常に強い眠気を感じた。仮眠を取ることに決め、午後7時から1時間半布団で横になった。午後9時からARC161に出た。

AtCoder Regular Contest 161 - AtCoder

Aはなんとなく見覚えがある。Aが昇順ソート済みとして、例えばN=5のときA_1,A_4,A_2,A_5,A_3のように並べるのが最適に見える。これでM型にならない場合はA_4=A_2またはA_5=A_3が成立するが、いずれにしても「Aに同じ要素が3個存在する」かつ「それ以下の要素が1個存在する」が成り立つ。

まず前者からその要素は1、3、5番目に並べるしかない。しかし後者からそれ以下の要素を2番目または4番目に置くことになって矛盾する。よって不可能。つまり先に述べたような構築を行えることが十分条件だけでなく必要条件にもなっていると分かり、判定が可能になった。

Bは最初f(X)=2と誤読していて場合分けをベタ書きしていたが、f(X)=3だとさすがに面倒。再帰関数を書いて上のbitから試していった。あるbitを立てないと決めた場合、その下のbitはどれでもいくつでも使えるから、探索する範囲はそれほど広くならない。

Cはdfs。「自分の色を決めたか」「親の色を決めたか」の二つの情報を持ちながら葉から決めていく。決めた場合は色を持つが、決めないということも許容する。これでうまくいく。ある頂点を見ている場合に、その頂点の色を操作後のSと合わせることだけ考える。最初に、自分の色を子によって決められてそれが矛盾した場合は不可能なことに注意。自分の色は自身に関係しないため、以降無視してよい。

色をBにしたい場合、子と親の色においてB過半数を占める必要がある。子の色で決まっていないものは自分より上には関係しないから、すべてBにしてよい。この状態で過半数を達成していれば親の色は何でもよい。ちょうど半々だった場合は親の色をBにするしかないから、このタイミングで「親の色を決める」という事象が発生する。それ以外は不可能。

Dは謎。まず辺の数に関する条件からDN\le N(N-1)/2、つまりD\le(N-1)/2が必要。そこからなかなか進まなかったが、D=1のときサイクルを作ればよいというところからそれっぽい構築をエスパーできた。D=1のときは頂点番号の差が\bmod Nで1であるような頂点間に辺を張った。これを2\dots Dでも行えばかなり対称性の高いグラフができるから、どの部分グラフもそれほど密にならなさそう。

また、これで多重辺や自己ループができない条件はD\lt N/2となり、辺の数から導いた条件と一致する。これもそれっぽさに信憑性を与えている。証明ができなかったが、その時点で400人以上通していたのでどうせこれだろうと思って出したら通った。

Eは解けず。あり得ない色パターンを持つような部分グラフを決定し、それを探すことで解こうとした。1個見つけて提出したが全然ダメでそれ以上は複雑すぎて考えられなかった。そもそも「解が必ず存在する」ということすら分かっていなかった。

遅めの4完で142位。意気消沈しつつ午後11時半からCF #875 div.1に出た。昨日延期されたコンテストである。

Dashboard - Codeforces Round 875 (Div. 1) - Codeforces

Aは頂点1から他の頂点へのパスを描くことを考えると、辺の番号が大→小の順に並んでいるところでステップ1を余計に1回行う必要がある。よってこれの最大値を求め、最初の1回を足したものが答え。

Bはよくわからない。a_i\cdot a_j\le 2nなので掛けて2n以下になる数のペアはO(n\log n)個しかないから、これを全探索した。対応するbを列挙しておいて少ないほうを舐めて和が求める値になるものを数えれば間に合いそう。この数える部分にmap<int,int>を使って出したら3700msだった。怖いが高速化する方法も特に思いつかないため、このままにしておく。

Cは結構すぐ解けた。括弧列を\pm 1にして累積和を考えることで、条件をうまく分解できる。具体的には区間[l_1,r_1][l_2,r_2]について、l_1\le l_2\le r_1\le r_2つまり交差しているときは[l_1,l_2-1][l_2,r_1][r_1+1,r_2]が、l_1\le l_2\le r_2\le r_1つまり包含関係にあるときは[l_2,r_2][l_1,l_2-1]\cup[r_2+1,r_1]が、それぞれ正しい括弧列になっていることが必要十分条件

これをたくさんの区間に対して計算するのは難しい。閃きによって「自分を含む区間の集合」が等しい括弧を集めてきたときに正しい括弧列になっていればよいことが分かった。Zobrist hashを使うことで高速に分類できる。あとは対応するカタラン数を掛け合わせれば答えになった。

Dは、直感的には二部グラフと見て二つの部集合をそれぞれ0、1で塗分けるのがよい。長さ1以上のパスに対するMEXが常に最大値の2となるからだ。さすがにこんなのがDに置かれるわけはないのでもう少し考えてみると、適当な部分木の色を一気に反転させることで改善できる可能性があることに気づいた。長さ1以上のパスのMEXはほとんど変わらないため、この操作で色0の頂点をいくつか増やせれば得である。

それでまず、0は3連続せず、1は2連続しないように塗り分けるdpを書いてみたところ、pretest 6で落ちた。1の2連続も許してみたもののこれも同じケースで落ちてしまう。同じ色が3連続している場合真ん中の色を切り替えることで必ず得すると考えていたが、その真ん中から別方向に辺が生えている場合を一切考えていなかったらしい。

どうしたものか考えこんでいると、CがHackされたという通知が来た。Zobrist hash用のmt19937_64にシードを与えていなかったから狙い撃ちされたようだ。random_deviceでシードを設定するようにしてリサブ。これで350点ほど落としてしまった。本当に勘弁してほしい。

Dに戻ってきたら、同じ色の連結成分のサイズを持つdpが降ってきた。ベースとして長さ1以上のパスのMEXがすべて2の場合、つまりn(n-1)を基本として、そこからどれだけ増やせたかを値に持って遷移していく。負になるところは無視してよい。

色0の連結成分のサイズがcのとき、長さ0のパスとして+c、連結成分内の長さ1以上のパスとして-c(c-1)/2が差である。c\le nなのでc(c-1)/2\gt nであるようなcは計算しなくてよい。つまり考えるべきサイズはO(\sqrt n)となる。色1も同様。遷移が間に合うかは分からなかったがそう酷いことにはならないだろうと考えた。

固定長配列でO(n\sqrt n)のメモリを確保しようとしたらMLEになった。関数内でvectorを用意すれば、必要なくなったらdeleteされるので空間計算量が押さえられそう。出したら通った。

Eは何も分からず。システスではBも何とか通ってくれて4完35位、レートは2867→2888(+21)となった。

今回のコンテストは、結果こそレート増加となったがいろいろ酷かった。まずBについて、少ないほうを舐めるという工夫に関する計算量の評価は去年のMHCで見たことがあったはず。これに照らせば今回の計算量はO(n\sqrt{n\log n}\log n)となる。

Dは2乗の木dpの亜種で、配列長をKで打ち切れば計算量がO(nK)となるというやつ。今回はK=O(\sqrt n)である。空間計算量についてはO(\sqrt n)で打ち切らなかった場合でも確保しているvectorの長さの和が常に「dfsでこれまで訪れた頂点数」と一致することが言えるので、O(n)となる。

この空間計算量の評価は問題の構造に依存しているが、依存しない方法もあるらしい。HLDの構造を利用する方法で公式解説から以下の記事にリンクが貼られていた。頭がいい。

[Idea] Using HLD to reduce memory - Codeforces

ARC-A、Bのコードゴルフをした。Aはソートして判定するそのままのコードを色々な言語で書いてみて、今のところPerlが一番短くなっている。BはRubyで、最初に答えの候補を全列挙した後二分探索で求める解法を実装した。[59,58,...,0]に対してcombination(3)を呼び出し生成すると、自然と降順に並んでくれてソートの必要がなくなる。

動画を投稿した。

www.youtube.com

www.youtube.com

日記を書いて午前8時就寝。