仮のブログ

仮です

Codeforces Round #218 (Div. 2)(バチャ), Codeforces Round #392 (Div. 2)(バチャ), Codeforces Round #903 (Div. 3)(本番参加)

バチャ記録再開

Codeforces Round #218 (Div. 2)(2023/10/11)

A: K-Periodic Array

\mod k 毎に出現頻度を数え, \min を足し上げればよい. https://codeforces.com/contest/371/submission/227629368

B: Fox Dividing Cheese

\gcd にするのが最適. 後は愚直に 2,3,5 で割ればよい. 読解にちょっと時間がかかった. https://codeforces.com/contest/371/submission/227629873

C: Hamburgers

二分探索して予算内に作れるか判定する. 場合分けとかを頑張れば二分探索が不要そう.
https://codeforces.com/contest/371/submission/227630478

D: Vessels

いっぱいになっていない容器の番号をsetで管理しておくと, 水があふれた場合どこまであふれるかが高速で求まる.
一回の注ぎで探索する容器の数の総和は高々 N+M 個.
https://codeforces.com/contest/371/submission/227631040

E: Subway Innovation

座標が連続した駅を選ぶのが最適.
コストの総和を毎回計算するとTLEなので上手く差分を更新していく.
最初駅がソートされてると思いペナ. https://codeforces.com/contest/371/submission/227632389

総括

29分全完1ペナ2位. 短時間で走るために簡単そうな昔の回を選んだら思ったよりも簡単でさくっと終わった.

##Codeforces Round #392 (Div. 2)(2023/10/11)

A: Holiday Of Equality

\max との差分を足し上げる.
https://codeforces.com/contest/758/submission/227678230

B: Blown Garland

周期4となるので, 各箇所が何になるべきかが確定する. よって, 各 ! を何にすれば良いか分かる.
https://codeforces.com/contest/758/submission/227678848

C: Unfair Poll

指名は M(2N-2) 周期( N=1 の時は若干違うので場合分けをするが方針自体は同じ). よって, 大体何回当たるかをこれで求めて置いて, 端数はシミュレートすればよい.
https://codeforces.com/contest/758/submission/227680096

D: Ability To Convert

下の位から, 貪欲に今見ている桁の数に含められるかを判定し, 含められなくなったら桁の値を確定する.
例えば, 問題文中のサンプルなら,

  1. 16^0 の位を 11311 と出来るか? →出来る.
  2. 16^0 の位を 11311 と出来るか? →出来る.
  3. 16^0 の位を 11311 と出来るか? →出来ない. 16^0 の位の数は 11 で確定.
  4. 16^1 の位を 11311 と出来るか? →出来る.
  5. 16^1 の位を 11311 と出来るか? →出来る.
  6. 16^1 の位を 11311 と出来るか? →出来ない. 16^1 の位の数は 13 で確定.
  7. 16^2 の位を 11311 と出来るか? →出来る. これが最上位なので, 16^2 の位の数は 1 で確定.

といった感じ. 但し, 各位の数の最上位が 0 とはなれないので, この場合は判断を持ち越すといった処理が必要. 判断を持ち越す場合に判定用の数がオーバーフローしないように注意.

https://codeforces.com/contest/758/submission/227683837

F: Geometrical Progression

Fの方が得意な見た目だったのでこちらに特攻.
項数と各項の範囲が与えられるので等比数列としてありえるものの数え上げ.
まず N=1,2 の場合は簡単なので別途処理をしておく.
そうでない場合, 初項を a, 等比を互いに素な正の整数 p/q と表すと, q^{n-1}\mid a である必要がある.
よって, q の取りうる候補は O(R^{\frac{1}{n-1}}) 個.
おのおのに対して, a の取りうる候補は O(R/q^{n-1}) 個.
おのおのに対して, p の取りうる候補は O((Rq^{n-1}/a)^{\frac{1}{n-1}}) 個.
互いに素の判定の前計算などを適切に行えば, これらを全て走らせても間に合う. (計算量がどれくらいかは不明)

https://codeforces.com/contest/758/submission/227690236

E:

間に合わなかった.
以下はあっているか不明だがバチャ中に考えたこと.
各枝について, 部分木の重さを最大まで減らした場合に, 自身の重さをいくら減らせるかを持たせる.
部分木の重さを減らしたくなったら葉に近い方からボトムアップに重さを上で求めた値まで減らす.
この際, 部分木の重さを減らし切った頂点があれば, その頂点も重さ減らし候補に新たに加える.
これを木DPで行うわけだが, 遷移の際に今見た部分木のどの辺の重さを減らせるかというのを持たせなければいけない.
この情報のマージにはマージテクを行えばよい.
持たせる情報や遷移に気を遣っていたら時間が足りなくなってしまった.
解説の計算量だけみたら O(n) とあったのでもっと賢い方法がありそう.

総括

5完16位. 点数差があったこともあり, F特攻が正解だった.

##Codeforces Round #903 (Div. 3)(2023/10/13)

A: Don't Try to Count

n,m がやたら小さいので, 適当な回数操作をして判定をすれば良い. 回数適当にしすぎてセルフhack出来てしまった 上手くやれば O(|T|) とかで解けそう.
https://codeforces.com/contest/1881/submission/227830383

B: Three Threadlets

雰囲気で最大のものから最小のものを切り出すのが良さそうで, 雰囲気でコーディングして, 雰囲気でペなって, 雰囲気で直して雰囲気でAC.
2つに分けた数の片方しか現状の数の集合に戻していなかったのが原因.
https://codeforces.com/contest/1881/submission/227834613

C: Perfect Square

回して数えて足し上げる.
https://codeforces.com/contest/1881/submission/227839248

D: Divide and Equalize

総乗が n 乗数となる事が必要十分. そのまま総乗はもてないので素因数分解形で持つ.
https://codeforces.com/contest/1881/submission/227841811

E: Block Sequence

DP \lbrace n\rbrace: n 項目をブロックの末尾にする時に消す数の最小値としてDPを回す. 今見る要素を使わないか, ブロックの先頭にするかの選択肢がある.
ブロックの中身を考えないために, ブロックの先頭に使う場合はブロックの末尾へDPを配る.
https://codeforces.com/contest/1881/submission/227845455

F: Minimum Maximum Distance

ぱっと見で二分探索がしたくなったがうまくいかず, さすれば全方位木DPかと思ったがこちらもパットは上手くいかず.
また, メタ的思考だがこの位置に全方位は出なさそう. よって考察不足な感じがするが分からなかったので一旦Gへ逃げた.

G: Anya and the Mysterious String

典型の組み合わせといった感じ?

典型1. 部分文字列に回文を含むかは高々長さ3の部分文字列を調べればよい.
典型2. 区間に対する加算操作は差分をとれば2点への加算/減算操作となる.

を用いる. ある文字をほぼ中心として回文が存在するかというのは差分の高々2要素をみればよい.
よってどこに回文があるかを, 一点更新, 区間和取得ができるデータ構造でもてば, 各変更クエリごとに数要素変更すれば事足りるようになる.
https://codeforces.com/contest/1881/submission/227883585

F: Minimum Maximum Distance

Gがさっくり解けたので安心して戻ってきた.
冷静になると何も難しいことは問われておらず, ほぼ木の直径を求めるだけで良い.
ざっくりとした言い方をすると, 印のついた頂点の内側(上側?)だけを木と思って直径を求めれば良い.
https://codeforces.com/contest/1881/submission/227893145

総括

全完1時間20分2ペナ70位.
Fの一回目でかなり時間を取られたのがもったいない.
数十分悩む暇があったらGを先に観るべきだった.