05/01(月)

午後1時半起床。しばらく布団でスマホを触った後、起き上がって購買に行きラノベを受け取ったりパン類を買い込んだりした。そこそこ遅めの時間に行ったのに大量に売れ残っていてびっくり。大型連休を前に学生が少なくなっているのだろう。自分はたくさん買えてほくほく顔だった。

しばらく週記を書いた後午後4時半からインターン先定例会に参加した。先週の進捗は1on1でタスクを確認したのと少し作業しただけ。

勉強会は3DCGの仕組みについてだった。この勉強会のために自分でプログラムを書いてモデルの表示やシェーディング、テクスチャー貼り付けなどできるようにしたらしく、その熱意に感服。特にシェーディングの方法が面白かった。

カメラからスクリーンのピクセルを通して物体を見たときの視線が面と交わる点の色を計算する。このとき面の法線が重要になるが、面に対して一律で同じ法線を使うのではなくいくつか決めた法線からうまく補間して決めることで曲面が再現できるらしい。

解散後、4月の読書記録をツイートした。思ったより多く読んだようだがそれより多く買っていたため積読の増分は大きい。

4月の集計
買った：28冊
読んだ：15冊
積読：+13冊

積読（累積）：+50冊
— こたつがめ (@kotatsugame_t) 2023年5月1日

深夜まで週記を書き続け、午後11時頃に投稿した。それからはずっとラノベを読み続け、午前4時就寝。

05/02(火)

午前10時起床。二度寝を試み布団でずっとスマホを弄っていたがそんな状態で眠れるわけはなかった。午後2時くらいに身を起こした。

DMOJのコンテストが終了していた。5完＋P6の55点を取った中では最速で2位、2897→2987(+90)。ここに感想を書いておく。

DMOPC '22 April Contest - DMOJ: Modern Online Judge

P1は $A$ に $0$ と $M+1$ を追加してソートすれば $\min(A_i+K,A_{i+1})-A_{i-1}-1$ や $A_{i+1}-\max(A_i-K,A_{i-1})-1$ が答えの候補になる。

P2は上下・左右の反転が値を変えず自由に行えるので4通り試す。すると上下または左右に対称な位置に対して同時に $+K$ する操作で $A$ を $T$ にできるか判定する問題になる。右下に値を押し付けるように貪欲に操作してみて一致するかチェックした。

P3は結構手間取った。上下方向に1歩進むのが $h$ 回、左右方向が $w$ 回だとする。 $h=0$ または $w=0$ としたときの答えは適当に計算。 $h,w\ge 1$ のとき、試すと $x\le h+Kw$ かつ $y\le w+Kh$ であればよいことが分かった。 $h+w=m$ と固定すると $\frac{y-m}{k-1}\le h\le\frac{Km-x}{k-1}$ が得られたので、 $1\le h\le m-1$ にそのような条件を満たす $h$ がある最小の $m$ を二分探索で求めた。

P4は区間をstreakが変わらないギリギリまでずらすことを考えると $x$ としては $(t+1)\bmod D$ という形の値だけ試せばよいことがわかる。さらに各 $t_i$ に対し、 $x=(t_i+1)\bmod D$ と定めた時の $t_i$ を含むstreakだけ調べるので十分である。

$t_i$ の先に何日streakが続いているかを計算する。 $i\le j$ で $t_{j+1}-t_j\gt D$ となっている箇所があったときに、特定の範囲の $x$ で $t_{j+1}$ をstreakに含められなくなる。これを「streakが途切れる直前のreviewの候補が $t_j$ である」という情報として保存しておく。現在の $x$ に対しこの候補の最小値を取ると、それが実際にstreakの最後のreviewとなっているため、 $t_i$ との差から日数が計算できる。

あらかじめ $x$ の候補を列挙して座圧しておけば、遅延セグ木の区間chmin、あるいは $t$ を降順に見ながらの区間setで情報を保存できる。 $t_i$ より前のstreakについてもほぼ同様に求められる。最後に足し合わせれば答えになる。

P5はそれぞれの $A$ に対しGrundy数を求める。素因数分解したとき現れる2以上の指数を集めた多重集合に対してGrundy数が定まるので、これをソートした状態でvectorに持ちメモ化再帰した。二つの数に分割する際は、それぞれの指数をいくつといくつに振り分けるかdfsで全列挙。 $\gcd\gt 1$ の条件を満たすためどれかの指数は両方に1以上振り分ける必要があることに注意。

素因数分解のため10⁶以下の素数全部で試し割りしていたのでTLEしたが、高速素因数分解を窃盗してきたら通った。Grundy数の計算については何も高速化しなくていいらしい。

高速素因数分解(Miller Rabin/Pollard’s Rho) | Nyaan’s Library

P6は部分点55点。 $K=0$ については、最初の $P$ の部分列として $N$ で終わる連番をできるだけ長く取り出し、残りを降順に1回ずつ選択すればよい。一般のケースは順列を $P_{1\dots K}$ と $P_{K+1\dots N}$ に分け、それぞれ同様にしてソートした。まず $P_{K+1\dots N}$ 内でソートを試みて、必要な要素がなかったら最小の要素でソートしておく。次はその要素を巻き込みながら $P_{1\dots K}$ 内でソートしてみる。以降交互に繰り返す。

これで最適解の倍以下の手数が達成できたらしく、半分の点が来た。おそらくほとんど最適で、交互のソートを逆から始めたりとかそういう細かい改善があるものと考えている。また順列を二つに分けるのではなく $P_{K+1}$ だけ特別扱いすると左右から見た操作が対称になってやりやすいかも。しかし細かいところまで詰めるのは気力がそもそもなかった。

