No.2758 RDQ
解説AC。なんか、思ったより難しかった。
やれることが約数列挙くらいしかないので、約数列挙して何かしようと思うのは良いが、何をすれば良いか分からなかった。
約数ごとにやろうと思ったら、クエリごとにindexの二分探索で答えが求められるとは気付いかなかった。
titiaのノート
2024年5月18日土曜日
2024年5月14日火曜日
AtCoder Beginner Contest 353
Fが解けず六完。
コンテスト後のツイート
G 「等差数列を加算するセグ木」とかMonotone Minimaとか考えて時間を食ったけど、SortedSetで山の先を管理すればOK。
— titia (@titia_til) May 11, 2024
F - Tile Distance
K=2の場合をケアしてAC。
Kが小さい場合に問題が起きそう、とは思ったから時間があれば解けたと思うので、Gに時間がかかり過ぎたのが敗因。
ただ、K=2の場合をケアしたつもりがWAが二個でてしまい困った。
これは、最初の方にしたK=2の場合は嘘になる考察をコードに入れっぱなしにしていたせいだった。考察に漏れがあったなら、コードも見直さないと。
Kotlin Heroes: Episode 10
Fまで六完。またもT-shirts圏に入れず。
コンテスト後のツイート
E kそれぞれの場合の最小のものを埋め込み、長さnまで伸ばした。
— titia (@titia_til) May 13, 2024
F 連続i個で下にいけるようにしたい→その右上と左下に置く。これは二項係数で計算できる。0の場合は全体から引いた。
H. Composite Spells
各魔法について、その魔法を使ったときのHP増減と、その途中のHP増減の最小値（つまり、最大ダメージ）を持って計算していけばOK。
コンテスト中この方針で書いたがWAが出て、何が原因か分からず迷走してしまった。
コンテスト後、解法ツイートを見て、LongをBigIntegerに直したらAC。
Kotlinって標準で多倍長整数使えると知らなかった。
Longで収まる範囲の問題しか出ないと思い込んでいたのが敗因。Longで収まると思い込んでいたからoverflowは考えなかった。
2024年5月13日月曜日
Codeforces Round 944 (Div. 4)
最後の問題が解けず。
H. ±1
2-SATという情報を得てAC。
この前のABCでは2-SATじゃないかと嘘考察してハマったのに、実際に2-SATが出たら解けなかったのは情けない。
ただ、最初見たとき2-SATは疑ったので、時間があって落ち着ければ解けていたと思う。
2024年5月7日火曜日
yukicoder contest 291
ABの二完。Bで唖然とするようなミスをして、Cも分からぬまま終了……。
No.1478 Simple Sugoroku
自力AC。
ワープを使う場合、「後ろx個へワープで辿りつけたらそこからは歩く」という戦略を取るのが良く、このxを全探索すればOK。
No.1479 Matrix Eraser
フローの練習で解いた。自力でグラフは構築したがTLEが取れず、他の人の提出などを見てAC。
・start→縦でまとめられるもの→(i, j)→横でまとめられるもの→goal
というグラフを考えたが、これだとMLE・TLEしてしまった。
（i, j）の部分は省略することが可能。また、A[i][j]の値ごとにflowを流せば良いので、H+Wの大きさのflowをHW回流す感じで解ける。
こうすればACできた。
ただ、言語とかDinic法の実装とかで工夫したら最初の方針でもACできたはず。そういうライブラリも持っておきたいね。
Educational Codeforces Round 165 (Rated for Div. 2)
Dまで。
コンテスト後のツイート
D heapqを二つ使う。一つ目のheapqにある要素で儲けを出すとし、その要素を無料で与えるとしたときの損失を入れておく。二つ目のheapqにはA[i]の値を入れる。一つ目のheapqから二つ目のheapqへ入れ、二つ目のheapqの要素を常にkにするようにして、答えを計算。
— titia (@titia_til) April 29, 2024
E. Unique Array
解説AC。
このG問題の類題で、似た解法で解ける。
各要素が唯一である区間を長方形と思って管理するところまでは同じ。その後、それを使って貪欲に処理していく。
最近解いた問題なのに、コンテスト中も、今復習しようとしたときも全く思い出さなかったのはひどいのでは。
2024年5月5日日曜日
AtCoder Beginner Contest 352
Eまで五完。
コンテスト後のツイート
AtCoder Beginner Contest 352 Eまで。
— titia (@titia_til) May 4, 2024
A X<Z<Y or Y<Z<X
B 尺取り
C B-aが一番大きいものを最後に。
D SortedSetをお借りしました。
E Cの小さい順に。
F 2-SATで解けそう！ と実装し始めたが上手くいかず終了。あれ、2-SATで解けないの？
F - Estimate Order
解説AC。
重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。
コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。
色々ひどかったけど、2-SATの復習は多少できたかもしれない。
G - Socks 3
解説AC。
・前半の、期待値を場合の数に置き換えるパート
・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート
どちらも典型なのだが、身に着いていない。
どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。
登録:
投稿 (Atom)