antino

競プロとか数学とか
AtCoder: 茶 水色を目指してゆるりと
競技用にはC++だけど、Juliaも学びたい

2024/04/13 初のABC(ABC349)
2024/05/25 茶入り(ABC355)
2024/06/30 緑入り(ABC360)

[antino @antinoki]

ABCのことを思い出すこともなく土曜夜に予定入れちゃっててまずい．そんなつもりは全くないのに実質的にモチベが低い．

[antino @antinoki]

今日もしかしてABCだったか？

[antino @antinoki]

てか実行制限4secじゃん！？(どの程度解法に影響してくるか知らんけど)
気づかなかったので2secじゃなかったら強調してくれるスクリプト入れよ

[antino @antinoki]

D問題の解説，言われてみればそうだわ...

[antino @antinoki]

#ABC370 3完して椅子ぬくぬく
A B C よし
D これ何かの典型なんですか...？行(列)ごとに空間の左(上)端と右(下)端を管理（例：v[1] = {1, 2, 4, 6}なら1行目で壊れている列は1, 4, 5のみ）する方法しか思いつかないが，insertの時間計算量が不安(しかも書けない)

[antino @antinoki]

配点的にEを解くまでの時間が大事になってきそうね

[antino @antinoki]

#ABC370 でます

[antino @antinoki]

imos法で済むところを「区間加算だからセグ木だ」と飛びついちゃう．1次元ならさして問題はないのだろうけど

[antino @antinoki]

しかし結局は「次にどのコイン(もしくはゴール)に到達するか」だけでいいから区間更新は必要ないのね．

[antino @antinoki]

Fは区間最大値更新・区間最大値取得にすると最大コイン数は求められるけど，経路を復元するのは難しそう

[antino @antinoki]

#ABC369 5完1ペナ
A B よし
C dp[i]を「長さ2以上，末尾がA_{i+1}の等差数列の個数」としてdp
D dp[i][j = 0, 1]を「i体目まで(j ? 奇数 : 偶数)体倒しているときの最大経験値」としてdp
E ワ―シャルフロイド後，橋の通り方をk!*(2^k)通り全探索
F 行を遅延伝播セグ木とみて区間加算・区間最大値取得？

[antino @antinoki]

自分の解法も実質的には最長広義単調減少列を求めていることを考えると，セグ木の作り方の差異がどこからきているか気になるけど，自分の木は「(r, c)から初めて最大何枚か」を全列で更新していっているのか．

[antino @antinoki]

もしかして橋の渡り方はbit全探索できるのか？
解説にある動的計画法も考えたいが

[antino @antinoki]

Eの全探索はABC345 D問題 - Tiling (https://t.co/HJoaHxNstw)で似たようなものを書いてたからやりやすかった！
Eの実装で手こずったのと，FのHとWの制約を見間違えて左上から全マス見ていく解法を書いてて時間が足りなかったのが敗因かな．
Dまで早く書けたのは良かった．

[antino @antinoki]

今更だけど，Dの当初の解法はvector<int>をいちいちコピーしてたからO(N^2)になってたっぽくて，実際参照の&つけたらACした...
関数の引数につける以外の用途を久しぶりに思い出したわ

Eの解法は別解として挙げられてるやつかな？level ancestorが高速に求められるからいけるらしい．

[antino @antinoki]

最初はMで割った余りごとにiを格納してlower_bound等で数えるO(N logN)(たぶん)の解法で提出したがTLE。その後、LISを求めるように余りごとに数えていって(平面走査？)O(N)でAC。
E 置換のサイクル分解かと思いきや単射じゃない..。functional graphのサイクルを見つければいいのかな？

[antino @antinoki]

Eの全探索はABC345 D問題 - Tiling (https://t.co/HJoaHxNstw)で似たようなものを書いてたからやりやすかった！
Eの実装で手こずったのと，FのHとWの制約を見間違えて左上から全マス見ていく解法を書いてて時間が足りなかったのが敗因かな．
Dまで早く書けたのは良かった．

[antino @antinoki]

#ABC369 5完1ペナ
A B よし
C dp[i]を「長さ2以上，末尾がA_{i+1}の等差数列の個数」としてdp
D dp[i][j = 0, 1]を「i体目まで(j ? 奇数 : 偶数)体倒しているときの最大経験値」としてdp
E ワ―シャルフロイド後，橋の通り方をk!*(2^k)通り全探索
F 行を遅延伝播セグ木とみて区間加算・区間最大値取得？

[antino @antinoki]

#ABC369 でます(忘れてた)

[antino @antinoki]

こっそりセグ木の勉強とか、D問題程度の難易度を早解きする練習したりしてる

[antino @antinoki]

最近、だいたい隔週でABC直前に現れて所感をポストしていくだけの人間になってる

[antino @antinoki]

最初はMで割った余りごとにiを格納してlower_bound等で数えるO(N logN)(たぶん)の解法で提出したがTLE。その後、LISを求めるように余りごとに数えていって(平面走査？)O(N)でAC。
E 置換のサイクル分解かと思いきや単射じゃない..。functional graphのサイクルを見つければいいのかな？

[antino @antinoki]

#ABC367 なんとか4完
A B よし
C forループを8個書くか一瞬迷った。繰り上がりをさせながらシミュレーションした。
D d[i] = (1からiまで時計回りで歩いた時の歩数) とすれば
(i<j かつ d[i] = d[j]) または (i>j かつ d[i] = d[j] + (1周))
となる(i, j)を数えればよい(等号はmod M)。
↓続く