01/23(月)

午後3時少し前に起床。すぐ集中講義のZoomに接続した。

今週1週間参加する講義の名前は「応用数理総論」で、これだけだと何のことかわからないが内容は数理論理学である。実は同じ講義が学部生向けとしても開講されていて、自分は去年それの単位を取得した。だから知っている内容だろうし単位も楽に取れそうという見込み、純粋に理解を深めたいという気持ち、さらに今期の専門科目で他に興味のある科目がなかったため、以上3要素により受講を決めた。

初回の今日は基礎の確認で、命題論理、1階論理、再帰的関数、不完全性定理などが予定されていた。実際は3時間に収まらず、不完全性定理は次回に回された。内容的にはほぼ同じことを去年もやったはず。去年は資料が配られるだけだったが今年はZoomで実際に説明されるので、そこで何か得られるものがあるかと思ったら、特に何もないまま終わってしまった。まあ聞いているだけでわかるなら苦労はしないということで。

午後6時終了。今日オンラインだったのは予定していた講義室が取れなかったからで、明日からは対面になるらしい。

直後にインターン先定例会の会議に接続した。勉強会発表が終わった後の質疑応答の時間で、発表を聞いていないため特に何も言えることはなく、スライドを眺めて30分ほどで終了。

それから日記を書いて午後9時半頃投稿した。書いている途中でちょっとTLを見たとき興味深い話題を見つけ、それに関して少し調べていたので日記に書いておく。

.#マシュマロを投げ合おう https://t.co/pj7FH7xEFF pic.twitter.com/GEQAes9Nlx
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年1月23日

日曜日のARC-Dの話。std::stable_sortを使うと比較回数が足りるという話だったが、サンプルを試すと同じペアが2回聞かれてしまうらしい。本当にマージソートしているならこんなことは起こらないはずだし、余計な比較をしているのになぜ回数が足りているのかもよくわからなくなる。上のツイートでは解決しておらず、自分も気になったので調べてみた。

2727行目を見るとマージソートする前に7要素ごとに挿入ソートが行われるようだ。実はGCCの挿入ソートは同じ比較を2回行うことがある。逆にそれ以外の部分は普通のマージソートだから、これが理由だとわかった。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2727

挿入ソートは、要素一つずつに注目して、前の要素より小さければ交換してさらに前を見るということを繰り返す実装になっている。ところがこれをそのまま書こうとすると、見ている要素のさらに前に本当に要素があるか毎回判定する必要が出てきてしまう。それを避けるため、最初に先頭要素と比較する処理が1819行目に入っていて、この比較が挿入ソート本体の比較とダブる可能性がある。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1819

以上のことは日記を書いているときに確認した。月曜日の時点では見る部分を勘違いしていて、数列の長さが短いと挿入ソートになるせいだと言っていたが、それはマージ用のメモリが確保できない場合のみ実行される関数だった。通常時は上のような理由で比較がダブるはず。

std::sortは高速化のためにいろいろ複雑なことをしているから、比較回数は多くなりがちらしい。まずクイックソートのパーティション用pivotを決めるために何回か比較している。次に、クイックソートの再帰が深くなるとヒープソートに切り替わる。最後に粗くソートした配列を挿入ソートして終わり。比較のダブりも至る所で起こりそう。

今日が期限の期末レポートがあるので書いた。確率モデル論という講義。講義中に出された問題から3問選んで解けという課題で、実は昨年末に出された時点で2問解いてあったので今日は追加で1問解くだけ。1時間で完成した。

教員のやる気がなさそうで講義スライドも講義動画も使い回しらしいが単位取得には問題ない。問題3問というのも実は全15問中3問で、しかも2回目・3回目の講義で3問ずつ出題されるという偏りっぷりだから、講義の序盤の内容だけ把握すれば期末レポートが書けてしまう。いわゆる楽単というやつだった。

しばらくなろうを読んだりニコニコ動画を見たりした後、かなり久しぶりにTUPCのテスター作業をした。そろそろ気合いを入れないとまずい。

一段落して午前7時頃布団に入り、しばらくなろうを読んで午前9時就寝。

01/24(火)

午後2時半起床。天気予報によれば夕方から雪が降るらしく原付で登校できない。仕方なく地下鉄で向かったら案の定遅刻、と思いきや先生が機材の設定に手間取っていたためギリギリ間に合った。

今日は去年やっていない2階論理の話。本当はもっと内容があったが、2階論理以外は理解が及ばなかった。そもそも理解しようとしていなかった気もする。眠気が強くウトウトしているうちに時間が過ぎていった。

学食で食事して帰宅。雪は降りそうだがまだ降っていなかった。疲れて布団に倒れこみ、なろうを読んでいるうちに寝落ちした。午後8時半。

午後10時に目を覚ました。改めて寝直すか迷っていたがECRがあることに気づき起きていることにした。なろうを読んで時間を過ごし、午後11時半からECR142。

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