午後3時前に外出し、まずつけ麺屋で食事した。こんな変な時間でも並んでいて仰天。その後ドラッグストアに寄った後、午後4時から7時間ほどゲーセンで遊んだ。

今日は32クレプレイしたらしい。まず来週に迫った大型アップデートで削除される称号をかき集め、それが終わった後は最近触っていない譜面をいろいろプレイしていた。特に成果はない。チュウニズムデュエルをかなり進めることができて、今回も期間内に終わらせられる見込みが立ったのは良かった。

ラーメン屋に行ったら満員で、相席で食事した。さすが大型連休前の飲み屋街といったところ。日付が変わる前に帰宅した。シャワーを浴びて日記を書き、午前3時過ぎ就寝。

05/03(水)

午後2時くらいに起床。今日はほとんど布団から出ず、ラノベを4冊読んだ。

1冊目、「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」4巻。これでシリーズ完結らしくびっくりしたが、最後まで面白かった。超強力な能力が乱れ飛ぶバトル描写が読んでいて楽しい。

主人公が悪役側に回ったのは目新しかった。3巻の時点でそういう兆候はあって、当時の感想にある「致命的な破綻」が実際に起こったということだろう。4巻冒頭からそうなっていたので、実際には3巻の時点で破綻していたようだ。なんと巻頭のカラーイラストページで主人公の敗北が描かれているから、結局負けるのかと残念に思う気持ちが最初はあった。しかし読んでいくうちにヒーロー側との気持ちの良い関係が分かってきて、最後には納得感のある敗北を受け入れることができた。

外面の順調さとは裏腹に、主人公の考えは良くない方向に先鋭化している。そのうち致命的に破綻しそうで少し怖い。やられ役のセリフにもそういう状態を揶揄するものがあり、そこだけは単純に主人公の無双を楽しむ気持ちにはなれなかった。
週記（2022/10/10-2022/10/16） - kotatsugameの日記

2冊目、「凶乱令嬢ニア・リストン」2巻。これも面白かった。主人公が学院に入学したこの巻はほとんどの部分がテレビ出演パートで、それも面白かったとは言えやはり最後の無双パートが良かった。二つは結構独立しているように見えるのでこれからも交わることはなさそう。キャラが共通する2作品を読んでいる感じだが主人公の態度が好みなので楽しい。

ところでイラストページが存在せず、辛うじてキャラクターデザインが載っていただけなのが不穏。3巻発売も決定しているらしいが今度はどうなるだろうか。

3冊目、「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」4巻。ついに明かされた主人公の過去が重すぎてひっくり返っていた。そこから幸せになるのが絶望的に見えて暗澹たる気持ちになってしまう。しかしさすがにそんなことはなく好調な雰囲気で終わったし、主人公の格好いいシーンもあって満足できた。

4冊目、「なーんにもできないギャルが唯一できるコト」。主人公の大げさなツッコミが古臭く見えて好みでない。しかしラスト、「ネタバレ」と題されて本編中では隠されていた情報がいくつか明らかにされたのには否応なしに興味を惹かれた。こういう引きの作り方もアリらしい。

いつの間にか寝落ちしていた。午前3時は回っていただろうか。

05/04(木)

午前10時前に起床。昼過ぎまでかけて布団でカクヨムを2作読了した。

1作目、「レアモンスター？それ、ただの害虫ですよ～知らぬ間にダンジョン化した自宅で普通に暮らしてました。日常生活を配信したらバズったんですが」。主人公が自身の特異性に一向に気づかない。それでいて世間ではバズっているのだから、かなり都合のいい展開が繰り返された。しかしそうして生まれた認識のギャップはすさまじく、面白かった。

kakuyomu.jp

2作目、「【悲報】現代ダンジョンの最強の中ボスな俺、知らない間にダンジョン配信者達から『あまりに強すぎて笑う』とバズりまくってしまう。」。バズっている部分までは良かったがその後ハーレム方向に進んでいったのはあまり好きになれなかった。ロリと深い関係になるのが受け入れられない。

kakuyomu.jp

食事した後しばらくYouTubeを見て過ごし、午後3時半からHUPC2023 Day 1に出た。ソロ参加。

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2023Day1

最初3問に簡単めの問題が集められており、そこと残りでそれぞれシャッフルされているらしい。よってまず最初3問を通し、その後はsolved数に従って解いていくことにした。結果はABCIFKJHMGをこの順に解いて10完6位。

Aは簡単めと言いつつかなり難しかった。まず $|s|=|t|$ をチェック。手で試すことで $|s|\ge 4$ ならどんな文字列にも変換できることが分かるため、残り $|s|\le 3$ のケースを全探索で処理した。

Bは $A$ 、 $B$ を降順ソートした後、 $A_i+B_j$ が書かれた $N\times M$ のグリッド上を $(1,1)$ からdijkstraっぽく探索して列挙した。

Cはいろいろな方法がありそう。自分が最初に思い付いたのはセグ木に「区間の最小値」と「その個数」を持つ方法だった。

Iはまず愚直に計算することで $O(NK)$ で解ける。また頂点間における寄与をダブリングで計算することで $O(N^3\log K)$ でも解ける。テストケースごとに計算量の小さいほうを実行したら通った。まず $NK\le 10^8$ くらいなら前者のアルゴリズムが適用できて、そうでない場合 $N^2\le 10^{12}/10^8$ より $N\le 100$ が言えて後者が十分高速になる。

