ジョギングした。2.5km。おととい腕立て伏せをした影響が残っているのか、肩が痛くなった。
今日解いた競プロの問題。
ARC148-C: ある1頂点のコインだけを裏返す方法を考えると、その頂点のボタンとその頂点の全ての子頂点のボタンを押せば良いことが分かる。この手続きを適用すれば「達成不可能」という場合はありえないことが分かる。
実際に必要なボタンを押す回数を考える。先述の操作を愚直にやると同じボタンを2回押す場合が出てくるが、2回押すのは押していないのと同じなので、各ボタンについて押した回数のMOD2をとって総和を取れば良い。
これだと正しい答えは出るが$O(NQ)$となりTLEしてしまう。そこで、子頂点の数を一括で足してしまうことを考える。こうするとMOD2をとるくだりが問題になるが、そもそもある頂点のボタンを押す回数は「その頂点を裏返す操作で押されたとき」と「親頂点を裏返す操作で押されたとき」で最大2回しかない。ある頂点を裏返す操作をするとき「親頂点を裏返す操作があるか」を判定することで2回目かどうかを判定することができ、その場合は操作回数を+1する代わりに-1すればよい。頂点集合$S_i$をsetなどで管理すればこれは$O(\log M)$などで判定できる。以上で全体$O(\sum M_i\log M_i)$で解けた。
新サイトのデザインがだいたい完成した。シンプルさを求めた結果、なんかちょっとサイト内で導線不足になっている感じはするが、記事シリーズを読むのに不自由しなければそこまで問題はないはずだ。
あるシリーズを順番に読んでるときに急にトップに戻りたくなる、みたいなのはそうそうないはずで、戻ろうと思ったときに探して見つかるならそれで十分だろう。
あとは中身を移し替えていく作業だ。Vulkan入門はちょっと手直ししたい部分も多分にあるのでそれも兼ねて。
久しぶりにファーストキッチンに行った。スパイシーチキンというのがあったので試してみたが、思ったよりちゃんと辛かった。
この間マクドナルドに行ったときは噂通りの紙ストローが出てきて辟易したが、ファーストキッチンは違うらしい。
ABC280に出た。
A: 数えるだけ
B: 差を取るだけ
C: $S_i \neq T_i$なるiを探すだけ。$i=|S|$までそのような$i$が無ければ$|S|+1$とすればよい。
これが通るのは分かるのだが、最初に血迷って書いたランレングス圧縮したうえで何かやる感じの回答がWAになる理由が分かっていない。
D: 倍数の話をしているのでまずKを素因数分解して$\prod p_i^{k_i}$の形にする。各素数$p_i$について、$N!$に$p_i$が$k_i$個含まれるような最小のNが求まる。これは単調性があるので二分探索で求めるのが良い。また単調性があるので、全てのNのmaxを取ればそれは条件を満たし答えになる。
N!にpがk個含まれる最小のNを求める処理がパッと思いつかず、適当にこんな感じやろ！で書いて2WA。雑すぎる。
E: 期待値DP。とっさにやり方が思い出せず、EDPCのSushiの解説記事を見た。期待値DPが出るたびにSushiを見ている気がする。
dp[i]=(残りライフがiのときに残り必要な攻撃回数の期待値)と置いてあとはやるだけ。
F: ポテンシャルを決めれば各クエリ$O(1)$で出来そうだなというのが分かる。道は双方向で、交通費が切れて動けなくなるみたいなルールもないので、連結性はUnionFindでも使えばよい。
ポテンシャルを決めるにはとにかく片っ端から決めてしまえばよい。ポテンシャルは差のみが重要なので、基準は位置も値もどうでもいい。片っ端から決めていって全ての道路を見分した結果、辻褄が合わない部分が出れば負閉路/正閉路があることが分かる。この問題の設定上、負閉路があればそれを逆回りすることで必ずポイントを無限に増やせるので、負閉路か正閉路かは問題にならない。連結でありさえすればそこには移動できるので到達可能性を深く考える必要もない。
ということで、各連結成分についてポテンシャルを片っ端から決めて、無限に増やせる閉路があればそれを記録し、各クエリでは非連結ならnan、連結成分内に閉路があればinf、そうでないならポテンシャル差を出力する。
C,D問題が適当すぎて3WAも出してしまった。落ち着いてやれば余裕で黄perfが狙えたはずだ。
今日摂取したコンテンツ。
https://zenn.dev/ryo_a/articles/d659f887c3957c
Discordの「ツ」の話。この話題自体は把握していたし技術的な背景もだいたい理解していたが、言語と国旗の話とか、あと合字という解決法の話はなかなか興味深かった。
Categories: 未分類