Aは $h=1$ なるモンスターが2匹いれば一つ目の呪文で倒すべきで、それ以外は1匹ずつ倒していく。Bは最初にtype 1をすべて話し、次にtype 2とtype 3を交互に話すのが最適で残りは貪欲に取れる。場合分けを頑張る。

Cは、 $k$ 回操作するとき、 $2k$ 要素を一気に削除してから先頭と末尾に $k$ 要素ずつ振り分けると思ってよい。これで $p$ がソートできるのと $p$ の部分列として $k+1\dots N-k$ が現れることが同値。この判定を使って $k$ を二分探索する。

Dは $a_i\cdot a_j$ の先頭 $b$ 項が一致することと $1\le k\le b$ に対して $(a_i)_k=(a_j)_k^{-1}$ となることが同値。辞書順において $a_i$ より小さい $(a_j)^{-1}$ のうち最大のもの、あるいはその逆を試せば十分である。あらかじめ $(a_j)^{-1}$ をソートしておいて、 $a_i$ の位置を二分探索で求めるとよい。

Eは大変だった。 $m_1$ 、 $m_2$ を素因数分解した結果を使うと約数の全列挙ができる。これが $d$ になるので、 $d_1,d_2\le n$ によって $d=d_1\cdot d_2$ と表す方法のうち $d_1$ が最小のものを求めたい。 $d_1\le n$ は最後にチェックすればよいので、結局 $d$ の約数であって $n$ 以下で最大のものを求めることになる。

約数の全列挙の過程でさらにその約数も全探索することにしたら、最悪ケースである $m_1\cdot m_2$ が高度合成数の場合に1ケース0.5secくらいになった。微妙に間に合わないようだ。その後高速化しようといろいろ書き換えたもののむしろ遅くなる一方だった。

しばらく考えてまともな解法を思いついた。もし $d\le n$ なら $d=1\cdot d$ とするべき。そうでない場合 $d$ の素因数 $p$ を全探索し、 $d/p$ の結果を流用する。最適な表し方 $d=d_1\cdot d_2$ について、もし $d\gt n$ なら必ず $d_1\gt 1$ だから、 $p\mid d_1$ なる $p\mid d$ が存在して $d/p=(d_1/p)\cdot d_2$ もまた最適な表し方となる。

Fは4頂点あって初めて破綻するらしい。赤の辺でも青の辺でもパスグラフになるような塗分けがある。どうせこれが存在しないことが十分条件でもあるだろうと思ったが、そこから先にはまったく進めなかった。

5完33位。F1は赤の辺と青の辺が必ず存在するという条件を外した状態、つまり2を足したものをOEISに投げると見つかるらしい。FORMULAを辿っていくと $O(n^2)$ の式が見つかって、F1はすぐ解ける。F2も書いてあることを使って頑張ると解けるらしい。

A006351 - OEIS

しばらくTUPCのテスター作業をしていたが遅々として進まない。布団に逃げ込んで午前4時頃ふて寝。

01/25(水)

午前7時半くらいに目を覚まし、うっかり2時間ほどなろうを読んでしまった。

昼過ぎに目覚ましで意識を取り戻す。Classroomの投稿で今日の集中講義がオンラインになったことを知った。「悪天候により」と書いてあって、さてはと思って窓の外を見たら一面の銀世界だった。それはともかくとしてもう一度寝直した。

午後3時前に起床しすぐさま集中講義へ。講義資料が共有されていないのを休憩時間まで言い出せず、前半は内容を見落とさないよう必死に集中していた。資料を手に入れて満足した後半はあまり聞いていなかった。今日は様相論理やクリプキモデルの話で、去年の時点でそれなりに分かったと思っているから余裕をぶっこいていた。実際にはまだ意味不明な話も多いが単位を取るには不足しないだろうと信じている。

集中講義を終えてすぐ布団に倒れこんだが、今日は夜中のCFに備えてしっかり目覚ましをかけておいた。ひと眠りして起きたら午後11時過ぎ。半からCF #846 div.2に出た。

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

Aは奇数三つか奇数一つと偶数二つを使えばよい。判定だけだと思ったら出力も求められて非常に面倒。 $n\le 300$ なので3乗が通るように見えるが、マルチテストケースで $\sum n$ の上限が大きいためそれだとTLEしてしまう。しょうもない罠。

Bは $k=2$ と固定してよいので分割位置を全探索する。

Cは解法が壊れていた。一応問題概要から説明。 $n$ 人の人がいて、それぞれが好む料理の種類が $a_1,\dots,a_n$ で与えられる。テーブルが $m$ 脚あって、それぞれに座れる人数が $c_1,\dots,c_m$ で与えられる。ここで $\sum c\ge n$ である。今から $n$ 人の人を全員テーブルに座らせ、テーブルごとに配膳する料理の種類を一つだけ決める。座っているテーブルに配膳された料理が好きな種類のものだった人数を最大化せよ。 $n,m\le 2\times 10^3$ 。