Fは一つ目の操作が $x\leftarrow\varphi(x)$ で二つ目がその逆であるから、二つ目の操作を行った後に一つ目の操作を行うのは完全に無駄。よって操作列は一つ目の操作を $n$ 回繰り返してから二つ目の操作を $m$ 回繰り返すようなものとして固定できる。

二つ目の操作は逆から見れば $y$ に対し $\varphi$ を適用していることに他ならない。つまり $\varphi^n(x)=\varphi^m(y)$ が満たされれば $n+m$ は答えの候補になる。 $\varphi$ の適用をある程度繰り返すとすぐ1になるから調べるべき $n$ 、 $m$ の個数は全探索できるくらい少ない。また同時に答えが-1になることがないのもわかる。 $\varphi$ のテーブルは前計算しておく。

Kは指数法則から先手が $A_i$ を選ぶと以降どのようにプレイしても $x=A_i^{\prod_{j\ne i}A_j}$ となる。対数を取り共通する値を括りだすことで $\frac{\log A_i}{A_i}$ を最大化する問題になった。 $\frac{\log x}x$ をWolfram|Alphaに投げたりすることで、3で最大、次に大きくなるのが2と4、その後5以上の数が順番に並んで最も小さいのが1だと分かる。この順序で比較を行い $A_i$ を決定すればよい。

Jは平方分割してbinary trieを持つ。ブロックサイズを $B$ とするとクエリあたり $O(B+N/B\log A)$ かかるので $B$ は大きめにすべき。自分は最初ノードにbinary trieを持つセグ木を書いてMLE、次に平方分割したものの $B=500$ としてTLEした。 $B=2000$ としたら1.5secで通った。

次に解かれていたのがM問題だったので読んでしばらく考えたが、一向にわからない。次の問題に進むことにした。

Hは $N$ 以下のゾロ目数が高々 $9M$ 個しかないため桁数と数字のペアとして列挙できる。このペアを辞書順比較することで昇順に並べておく。その真の値が順に $R_1,R_2,\dots$ だったとしよう。区間 $[l,r]$ に含まれるゾロ目数はこの連続部分列になるが、それが $L$ 番目から $R$ 番目だとすれば逆に $R_{L-1}\lt l\le R_L$ 、 $R_R\le r\lt R_{R+1}$ より $(l,r)$ が $(R_L-R_{L-1})\times(R_{R+1}-R_R)$ 通り存在することになる。

$k=1\dots 9M$ に対し、 $R-L+1=k$ のもとでこの場合の数を足し合わせることができれば答えとなる。これは畳み込みの典型的な応用で、 $R_{i+1}-R_i$ として作った列とそれをreverseしたものを畳み込み、適切な部分を取り出すことで計算できている。

Mに戻ったら解けた。 $i$ 種類目の魚のうち $j\gt A_i$ 匹目を入れるタイミングを $t_{i,j}$ とすると、 $t$ に出現する数が1から連番になっていて $t_{i,j}\gt t_{i-1,j},t_{i,j-1}$ が成り立っていればよい。

ところで $t$ のうち値が存在する部分はヤング図形の形をしており、ヤング図形に先ほどのような感じの条件を満たすように数を書き込んだものは標準盤と呼ばれる。標準盤の数え上げはフック長の公式で行える。このあたりの話は覚えていなかったが、ヤング図形の形をしているのに気づいてそのキーワードでググったらすぐたどり着けた。

Gは大変。 $s$ 、 $t$ 、 $k$ を連結にしようとしたときパスが合流する頂点を $w$ とすると、 $sw$ パス、 $tw$ パス、 $kw$ パスの和が $S$ となる。前二つは $k$ によらないので最後の一つ、より正確には $kw$ パス上の頂点から $w$ を除いたものについて、 $A$ の和を最大化する。 $k=w$ のケースは自明だから $k\ne w$ としておく。

$st$ パス上の頂点 $w$ とそこに接続する辺で $st$ パスに含まれないものを固定し、その先から $k$ を選ぶことで $A$ の和を最大化するということをしたい。すべての $w$ と辺の組に対して $A$ の和の最大値が全方位木dpで計算できるのであらかじめ求めておく。

適当に根付き木にして $w=s,t,\mathrm{lca}(s,t)$ の場合をまず計算する。使ってはいけない辺が高々2本しかないため、求めた値が大きい順に辺を3本も見れば最大値が決定できる。

そうでない場合使ってはいけない辺がちょうど2本存在し、そのうち1本は $w$ から親に向かう辺である。この場合求める値はもう1本の辺 $e$ と対応する。つまりほかのクエリであっても、同様のシチュエーションで辺 $e$ が出現した場合取得すべき値が一致するということ。 $e$ 全体は高々2本のパスをなすから、あらかじめすべての $e$ に対して値を求め辺属性のHLDに乗せておくことで高速に計算できる。

Gが通った時点で残り9分しかなかったが一応ほかの問題にも目を通した。EがGより解かれていたものの最後の制約を見落として何もわからずじまいだった。

www.youtube.com

午後8時過ぎに外出し、ゲーセンに行って閉店までプレイした。今日は14+のAJを三つ出し、チュウニズムデュエルを終わらせた。

「Everlasting Liberty」は特に運指も組まず、前半が揃うまでプレイした。後半は速すぎるので適当にやっても通る。うっかりタップスライドが全部赤くなったりして精度がちょっと悪くなったのは残念。

