はじめに
せっかくバチャ走ったしなんか残しとくか～ というお気持ち
そういえば日本語解説とかあんまりないですよね
Twitterで垂れ流されてるのはよく見るけど記事にまでしてる人見たことないです
バチャの結果は 3ペナ7完 見方がよくわからないんですが67位でしょうか
本文
問題名がリンクになってます
A. Square String?
概要
与えられた文字列がSquare Stringかどうか判定
Square String: 同じ文字列を二回繰り返したもの
解法
$s$ を半分に切って二つつなげたものが $s$ と一致するか判定
偶奇判定はしなくてもどうせ奇数なら一致しない
s.substr(i, k) で $s$ の $i$ 文字目以降 $k$ 文字分の部分文字列 を返します
s.substr(i) と書くと $s$ の$i$ 文字目すべて になります
B. Squares and Cubes
概要
$n$ 以下の自然数のうち, 平方数または立方数である者はいくつありますか？
解法
サンプルを見ると $10^9$ 以下のものは $32591$ 個しかないと書いてあるので全列挙して数えればいい
先に配列に突っ込んでsortしておくと二分探索で数えられる (やらなくても普通に間に合うと思う)
$1$ 以外にも例えば $64 = 8^2 = 4^3$ などが重複するので set や unique を使うなどしてはじくこと
C. Wrong Addition
概要
間違った足し算として, 桁ごとに足した答えを連結する という操作を行う
上記の演算での $a + b = s$ である $a, s$ が与えられるので $b$ を復元してください
解法
下の桁から見て, $a$ の $i$ 桁目 が $s$ の $j$ 桁目より小さければ $b$ の $i$ 桁目はその差分, 大きければ繰り上がりが発生している
その場合, $s$ の一つ上の桁を見て $1$ でなければアウト
reverse して尺取り法みたいに書くのが楽だと思います (そうしました)
D. New Year's Problem
概要
$m$ 個のお店があって, そこから $n-1$ 個まで選んでその中から $n$ 人の友達へのプレゼントを買う
どのお店で誰に買ったときに満足度がいくつなのか が与えられるので友達のなかで満足度が一番低い人の満足度を最大化してください
解法
問題文に二分探索と書いてある (最小値の最大化) ので二分探索を考える
答えを $x$ 以上にできますか？ という判定問題
まず, 当然どの友達に関しても満足度が $x$ 以上であるようなお店が存在しないといけない
また, $n-1$ 箇所しか行けないのでどこか一つのお店で最低二人分買わなくてはいけない つまり, お店で二番目に満足度が高いものが $x$ 以上であるようなお店が少なくとも一つ存在しないといけない
逆に, この二つを満たせば必ず達成できる
これは二分探索しなくても解けて, 答えは $\min$ {好きなお店を選べる時の友達 $i$ の最大値, $\max${お店 $j$ で二番目に満足度が高いものの}}
E. MEX and Increments
概要
数列 $a$ が与えられる
好きな要素をインクリメントする という操作を好きな回数行えるとき, mex を $i$ にできますか という問題を各 $i \in [0,n]$ について解いてください
解法
$i$ の小さいほうから解いていく
まず, $i$ 未満の数字はすべて存在してないといけない 存在しない数字がある場合, 適当な数字をインクリメントすることで用意する必要がある
これは, 余っている数字の中で一番大きいものを貪欲に選べばよい
余ったものを stack などに適当に突っ込んでおいて, 必要になったら取り出してインクリメントの回数を足せば回数がわかる 必要になったが stack が空なら不可能なので $-1$
最後に $a _ j = i$ であるようなすべての $j$ に対しインクリメントすれば mex が $i$ になる
よって, 答えは 今までの合計 と $a _ j = i$ であるような $j$ の個数 の和
合計で償却 $O(n)$
F. Let's Play the Hat?
概要
the Hat というゲームを $k$ 回行う
$n$ 人いて $m$ 個の机がある
それぞれの机は $\lfloor\frac{n}{m}\rfloor$ 人か $\lceil\frac{n}{m}\rceil$ 人集まるようにする
どの二人を選んでも $\lceil\frac{n}{m}\rceil$ 人で遊んだ回数の差が $1$ 以下になるような方法を一つ構築してください
解法
$n % m$ 人があふれるので, $(\lfloor\frac{n}{m}\rfloor + 1)\times(n % m)$ 人が $\lceil\frac{n}{m}\rceil$ 人の机に集まる
人が多い机になる人を毎回ずらしながら割り当てる
実装が下手なのでだいぶ index がややこしい感じになってしまった
G. Unusual Minesweeper
概要
$n$ 個の爆弾があって, 爆発すると爆風が $+$ の字のように各方向に $k$ だけ伸びる 爆風に巻き込まれた爆弾は連鎖的に誘爆していく
各時間に一つの爆弾を選んで爆弾させることができる また, それぞれ $timer$ 時間後に自動で爆発する
すべての爆弾を爆発させるためにかかる時間の最小値を求めてください
解法
爆弾 $i$ が爆発したときに $j$ が誘爆するなら, $j$ を爆発させても $i$ が誘爆する
DFS や UnionFind などを使ってそのような爆弾を一つにまとめて, 自動で爆発するまでにかかる時間は連結成分内の最小値とすることができる
あとはかかる時間が大きいほうから貪欲につぶしていけばいい
最初にまとめるときは map<int, vector<int>> などを使うと楽
$x$ 座標が同じものを突っ込んでおいてソートして $y$ が近ければ辺を張る をすると $O(n\log n)$ くらいの計算量オーダーでできる
H. Permutation and Queries
概要
順列 $p$ が与えられるので, 以下のクエリを処理してください
- $p _ x$ と $p _ y$ をスワップ
- $i = p _ i$ という操作を $k$ 回行った後の $i$ を出力
解法
スワップのクエリがなければダブリングを用いて $O((n + q)\log n)$ とかで解ける しかしこれでは更新ができない
ダブリングの代わりに平方分割で同じことをすると $O((n + q)\sqrt{n})$ になるが, これなら更新できるか？
$i$ の親を $\sqrt{n}$ 回たどる という操作列の中に $x$ または $y$ が含まれるような $i$ は高々 $2\sqrt{n}$ 個なので, これの更新が効率的にできればいい と思ったがいい方法が思いつかなかった
更新以外は こういう感じ でできる
この実装だと更新に $O(n)$ かかってしまう
ここまでしかわかっていません 解けたら追記します
追記 通りました
さすがに頭が固すぎました
$p_x$ と $r_{p_x}$ の更新は $O(1)$ でできるので $pp_x$ ($\sqrt{n}$ 個先の親) について考えます
今回更新しないといけないのは $x, r_x, r_{r_x}, \cdots$ の高々 $\sqrt{n}$ 個です 上の更新を済ませた後に $pp_x$ を愚直に求めた後, $pp_{r_x} = r_{pp_x}$ というように子供を $\sqrt{n}$ 回たどりながら更新すれば $O(\sqrt{n})$ で更新できます ($y$ も同様)
$p_x$ と $r_{p_x}$ の更新を先にやってしまうとなんか $pp$ の更新がうまく行かなそうな気分になっていたのですが, 冷静に考えればそんなことありませんでした
ということでこれで更新が $O(\sqrt{n})$ でできました もう片方のクエリもこの結果を持ちいて $O(\sqrt{n})$ で計算できるので, 全体で $O((n + q)\sqrt{n})$ が達成できました
おわりに
感想としては
- 何も考えてなくてオーバーフローで2ペナ生やした
- H が上記のコードで $O((n + q)\sqrt{n})$ にできていると思い込んで提出連打してしまった
- ↑の間違いに気づいたあと焦りすぎて何もわからなくなった
のでちょっとよくなさすぎた 反省しています
こういう記事は普段はてブの方で書いてるんですが, 数式の書き方がめんどくさすぎてこっちで書きました 次があるかは不明