自分は好む人数が多い種類の料理を座れる人数が多いテーブルに配膳していく貪欲を行った。計算量 $O(m\log n)$ に比べて制約が小さいのがよくわからないが、ともかくこれでpretestは通ったから、想定解も貪欲をしていただろうことがわかる。

しかしこれは大嘘である。コンテスト後に考えてみると、そもそも部分和問題を何回も解くようなケースを含んでいるからまともには解けなさそうだと分かった。結局このコンテストはunratedになり、C問題は後々削除された。

Dは下のbitからどんどん引いていくと操作後の値がわかる。直前のpopcountから1だけ減っていれば、もともとそのbitが立っていて今は立っていないということがわかる。そうでなければ逆。最後に引いた数を足して答える。

Eは辺の重みとして $g$ が現れることと $[l,r]$ に $g$ の倍数が二つ以上存在することが同値。後者の条件は $\lceil l/g\rceil\lt\lfloor r/g\rfloor$ と書ける。ここでうっかりfloor_sumを考えてしまった。sumを取るときに動かす変数 $g$ が分母に来ているので解けない。正解は $\lceil l/g\rceil$ を $O(\sqrt l)$ で列挙すること。ここで $l\le 10^9$ という制約が使える。

Fは選ぶ三つの数のうち最小でも最大でもない値はどうでもよいためソートすると「 $\min=a_l$ かつ $\max=a_r$ の三つ組が $r-l-1$ 個ある」と書けて寄与が分解できる。これで $\min$ と $\max$ がともに何かの倍数であるような場合の数が求められて、あとは約数で包除原理をすればよい。

GはまずSuffix ArrayとLCP Arrayを構築する。最初は同じ長さ $0$ の文字列がSuffix Arrayの $[0,n)$ に出現している状態だと捉え、そこから文字列の長さを増やしつつLCP Arrayを見て区間を区切っていくことで、長さに対して部分文字列が何種類、それぞれ何回現れるかカウントできる。

回数を頻度配列で保存することにしても更新は可能。この配列のうちインデックスが長さの倍数であるような位置について和を取ることで、特定の長さに対してdeliciousな文字列が数えられる。長さを全探索すると配列を見る回数は $O(n\log n)$ になり、十分高速。

全完したがC問題をうっかり通してしまったのはバカ発見器という感じで残念。コンテスト終了直後は4位と表示されていて、その後C問題が削除された結果10位になっていた。

システスについて、A問題をTLEで落とした人が上位にも少しいた。上で言及した罠がpretestに入っていなかったらしい。信じられないくらい性格が悪い。

今日のCFはまた音声入りで画面を録画していた。コンテストは破綻していたがせっかく撮ったので投稿したい。C問題に関してちょっと文章で説明を入れたりしてから投稿した。

www.youtube.com

Universal Cupというコンテストシリーズがもうすぐ始まる。中国で行われたclosedな5hのセットが出題されるらしい。1チーム3人なので参加するためにはチームを組む必要があるが、夏ごろのMulti-Universities Campとは違いOpenCupのSlackで何か募集が行われたり組まれたりはしないらしい。一人で出るには辛そうなので自分から探しに行く必要があった。

「チームどうしようかなあ」のようなツイートを行い、言及を待って突撃するという姑息な方法でチームを組むことに成功した。ぷらさんとかっつさんである。どうぞよろしくお願いします。

1st Universal Cup Announcement - Codeforces

朝までTUPCのテスターをしていた。午前9時に布団に入り、小一時間なろうを読んで就寝。明日の集中講義もオンラインである。

01/26(木)

午後3時前に起床。今日はTAを休んで集中講義に参加する。オンラインだしTAの教室に行くだけなら行けるな……とも考えたが、雪が積もっていて外に出る気にならなかった。

すぐさま集中講義へ、と思ったらZoomリンクが見当たらない。月曜・水曜に使ったものはそれぞれその日時のミーティング専用らしく今日は使えなかった。しばらく待っても音沙汰がなく他の人がどうなっているのかわからない。恥を忍んでClassroomにZoomリンクがないとコメントしたら、先生からは「自分は繋がっているのですが」という投稿があった。

言葉の感じからするに、これは先生しか繋がっていないという意味で、他の誰もミーティングに参加できていないのだろう。案の定Zoomリンクを送ってくれとのコメントがぽつぽつ付いた。しかしそれから実際にリンクが送られてくるまでにはさらに時間がかかり、結局講義が始まったのは予定時刻の30分後だった。

その待ち時間の間に新春TCB2023の賞品を選択した。ちょうど今日の昼前にメールが来ていた。自分に回ってきた時点で何の賞品が残っていたか公開するのはあまりよくない気がするが、自分が何を選んだかはここで言ってよいだろう。トラックボールマウスを選んだ。

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