Everlasting Liberty AJ pic.twitter.com/ZriLc2R3O0
— こたつがめ (@kotatsugame_t) 2023年5月4日

「BUCHiGiRE Berserker」は久しぶりにプレイしたらラストが安定するようになっていて、数回連奏したら出た。これは速すぎるうえリズムが取りにくいので、そこは少し体に覚えさせる必要がある。

BUCHiGiRE Berserker AJ pic.twitter.com/CbVJji4Ozl
— こたつがめ (@kotatsugame_t) 2023年5月4日

「Destr0yer」は今日一番苦労したので達成感もひとしお。中盤のフリック地帯がよくわからないながらもできるようになっていたので、ラストが揃うまで何度もプレイした。そしたら序盤でもアタミスを出すようになって大変だった。

5、8、9小節のフリックは一所懸命擦らないとすぐ抜けてしまう。またそうすると直後のタップなどで赤が出るが、これはもう仕方ない。28、30小節のフリックは片手で、32、34小節ではGoFの蟹のようにして取った。39小節の小粒は直前に振り下ろしエアーがあって手の位置が定まらず、まともに押そうとすると必ずアタックが出てしまう。擦って解決した。

49小節のフリックはめちゃくちゃ速く手を動かさないと抜けてしまう。51、52小節のフリックが直前のタップに隠れているのも嫌らしい。ここも頑張って手を速く動かす。54小節はもう見たまま押した。1敗。

Destr0yer AJ pic.twitter.com/Iw4jshVw5q
— こたつがめ (@kotatsugame_t) 2023年5月4日

立ち食いそばを食べようとしたら祝日のためすでに閉店してしまっていた。代わりに油そばを食べ、日付が変わるころに帰宅。シャワーを浴びてからラノベを1冊読了。

「不敗の名将バルカの完璧国家攻略チャート」。主人公の用意周到っぷりが気持ちよかった。どんな窮地でも安心感を持って読める。ヒロインである王女との両想いな幼馴染という関係もいい。立場的な問題からくっつくことのできない二人ということが最後に語られ、非常に残念に思っていたが、それでも希望も見えるラストシーンだった。

午前3時就寝。

05/05(金)

正午起床。食事して午後1時からHUPC2023 Day 2に出た。今日もソロ参加。今日は並列実装なしというルールなのでソロ参加に優しい。

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2023Day2

Aが一番簡単で残りはシャッフルらしい。Aを解いてからsolved数順に見ていくことにした。結果はABCGEIDHをこの順で解いて8完6位。

Aは $D$ を無視して $\mathrm{lcm}(T)$ を答えればよい。FAだった。すると当然次に解く問題がわからないので、とりあえずBに進んだ。

Bは $\mathrm{round}(-0.5)=-1$ なのがちょっと直感的でない。また誤差という意味でも $\sin\theta^{\circ}=\pm 0.5$ のケースは特別扱いすべきだろう。それ以外は直接round関数に渡しても問題なさそうだったのでそれで答えを出した。しかしWA。手元で試していると出力の0に負号がついている場合があることに気づいた。どうせ出力は $-1,0,+1$ の3種類なので、round関数の戻り値を使って場合分けすることで通した。

CはAの答えが $X$ になるような交点周期 $D$ の組み合わせを数え上げる問題。 $X$ の約数を列挙して $D$ の候補とすると $\mathrm{lcm}(D)\mid X$ となる $D$ が数え上げられる。これを $\mathrm{lcm}(D)=X$ にするためには、 $\mathrm{lcm}(D)$ において $X$ のどの素因数が足りないかを全探索する包除原理が使える。制約の範囲で $X$ の素因数は高々11個しかない。

足りない素因数を固定すると $D$ の候補が変化するが、毎回約数列挙していては間に合わないのであらかじめ列挙してあった $X$ の約数から抜き出してくるのが良い。

Gは同じ行にある角を列挙して距離2にある角のペアを全探索することで桂馬を置くマスの候補が列挙できる。あとはそのマスに角が置かれていないか・利いていないかの判定で、これは $r+c\ne s+t$ かつ $r-c\ne s-t$ で可能。あらかじめ $r+c$ を入れたsetと $r-c$ を入れたsetを作っておけばよい。

同じ行にある角を列番号でソートし、隣り合う角のペアだけ調べるという実装をしてしまった。これは角が三つ以上並んでいるケースで候補を正しく列挙できないが、テストケースが弱かったらしく通った。コンテスト終了後に間違っていることに気づいた。

EはXORだからと最初基底を扱う方針で考えていたが最終的には関係なかった。まず明らかに、 $X\ge v$ のとき $a=v$ とすることで $X\leftarrow X-v$ が行える。また $v$ が奇数で3以上なら $a=1$ で操作することで $X\leftarrow X+(v-2)$ が行え、 $v$ と $v-2$ が互いに素であることから必ず0が作れる。 $v=1$ のときは自明に0が作れる。

$v$ に奇数が存在しない場合 $X$ の下1bitはどうやっても変更不可能なので、まるっと無視してよい。これを $v$ に奇数が現れるまで続ける。 $v$ がすべて0のケースに注意。整理するとこういう説明になったが、コンテスト中はほとんどのケースで $X\leftarrow X\pm v$ ができることから $\gcd(v)$ に注目して考えていた。結構遠回りしてしまった。