新春TechFULの商品であるトラックボールマウスが届いた。
週記（2021/03/01-2021/03/07） - kotatsugameの日記

集中講義の話に戻る。今日は様相論理の続きで、これも去年結構頑張って理解したはずの部分である。微妙に書き方が違う気もするが、まあ方言みたいなものだろう。ということで今日は最初から話を聞く気などなく、Zoomに接続だけしておいてこの講義の課題を解いていた。5日間毎日2題ずつ課題が出されていて、そのうち1題ずつに答えるのが期末レポートになる。

話は聞かないとしてもスライドには目を通している。参考文献として井上真偽「恋と禁忌の述語論理」が挙げられていたのが印象的だった。名前はよく聞くが別作品しか持っていないしそれも積んでいる。

午後6時に終了した後準備して外出。徒歩でゲーセンに向かった。TAのために外出するのは気が進まないがゲーセンに行くなら話は別である。

立ち食いそばを食べ、午後7時半から閉店まで4時間ほどプレイした。2週間ぶりなので新曲が結構あり、今日はほぼそれを埋めるだけとなった。

ただし大きな成果も一つ。「TiamaT:F minor」で5アタフルコンを出した。SSS+に少し届かなかったのが残念。実はこれは今日1回目なので、譜面が体に染みついておらず変なところでアタックを出してしまった。

ティアマトフルコン！SSS+寸…… pic.twitter.com/dKeA6j5P1f
— こたつがめ (@kotatsugame_t) 2023年1月26日

油そばを食べて日付が変わってから帰宅。TUPCのテスター作業をしたり、集中講義の先生に質問したいことをまとめたりしたら朝になった。ちなみに明日の集中講義は最後だからと対面の予定になっている。

午前6時に布団に入り、そこから2時間ちょっとなろうを読んで就寝。

01/27(金)

午後2時起床。生協でラノベを受け取りつつ地下鉄で山に登った。午後3時に微妙に遅刻したが、月曜日と同様今日もまだ講義は始まっていなかった。

今日の内容は逆数学と順序数。これは去年の講義では影も形もなかったものである。何も知らないし何もわからない。そのまま講義が終わってしまったので、昨日まとめてきた質問を聞いてから講義室を出た。

ホスフィンに誘われて夕食を一緒に摂り、次の飲み会の日程をすり合わせるなど結構話し込んで帰宅。家に着いたのは午後8時前だった。

今日は生命情報システム科学のレポートの提出期限。最終回である。Classroomの課題ページに期限が設定されておらず、講義スライドを見ないと失敗するのはいつものこと。

今回の課題は、講義で扱ったアルゴリズム・手法・データベースをどれか選んでレポートを書けというものだった。ゲノムアセンブリをグラフを用いて行うとき、頂点を並べる問題にするとハミルトン路を探すことになって難しいが、適当に変形して辺を並べる問題にするとオイラー路を探すだけになって簡単ということが説明されていたので、それについて書くことにした。

具体的には後者が簡単であることを示すつもり。グラフがオイラー路を持つ必要十分条件を示せば量としては十分だろう。十分条件は構成的証明によって示そうと思っている。これだとクラスPに属するというだけでなく実際に単純なアルゴリズムで解けることがわかる点で嬉しそう。

知っている話なので特に何か調べる必要もないはず。楽に書けそうに見えたため余裕ができたと勘違いし、うっかりなろうを読んで2時間弱をドブに捨ててしまった。それから慌てて書き始めた。グラフ理論の話を細かくするのは趣旨から外れるが、日本語だけで説明しようとするとかなり注意深くやらないと不正確になってしまう。説明を考えるのには思ったより苦労した。

さらに今日はCFがあるので、日付が変わるまでの時間をフルに使えるわけではない。午後11時半を目前にしてギリギリ完成し、急いで提出してCF #847 div.3へ。

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

Aはサンプルに30桁の情報があるのでコピペする。Bは最大値が $s-r$ だと決まる。残りは適当に構築すればよい。入力に対して必ず解が存在するという制約が嬉しい。

Cは先頭要素の多数決を取ることで $p_1$ がわかる。そして先頭に $p_1$ が来ていない列が $p_2,p_3,\dots,p_n$ になるため、 $p_1$ をくっつけて出力すればよい。

Dは貪欲に取ってよい。マトリョーシカをサイズの昇順に見ながら、今作っている最中であるようなsetの個数を管理した。

Eは結構時間がかかった。サンプルを2進数に直してみると、どうやら $x$ で立っているbitの一つ下のbitが必ず0なら構築できそう。逆にそうでない場合構築できないことも何となくわかって、出したら通った。