Iは四つの文字列の末尾を固定すると考えるdpで数え上げた。こうすると各文字列に含めてよい $s$ の部分文字列がわかり、その各文字は場合の数に $\times 1$ 、 $\times 2$ 、 $\times 27$ のどれかで寄与する。 $\times 0$ が存在しないので累積積を取っておくことで遷移の係数が分離でき、貰うdpが区間和で書ける。

$a$ を固定するループが $|A|$ 回回り、その内側で $b$ 、 $c$ の固定が独立に $|B|$ 回回る。それに加えて $O(N\log N)$ なので結構重く、0.8secだった。

Dはrotateを一般化して置換の合成と見なすとセグ木に乗る。まずクエリ2を区画のswapだと思うことにする。区画ごとに、どんな装置がいつどこに追加されるかを追跡しておき、座圧セグ木を作って装置を追加するたびに全体の積を取得することで、クエリ1を区画に設定された置換の更新として書き換えることができる。その後区画ごとに置換を一つ持つセグ木を作ると更新もクエリ3の取得もできる。

Hは大変だったが面白かった。構文解析パートが非自明。自分は行列式の左上マスを指定すると「行列式の値」「文字列としての高さ」「幅」を返す関数を定義して再帰した。

最初は1行目を端まで読んで行列のサイズを特定しようとしたが、これはうまくいかなかった。右端の判定ができない。そこで、まず $1\times 1$ の行列を読み、次に $2\times 2$ の行列を読み、……と繰り返すことにした。こうすると正しいサイズまで読み進めたところで右端に必ず|が出現するため、判定がうまくいく。

最後、残り45分でFが残った。必要十分条件を見つけて何とかコードを書き上げ残り1分で提出するもWA。そもそもサンプルが合っていなかった。幸い修正箇所はすぐ思いついたものの、書き直してからよくわからなくなって手を止めたところで時間切れになった。直後に考えていることが正しいことに納得がいき、再度提出したら通った。時間がないのだからやけくそで提出しておけばよかった。残念でならない。

見つけた条件は、 $i$ 番目以前に1が存在するとき $A_i\le N-i+3$ 、そうでないとき $A_i\le N-i+2$ というもの。ただし1-indexedである。後ろのほうを手で実験して推測し、小さい $N$ で全探索して確信した。ここから1の位置を固定して数え上げようとした。

1の左右をそれぞれ累積的に前計算しておく。1の右側については右端から使える数を保存しつつ見ていけばよい。使える数の集合は単調に増えていくので、これまでに使った数の個数を引いたものが自由度となり、これをどんどん掛けていくことで求まる。

左側は逆に「使ってはいけない数」、つまりより左の位置ですでに固定されている数を管理する。自由度は最大2なので、そこから個数を引いたものが実際の自由度。ただしこれまでの考察は基本的に右端から値を当てはめることを考えており、最も左にある-1だけは確定するので自由度2だと判定しても場合の数を変化させてはならない。ここがWAの原因だった。

www.youtube.com

しばらくハーメルンを読んで、午後9時20分からyukicoder 387に出た。今日はUnion Findで解ける問題が集まっているらしい。

yukicoder contest 387 (Union Find Contest) - yukicoder

Aはループの個数を数えて $N$ から引くというよく見るやつ。数える方法はいろいろある。自分はUFを使わずループで処理した。

Bはちょっとギョッとした。UFの代表元をsetで管理し、クエリ2に対しては高々2個見て答えればよい。

Cは0から9に対応する超頂点を作り適切にマージしていけばよい。連結成分ごとに答えに0、1、10のどれかが掛かる。これも何となく見覚えがあるが具体的にどれかは思い出せない。

Dはクエリ1とクエリ2で $u$ 、 $v$ の範囲が異なることに注意。すると連結成分が常に区間になるとわかるので、区間をsetで管理するテクで扱える。正確には、 $u$ と $u+1$ が連結であるような $u$ というのがいくつかの区間になっているからこれを持った。この表現によればクエリ1は区間 $[L,R)$ を挿入、クエリ2は区間 $[L,R)$ を削除ということになって綺麗。 $u=v$ のケースなどを忘れていたがサンプルがかなり強くて助かった。

Eはちょっと前のyukicoderでも見た。当時の自分の解法と同様に0・1に対応する $2N$ 頂点のUFを作り適切に辺を張る。連結成分数 $c$ を数えておけば答えは $2^{c/2}$ 。ただし一度 $c$ が奇数になったら以降答えは0になる。

No.2277 Honest or Dishonest ? - yukicoder

クエリ3ではUFを初期化することになるが、どの頂点を書き換えたか履歴を保存しておいてそこだけ戻せばよい。Undo可能UFとは異なり初期値に直接戻すだけでよいので、持つべき値は頂点番号のみで十分だし、経路圧縮も自由にできる。初期化後にこの履歴を削除し忘れてTLEした。

Fは頂点ごとにそれが属する連結成分の代表元までのdistを持ち、この値とUF自体をマージテクで管理した。クエリ1による辺の追加は、重みに適切なdistをXORすることで代表元同士を結ぶのに書き換えられる。クエリ2は $u$ と $v$ が同じ連結成分にある場合代表元までのdistをXORすることで答えられる。

クエリ3はbitごとに分けて考えた。答えに寄与するのは見ているbitが立っているdistのみ。クエリ2におけるdistの計算方法を考えると、代表元までのdistで見ているbitが立っているものと立っていないものの間のdistがそうである。立っているものの個数をbitごとにカウントしておけばよく、マージテクと同時に行える。

Fはクエリ3が難しかったのに対し、Gはクエリ2が難しい。Fと同様にUFをマージテクで管理することにする。異なる二つの連結成分をクエリ1でマージする際、成分間にまたがるようなパスのdistはそのクエリの $w$ と一致する。このことを用いるとクエリ3の答えを連結成分ごとに簡単に管理できる。

クエリ2については、全体を先読みした後頂点ごとにどの頂点との距離がいつ聞かれるか保存しておき、これもマージテクで管理しながらクエリ1によるマージの際に小さいほうを全部見た。頂点集合をvectorではなくsetで持っておくと連結になったかの判定が高速にできる。ここで頂点集合の小さいほうとクエリ集合の小さいほうが必ずしも一致しないことに注意。また $u=v$ を取り除いておくのを忘れ何度かペナを出した。

Hは解けなかった。これまでと同様UFをマージテクで管理する。クエリ1のたびに小さいほうのグラフをdfsすることで、代表元からの距離とLCAのダブリング用テーブルが適切に更新できるから、クエリ2に対しては通常の森であるかのように答えることができる。しかしクエリ3がどうにもならない。木の高さが常に小さいと思い込んで実装してみたが見事にTLEした。

7完最速で6位。

Hを解説の方法でupsolveした。連結成分に対し直径とその端点の組を持っておく。成分をマージする際その辺を通るようなパスで長さ最大のものを知りたい。つまりマージ前の時点で $X$ から最も遠い点と $v$ から最も遠い点を見つけられればよく、実はこれは計算してある直径の端点のどちらかであるから、4通り試せばよい。頂点間の距離を計算するのはコンテスト中のコードで実装できている。

何かすごいことをする・すごいものを持ち出すのかと思っていたらそんなことはなく、直径に関する性質がちゃんと身についていれば解けたということ。少し悔しい。

午後11時半からCF #870 div.2に出た。

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

Aは嘘つきの人数を全探索する。 $l$ が大きい人を優先的に嘘つきにすべきなので、その状態で条件が満たされているかをチェック。 $l$ をソートしておけば高々2個の条件を見るだけでよいが、判定に $O(n)$ かけて全体 $O(n^2)$ で解いても十分間に合う制約になっている。

Bは $a_i\equiv a_{n-i+1}\pmod x$ のような条件が $\lfloor n/2\rfloor$ 個得られる。この条件は $x\mid(a_i-a_{n-i+1})$ と書き直せるので $a_i-a_{n-i+1}$ の最大公約数を求めればよい。 $x$ を無限に大きくできるのは $a$ がもとから回文の場合だが、このとき通常の実装なら最大公約数は0となっているはずで、それをそのまま出力してよいため少し楽。

Cは $n$ の約数で2以上 $m$ 以下のものが存在するかチェックすればよい。毎回約数を全列挙しても間に合うだろうが、自分は10⁶以下の数に対して2以上の最小の約数を前計算しておいた。エラトステネスの篩の要領で高速に計算できる。

Dはtop 3であることを忘れ、区間 $[l,r]$ とその中にある三つのインデックス $l\le i\lt j\lt k\le r$ について $b_i+b_j+b_k-(r-l)$ の最大値を求めることにしてよい。ここで $i=l$ 、 $k=r$ とすべき。 $j$ を全探索すると最大化する値は $b_j+(b_l+l)+(b_r-r)$ とまとめられて、 $l\lt j$ における $b_l+l$ の最大値と $j\lt r$ における $b_r-r$ の最大値を個別に求めて足し合わせることで計算できる。

Eはちょっと難しかった。あらかじめ $r_{1,\ast}$ でソートしておくと、モデルの順番が番号の昇順と一致する。どのモデルを最後に選んだかを状態とし、遷移は毎回 $O(n)$ で試すような $O(n^2)$ のdpを行いたい。この遷移を前計算した。

各モデルに対しそれより前に選べるモデルの集合をbitsetで管理する。都市を一つだけ抜き出したとき、 $r$ でソートし差分更新を行うことでこの集合が $O(n\log n)$ で列挙できる。すべての都市でそれを行い、モデルごとにbitwise ANDで更新していくことで全体 $O(mn^2/\mathrm{wordsize})$ になった。1200ms強かかっているが他の人もそんなくらいなので良さそう。

Fはちょっと面白かった。サンプルを手で確かめると、クエリ2個ではまだ特定できていないことに気付ける。2点の射影がうまいこと一致すれば2手で特定できるものの、それが一般のケースで必ずできるかというと全然そんなことはない。つまり $n=2$ 、引いては一般のケースで、3手は必ずかかるということが分かった。

逆に3手で特定する方法を考えた。まず $X$ 軸と $Y$ 軸を聞くことで点の座標集合が手に入り、点の候補が $n\times n$ 個に絞られる。座標が必ず1以上離れているという制約からこれらの点はそこそこ間隔を開けて分布している。すると、うまく直線の傾きを定めることで $n\times n$ 個の射影が区別できるくらい離れてくれるのではないかという直感が働く。

具体的な傾きはわからないので乱択した。射影を列挙するとこれは直線に乗っているので、ソートして隣り合う点が十分離れていることを確かめる。無事そのような傾きが見つかったら満を持してクエリを投げ、帰ってきた点集合から対応する点を特定し、答えとする。ランダムケースで正答できたので投げたら通った。

システスも全部通って全完3位。動画を投稿した。途中でメールアドレスが映り込んだのでモザイク処理をかける必要が生じ時間がかかった。