Fは謎。黒く塗られた頂点が増えたら答えも小さくなるだろうと思って、500頂点まではLCAを使って距離を求め、それ以降はdfsで探索するコードを書いたらTLE。そこでクエリ平方分割し、基本はLCAで距離を求めつつ適当な回数ごとにまとめてBFSすることで答えを更新するようにした。これも最初の提出はTLEだったが、BFSで答えを更新しなくなった瞬間打ち切るのと、答えがすでに1のときLCAで距離を求めないのを実装したら、TL 4secのところ2.6secで通った。

Gはちょっと面倒。頂点1から距離1以下の頂点にトークンがあればよい。そうでない場合、トークンの移動先は常にボーナスが置かれた頂点でなければならない。まず、頂点1からボーナスが置かれた頂点だけを通ってたどり着けるトークンを距離とともに列挙した。ただしトークンが置かれた頂点自体にはボーナスが置かれていなくともよいことに注意。

列挙したトークンのうちどれかを頂点1まで持っていくには、その距離から1引いた回数だけ別のトークンでボーナス頂点を踏まなければならない。ここで、辺で隣接するボーナス頂点に1手でたどり着けるトークンがあれば、それでボーナス頂点を往復することで何回でも踏むことができる。そうでない場合も、ボーナス頂点に1手でたどり着けるなら1回だけ寄与できる。これも別に数えておく。

どのトークンを頂点1に持っていくか全探索し、そのたびに先ほど数えた値を差分更新して、必要な回数だけボーナス頂点を踏めるか判定した。グラフが木だと思い込んでいて探索で1MLEしたが何とか通った。

全完31位。Fでかなりしてやられてしまった。Eは $a+b=(a\oplus b)+2(a\,{\rm AND}\,b)$ を使うと $x=a\oplus b=2(a\,{\rm AND}\,b)$ となって、自分がサンプルを観察して得た考察がストレートに手に入る。

Gは頂点1に持っていくトークンは候補が複数あるなら距離が最も近いものとしてよいらしい。距離2なら別の候補によってボーナス頂点を1回踏めばよい。距離3以上なら、別の候補によってボーナス頂点を往復することができてこれまた達成可能。

「黄金の経験値」の続刊が決定したらしくかなり嬉しい。2巻はおそらくちょっと苦しい展開が最初のほうにあるはずで、少し怖がってもいる。

皆様の応援（経済力）のおかげで、二巻の発売が決定いたしました！
ありがとうございます！

男装の吸血鬼っぽい新キャラ……
いったい何ランなんだ（ https://t.co/nEuWTnX77Y
— 原純【黄金の経験値】書籍第Ⅳ巻３月８日発売予定！　コミックも連載中！ (@harajun1001) 2023年1月25日

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

01/28(土)

正午少し前に起きてAHC017に参加し、提出を行った。自分がこの時間に提出を行ったことは順位表からわかる情報である。

THIRD PROGRAMMING CONTEST 2022（AtCoder Heuristic Contest 017） - AtCoder

そのあと食事して日記を書き、午後2時からUniversal Cupの1回目に参加した。Discordで通話しつつHackMDで考察メモを共有する今期のOpenCupと同じスタイルで、ルールも同様コピペ・検索あり、コーディングは同時に一人まで。

今日のセットは中国のICPC由来でShenyang Regional。コンテスト後にQOJにも上がった。

The 2022 ICPC Asia Shenyang Regional Contest - Dashboard - Contest - QOJ.ac

チームでDCAEFLIHの8完。自分はCAEIHを解いた。最終順位はShenyang Regional参加チームも含めて24位。

コンテストが始まってすぐ問題を3等分して読み始めた。先頭から読んでいたところもうDにACが出始めたらしいので、かっつさんに読んでもらったところ、一瞬で通った。その後Cが通されているのを見て、すでに読んだものを改めて考えてみると自明。これもすぐ通った。

しばらくしてAFLが通され始めた。チームメイト二人がFLを考察しているらしい。一応問題概要は読んだが、Lは解けていそう、Fは天才構築に見えて何もわからなかったので、Aを考え始めた。絶対値記号を含む式を二重積分すればよさそうで、端点を集めて区間を区切りそれごとに計算すれば解ける。PCが空いていたので書き始めた。

書き始めてすぐ、積分範囲の点が有限個しかない場合の処理が思ったより面倒なことに気づいたが、PCを空けても使う予定がないとのことだったのでそのまま考え考えコードを書いていた。1時間以上経過してようやく完成。サンプルのほかにいくつかWolfram|Alphaで計算したものも試してから提出。見事一発で通った。

次にEを考え始め、結構すぐに残す橋の本数で包除原理をすることを思いついた。これは偶奇にしか興味がないので、状態数を別のことに使える。まだPCが空いていたので書き始め、頭が混乱したときに2乗の木dpになっていると指摘を受けたりしつつ何とかサンプルを合わせて出したら通った。