www.youtube.com

ハーメルンを読んだり日記を書いたりして午前5時就寝。

05/06(土)

午後0時半起床。午後1時からHUPC2023 Day 3に出た。またしてもソロ参加。今日は並列実装ありに加えコピペに関してICPCルールが適用されておりライブラリを貼ることができないので、三日間の中でソロ参加には一番厳しいルールだと感じた。

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2023Day3

セットの難易度は昨日と同じで、Aが一番簡単、残りはシャッフル。戦略も昨日と同じにした。結果はABDMFKIHJNELGをこの順に解いて13完、優勝。言ってしまえばボス問不在のセットだった。

Aは面倒。正六角形の中に正三角形を描いて座標の変化 $(+1,0)$ 、 $(0,+1)$ に対する重心の変化を求めた。これを愚直に足すと誤差がすごいことになるらしくWA。ちゃんと掛け算をしなければならなかった。

Bは左切り捨て可能素数を実際に列挙する。ミラーラビン素数判定法を写経して__int128を使いつつ計算した。baseはWikipediaを見て17以下の素数を使ったが、これは調べたい範囲に対して決定的にならないようだ。上界をしっかり読んでいなかった。しかし正しい個数列挙できたためOK。

Dは $\log_3|S|$ と $S\bmod P$ の値を状態に持つdp。 $10^{3^k}$ のような値が必要になるが、これも同様に計算できる。

Mは最初何かを全列挙できないか調べていたが、完全に無駄。冷静になるとすぐbitDPが思いついた。

Fは2乗の木dp。部分木の根を選んでいないか、選んだとしてそれを含む連結成分におけるXORが0か1かで3状態あるので、遷移を頑張って書き下す。

Kは考慮すべき $1\le x\le 10^7+1$ すべてに対してMEXを計算した。そもそもMEXは最大 $N$ なので、 $A\bmod x$ が $N-1$ 以下にならない限り考慮しなくてよい。よって $A'=A\bmod x$ を固定し $A-A'$ の約数を列挙することで $x$ の候補を生成した。あらかじめ高速に素因数分解できるよう前計算しておけば、列挙する値は連続する数の約数たちなのでそれほど多くならない。

$x$ に対する $A'$ をbitsetで管理する。 $A$ がそもそも $N-1$ 以下である場合は $A+1\le x$ に対してbitを立てる必要があるので、これは別に管理して $x$ を走査する際に合流させた。MEX自体は「存在しない数」に対してbitを立てたbitsetにおける_Find_firstで高速に求められる。ここを愚直に計算すると台無しなので注意。

Iは $O(1)$ 数え上げ。前半 $N$ 頂点の間には辺はない。つまりこれらの頂点は後半 $N+1$ 頂点と繋がっているが、どれと繋がっているかはdisjointである。ここで前半 $N$ 頂点と繋がっていない頂点が一つだけ存在するか存在しないかに場合分けできる。

前者はまず前半と後半の繋がり方が ${}_{N+1}\mathrm{P}_N$ 通りで、後半だけ見ると $N$ 頂点完全グラフに1点追加したものだから $2^N-1$ 通りとなり、この積。

後者はそれぞれ $\binom{N+1}{2}\times N!$ と $2\times\sum_{k=0}^{N-1}\binom{N-1}{k}2^k$ になる。後半 $N+1$ 頂点のうち2頂点を圧縮し、前半と後半を繋げるのが一つ目の式。後半は完全グラフになっているので圧縮を戻す。すると2頂点の間に辺があるかで2通り、あとは片方の頂点から他の $N-1$ 頂点のうち $k$ 個に辺が出ている場合を考えてこうなった。和の部分は二項定理で閉じた式にできる。

Hは前半のグラフと後半のグラフを何度も行き来するのが損だということに気づけば簡単。前半と後半（の逆辺からなるグラフ）でdijkstraを行い、コストも分解すればそれぞれで最小値を求めて足し合わせるだけになる。

Jは0-indexedの $i\lt j$ について $|A_i-A_j|$ の寄与が $2^i\times 2^{N-j-1}$ であることに注意。 $A_i\le A_j$ とそうでないケースに分けることで絶対値を外し、BITを使って計算した。 $\bmod 998244353$ で足し算する関数とBITの更新をする関数の名前を被らせてデバッグに時間がかかった。

Nは「 $U$ のsuffixであって $T$ のprefixと一致する最長のもの」を状態とし、遷移に関する式を立てて掃き出し法で解いた。必ず解けるかは知らないがassertを入れて出したら引っかからず通ってくれた。

Eはダブリングを2回。1回目のダブリングですべての地点に対し $S_l$ と $S_r$ を求め、移動方向を確定させて、2回目のダブリングで $K$ 回の移動をシミュレートした。

Lはまず札を取り除くことによって得られる点数が机に置いた段階で確定することに気づいた。もう解けたと思ってdpの実装を始めたが $O(N^2)$ で書けてしまい何か怪しい。よくよく問題文を読んで、すべての札を取り除く必要がないと判明した。

しかしdpの状態数を増やすだけで対応できた。机の上には、最初に何枚か最後まで取り除かない札があって、その上にまた何枚かそのうち取り除く札がある。この枚数の組を状態として持てばよい。計算量は $O(N^3)$ で、定数倍が結構よいので問題なく通る。