その後Fがぷらさんによって通された。相変わらず何もわかっていないので感動。さらにかっつさんによってLが通された。小数の出力なのに判定が絶対誤差 $10^{-9}$ 以下になっていて不安という話をしていたので、真の値が1以下だから相対誤差のほうが値が大きくなり、つまり普通の誤差ジャッジと変わらないということを指摘した。

実装の間にIの考察が完了していた。 $a-b$ の値の昇順に並べると0以下の範囲とそうでないところで購入戦略が変わり、前者はインデックスの $\bmod 4$ を、後者は $\bmod 2$ を見ればわかる。1点更新をどうしようか迷ったがクエリを先読みしておけばセグ木に乗る。ノードに、そこに入っている値の数と、入っている一番左の要素を0番目としたときのインデックス $\bmod 4$ に応じた和を持てばよい。実装したら一発でサンプルが合って、半信半疑で提出したらそのまま通った。

その後は皆でHを考えていた。 $|P|\le|Q|$ とすると $Q$ の一部に $P$ が含まれるので、 $Q$ だけ考えればよい。ユニークな回文は高々 $\sum|S|$ 個しかなく、重複の削除はロリハで行える。そうやって $Q$ を全探索したうえで、まず $|P|=|Q|$ つまり $P=Q$ のケースが一つあり、残りは $Q$ から $P$ を取り除いた部分も回文になっている必要があるので、 $Q$ を回文二つに分割する方法の数え上げとなる。

回文は $\gcd$ っぽいことができたはずだと口走ったらぷらさんからARCの過去問が送られてきた。解説を見るとその通りのことが書かれていてバッチリ。だから $Q$ の回文による周期が高速に求められれば良いことになる。 $|Q|$ の約数 $d$ を全探索しても時間的には問題なさそうで、 $d$ が周期であるかを見たい。

C - 足の多い高橋君

ここで閃いた。 $Q$ の先頭 $|Q|-d$ 文字と末尾 $|Q|-d$ 文字が完全一致すれば、 $|Q|$ は周期 $d$ を持ち、特にこの周期が回文になる。この判定はロリハで行える。誰もロリハのライブラリも回文列挙のライブラリも持っていないようだったので自分が書くことにした。コンテストは1時間くらい残っているが結構ギリギリそう。ペアプログラミングっぽいことをするつもりで画面共有をしてから書き始めた。

まず回文列挙をPalindromic treeを窃盗して行う。それっぽく書き換えたら望み通りのふるまいをしてくれた。ロリハは空で書く。小文字を整数に直すとき、うっかり $0\dots 25$ にマップしていたのを壊れると指摘され慌てて $1\dots 26$ に書き直した。これでとりあえず回文の列挙はできて、周期の判定も行える。

math314.hateblo.jp

あとは $|Q|$ の約数を全探索するだけ。全体で調和級数になり間に合うと思ったがそれには $1\dots 10^6$ に対して約数を前計算しておく必要がある。vectorにpush_backしていたらそれだけで1sec以上かかるらしく、大きめの周期を持つように作ったランダムケースでTLの3 secをギリギリ超えてしまった。

ロリハの法を2種類から1種類にして提出したところ、TLEはしなかったもののWA。実装ミスではなくハッシュの衝突だと信じ2種類に戻して、代わりに約数列挙を $1\dots 99$ まではその場で試すように書き換えたらなんと通った。コンテスト終了17分前だった。ロリハを構造体や関数を用意してきちんと実装したのが後から便利だった。

もう解ける問題はなさそうと終了モードに。全員時間に余裕があるとのことなので、1問ずつ振り返る感想戦をお願いした。自分の分については上に書いたので割愛。

Dはかなり素早く通ったなという感想だったが、問題文を確認すると結構長くてびっくり。どうやらほとんどの部分はLoLの世界大会とプロチームの話をしているらしい。その知識があると読み飛ばせて楽とのことで、分担が思いがけず良かったということになる。

Lは実装担当がかっつさんだったが、考察の初手はぷらさんらしい。1回の攻撃ごとに必ず1体死ぬというもので、結構非自明だと思う。一瞬で出てきたらしくすごい。それにしても早い段階で解けていそうと思ったのにその後なかなか実装されなかったのが気になる。自分がそう思っていると伝えるコミュニケーションが足りていなかったのかもしれない。

午後8時前に解散。食事して午後9時からABC287に出た。

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) - AtCoder

AはとりあえずC++で書いてから、Perlからgrepを呼び出して数えるコードを提出しておいた。Bは愚直に探索。最初に $S$ と $T$ を全部読み込んでから判定しなければならないのが面倒。 $T$ 、 $S$ の順に与えられていれば $S$ は読みながら処理ができるのに。

Cは次数1の頂点が二つで残りが次数2の頂点であることをまず判定。サンプルも合って提出しようとするときにサンプル3の説明画像でループを目にして、グラフが非連結の場合に間違えることに気づいて慌てて書き直した。

Dは $S$ の左右からどこまでマッチさせられるかそれぞれ探索し、その情報を組み合わせればよい。

Eは文字列を辞書順ソートして隣接する文字列のペアだけLCPを計算すれば十分である。LCPの計算も愚直に行ってよい。比較に $\min(|S_i|,|S_j|)\lt|S_i|+|S_j|$ だけかかると評価すれば $O\left(\sum|S|\right)$ だとわかる。Suffix ArrayからLCP Arrayを構築するのにアルゴリズム的工夫を要求されるのは $\sum|S|=N(N+1)/2$ だから。

Fは2乗の木dp。先ほどUniversal Cupでも見たので何を使うかだけはすぐわかり、意気揚々と書き始めたが、実装を終えてサンプルが合わないのに気づいてから部分木の根を使ったか使っていないかも状態に持つ必要があることに気づいた。思ったより面倒。

Gは解法は一瞬だが実装に苦労。得点を先読み座圧してセグ木に乗せ、どの得点のカードが何枚使えるかと総得点を持つ。そういえば座圧セグ木もUniversal Cupで見たばかりか。この上で二分探索することでどの得点のカードまで使うかが判定できる。それより大きな得点のカードは全部使い、足りない分を調整すればよい。得点や枚数の書き換えにちょっと苦労してしまった。

Exは微妙なサイズの制約が気になる。番号が小さい頂点から順番に見つつ、今見ている番号以下の頂点だけを使って行き来できる頂点のペアを管理する。具体的には $N\times N$ のテーブルを更新していく。これはbitsetを使うとワードサイズを $w$ として $O(N^3/w)$ で行える。代わりに、具体的にどのタイミングで行き来できるようになったかがわからないが、これは並行二分探索を行うことで対処できる。これで $O((N^3/w+Q)\log N)$ になった。

1WAを出した。頂点 $u$ を見ているとき、 $s_1\rightarrow s_2\rightarrow u\rightarrow t_1\rightarrow t_2$ というパスを考えなければならない。 $s_1\rightarrow s_2$ と $t_1\rightarrow t_2$ は前に計算しておいたテーブルで、 $s_2\rightarrow u\rightarrow t_1$ は入力されたグラフになる。ところが $s_2$ を抜かして考えていた。サンプルが弱すぎる……。

1WA全完で19位。賞金には遠いかと思ったら上位にそれほど学生がいないようで、ペナがなければ滑り込めていたらしい。

Exは新しい頂点を見るたびにクエリの処理を行う $O(N^3/w+QN)$ でよかった。 $QN$ の最大値を $2\times 10^7$ ではなく $2\times 10^8$ と計算間違いしていた。たとえそうだったとしても通りそうな気はする。さらに、行き来できる頂点のペアのテーブルに更新がある度bitsetの_Find_firstと_Find_nextを使って列挙することで、 $O(N^3/w)$ で全点対間の答えを求められるようだ。

コードゴルフ。AはVimに負けていた。多数決を取るときにソートしてから50%でカーソル移動して真ん中の行の文字列を見る方法があるのは既出だが、そこから答えの出力を分けるのは自分では書けなかっただろう。

BはRubyで、 $T$ をまとめて正規表現のORとして表現しマッチする方針を書いた。しかしその後、判定したい文字列の4文字目以降と同じものが入力された文字列に存在するか見る方針で縮められた。これだと $T$ の判定が必ず失敗するので、わざわざ避けておかなくてよい。

EはRubyで縮めてみたがPerlに負け。文字列のXORを取ってヌル文字を探すことで、先頭からどこまで一致するのか一発で判定できるのがめちゃくちゃ強い。他は手付かず。

今日も音声入りで画面を録画していた。少し編集して投稿。

www.youtube.com

ずっと日記を書いていた。午前11時半就寝。

01/29(日)

午後7時起床。

昨日のUniversal Cup-Hの話で、回文の長さの約数列挙が $S=\sum|S|$ として $O(S\log S)$ に本当になるのかと指摘された。例えば $S/2$ くらいの高度合成数を長さに持つユニークな回文が $S/2$ 種類あるケースはないのか。考えた結果、2種類の回文が交差していたらその部分の文字列があらかた固定されて3種類目が交差できなさそうに見えたので、そういう説明をした。正確な証明はつけられなかった。間に合っているのでヨシ！

布団から出て食事し、午後9時からARC155に出た。

AtCoder Regular Contest 155 - AtCoder

Aから難しかった。昨日のUniversal Cup-Hに引きずられて考察がまとまらない。とりあえず $K\lt 2N$ のケースは真面目に判定できる。 $K\ge 2N$ のケースは $S'$ が周期 $2N$ を持つので、 $K\lt 2N$ のケースと同様に両端の文字列を求め、それが整合するか調べればよさそう。もうちょっと簡単になりそうに見えたがどうにもならないので書き、一発AC。25分くらいかかっていて辛い。