残り30分でCとGがどちらも0ACで残っていた。まずCを読んだところすぐに2次元BITがあれば解けると分かった。実装に突入しそうになったが念のためGも読んでおくか、と思って見たらこちらもすぐ解けた。実装はGのほうが簡単なのでそちらを先に通すことにした。

Gはクエリ1による辺の区間がdisjointであるという制約がついている。実はここ問題文が怪しいと思っていて、条件を満たすかチェックする対象となるのが「それまでに与えられたクエリ1」と「それまでに実行されたクエリ1」では意味が違ってくる。前者で書いてあるように見えるが、問題設定の自然さに引きずられて深く考えず後者で実装した。結果的には後者の解釈で正解だったようだ。

最初に実行するクエリ1を抜き出したら、辺によって距離が縮む分を区間和で取得したいので、ソートしておいてBITのindexにする。あとはクエリに対して端を場合分けで処理するだけ。

Cは15分遅れで通った。45度回転して2次元BITに乗せ、 $x$ を二分探索する。 $\log$ が三つくらいついているがあまり気にしなかった。クエリ1が値の更新なので以前の値を保存しておく必要があること、座標に初期の値 $M$ がついていることなど微妙な嫌がらせが面倒。 $M$ の寄与についてはオーバーフロー回避が面倒だったので__int128で計算した。

www.youtube.com

しばらく日記を書き、午後8時からUniversal Cup 15回目に出た。今日はHangzhouセット。

The 1st Universal Cup. Stage 15: Hangzhou - Dashboard - Contest - QOJ.ac

書く

朝方まで日記を書いていた。その後ハーメルンを1作読了。「（仮題）とある転生者の異文化体験」。Vtuber、音楽チートなどの要素に惹かれて読み始めたが、実体は男女比が女性のほうに偏った世界におけるハーレムものだった。話が進むにつれその要素がストーリーのほとんどを占めるようになり求めていたものとは異なってしまったとはいえ、これはこれで面白かった。

syosetu.org

午前8時半就寝。

05/07(日)

午後2時半に目を覚ましてずっとなろうを読んでいた。うっかり午後8時半くらいに寝てしまったが、目覚ましをかけていたので何とか1時間ちょっとでの起床に成功。午後10時20分からTROC #32に参加した。15分こどふぉっている。

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

Aはよい。Bは各タイルにいるロボットのスコアが左に連続する白いタイルの枚数になるのが最大で、何回も動かせばそうなる。

Cはまず $A$ の隣り合う要素がすべて異なる必要がある。さらにどこかに相異なる3要素が並ぶ位置があった場合、そこから左右を順に操作していくことで目標を達成できる。そうでない場合明らかに不可能。隣り合う要素がすべて異なる数列は $M(M-1)^{N-1}$ 通り、そのうえで相異なる3要素が並ぶ位置がないものは $M(M-1)$ 通りで、これを引くと答え。

Dはマークされたタイルに対してそこに行けるルーク二つのうち片方だけを残す必要がある。よってこの二つのルーク間に辺を張ると、二部グラフでないなら不可能、二部グラフなら片方の頂点集合が答えになる。

Eは獲る対象とするセクションの区間を考えるとよい。同じインデックスで $x$ 回操作すると連続する $2x-1$ 個のセクションのうなぎを獲れる。なので最初1セクションをコスト $D_1$ 、以降獲り続ける限り2セクションをコスト $D_1$ で獲れるとしてdpした。

ただしこれだと奇数長の区間しか対応できないので、わざと1セクションだけ獲るような遷移も追加しておいた。端だけ何とかすればよいだけかもしれないが、まあこの遷移を増やして過剰に得することはない。

Fはかなり難しかった。スタックに入っている数の偶奇は常に一致する。よって $A$ の偶奇が開き括弧と閉じ括弧のような関係になっており、 $A$ の偶奇に $\pm 1$ を対応させて累積和を取ることでいろいろわかる。具体的にはまず、この値が同じになったタイミングでスタックが空になるので、その間の $f$ だけわかれば右から順に $L$ を固定した時の和が計算できる。

こうやって $f$ を求める範囲を固定すると、その間スタックに入っている数の偶奇が確定する。これを固定すると累積和が一致する点を見ることでどの数がどの数によってスタックからpopされるか特定できるので、それに対応する区間にOR更新を行えば良さそう。

対応させた $\pm 1$ に合わせて累積和が大きい・小さいものから順にこれを行うことで、 $L$ を固定したときスタックに入る要素だけ見て区間ORしたものが得られるから、そこから区間和を取得することで先ほど求めたかった値が求まる。区間OR更新には1ノードあたり $O(\log A)$ かかるので、計算量は $O(N\log N\log A)$ 。1回TLEを出した。

Gはかなり素早く解けた。 $A$ の昇順に並べ替えておき、先頭から順に $A$ と $B$ のどちらを選ぶか決めていく。ある $i$ で $A_i$ を選んだ場合、以降 $B_i$ より小さい $B$ を選ぶことはできない。実はこれだけが条件らしい。

これまで選んだ $B$ の最大値を持ってdpすることを考える。 $B\gt B_i$ なら $\mathrm{dp}_B\leftarrow\mathrm{dp}_B+A_i$ しかできない。 $B\lt B_i$ なら $\mathrm{dp}_B\leftarrow\mathrm{dp}_B+B_i$ が可能なほか、 $\mathrm{dp}_{B_i}\leftarrow\min_{B\lt B_i}\mathrm{dp}_B+A_i$ もできる。これは区間ADD区間MINの遅延セグ木で実家dpにできる。