Bも難しい。 $||x-a|-b|$ のグラフがどういう形をしているか調べ、高々4つの区間にある傾き $\pm 1$ の線分として表現できると分かった。この区間と出力クエリの区間の端点を全部混ぜてソートすると、区間の中では右端または左端しか見なくてよい。これは遅延セグ木に乗る。ノードに対して対応する区間の端点を持ち、切片を情報として更新すればよいのだ。

ほんまかと思いながら実装。1WAしたがこれは出力クエリで $a=b$ となるケースだった。対応するノードが1個もないので $\infty$ が返ってしまう。無理やりノードをねじ込んで対処した。結局端点の情報はノードが持っているから、それさえ正しい値なら良いのだ。

Cはスムーズに考察できた。操作が可逆なので、 $A$ と $B$ 両方を何らかの正規形に直して一致するか判定する方針を考えてみる。まず、奇数が1個もなかったり、あっても離れている・偶数が存在しないといった理由で奇数を含むような操作ができない場合は、間の偶数を適当にソートしたもので比較する。ただし偶数が2個以下だった場合は操作できないのでそのまま。

奇数を含むような操作ができる場合、操作を繰り返して奇数要素を先頭に集めることができる。そして今偶数が1個以上あるのだから奇数の隣接swapが可能、つまりソートできる。偶数は2個以下ならそのまま、3個以上あればソートできるので、これらを結合したものが正規形になる。出したら一発で通った。

Dは $G$ を状態として小さいほうからdpすれば答えは出ると思ったが、 $\gcd$ 操作による遷移先を列挙するのが難しい。約数を列挙したり包除原理したりして何とか実装できたと思ったものの、間に合わなかったしそもそもWAだった。

3完75位。Bはやはり想定解ではなかった。コードゴルフは何一つ行っていない。

コンテスト後30分ほどDと格闘した結果03_rand3_*.txtというケースだけ全部落ちるようになり、何もわからないままCF combinedに出た。

Dashboard - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aは $x^y\cdot y+y^x\cdot x=xy(x^{y-1}+y^{x-1})$ と変形。べき乗が嫌なので $x=1$ としてみると $2y=n$ となるから、 $n$ が偶数なら $y=n/2$ でよい。またこの式の値は必ず偶数になるようなので $n$ が奇数の場合解なしだともわかる。

Bは常に $p=1$ としても損しない。 $\sum a\cdot p$ の最大化のためには異なる素数はできるだけ積の形にして $a$ とするのがよい。同じ素因数を二つ以上含まないような数を貪欲に $n$ から取ればその和が答えとなる。

Cは各 $x$ が取りうる値の範囲がわかるが、もし最適解がこの範囲の端点にない $x$ を使っていれば、どちらかの端点に寄せても損しないとわかる。よって $x$ の取りうる値が範囲の左端・右端の二通りとなり、dpできる。

Dは、まずそのままの状態でループするなら、経路の途中からループしない点もしくは範囲外に飛ばす必要がある。ループしない点をあらかじめ数えておいて経路上の点を一つずつ見て足し合わせればよい。そのままの状態でループしないなら逆に飛ばしてはいけない点を考える。これはループする点もしくはループしないとしても今いる頂点にたどり着いてしまう点で、後者は逆向きの辺を張って探索し求めた。

Eは $\bigoplus_{i=1}^n i$ が $k$ の偶奇によって $0$ か $x$ か決まる。これが満たされていると、まず $k-1$ 個の部分列に分け、最後に余ったものをひとまとめにするという方法で構築できる。部分列に分ける際は $[i,x\oplus i]$ という2要素のものしか考えなくてよい。そうでなければ、適切に1要素選んでそれ以外をひとまとめにし、別の部分列の要素と交換することで2要素に直せるから。

Fは大変だった。本当は $a^{2^k}$ を考えなければならないのに $a^{k+1}$ を考えたまま実装まで終えてしまい結構時間を取られた。もともとの $a$ に長さ $l$ のループがあると、 $2^k$ ステップ後には $g=\gcd(2^k,l)$ として $g$ 個の長さ $l/g$ のループに分解されている。

逆に $a'=a^{2^k}$ に長さ $l$ のループが $x$ 個あれば、これを束ねて長さ $xl$ のループを作れそう。最小化すべき値は実はループの個数を数えているので、できるだけたくさん束ねるべきである。 $x$ の条件は $\gcd(2^k,xl)=x$ 、つまり $x\mid 2^k$ かつ $\gcd(2^k/x,l)=1$ 。 $a^{k+1}$ と誤読していたときは約数を見ながらdpしないと最適な $x$ が求まらなくて大変だった。それでも約数が少ないので一応解けはするはず。