2024年5月14日火曜日

Kotlin Heroes: Episode 10

　Fまで六完。またもT-shirts圏に入れず。

コンテスト後のツイート


H. Composite Spells

　各魔法について、その魔法を使ったときのHP増減と、その途中のHP増減の最小値（つまり、最大ダメージ）を持って計算していけばOK。

　コンテスト中この方針で書いたがWAが出て、何が原因か分からず迷走してしまった。

　コンテスト後、解法ツイートを見て、LongをBigIntegerに直したらAC。

　Kotlinって標準で多倍長整数使えると知らなかった。
　Longで収まる範囲の問題しか出ないと思い込んでいたのが敗因。Longで収まると思い込んでいたからoverflowは考えなかった。



時刻: 0 件のコメント:
ラベル: ,

2024年5月13日月曜日

Codeforces Round 944 (Div. 4)

　最後の問題が解けず。


H. ±1

　2-SATという情報を得てAC。

　この前のABCでは2-SATじゃないかと嘘考察してハマったのに、実際に2-SATが出たら解けなかったのは情けない。
　ただ、最初見たとき2-SATは疑ったので、時間があって落ち着ければ解けていたと思う。
時刻: 0 件のコメント:
ラベル: ,

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できたはず。そういうライブラリも持っておきたいね。
時刻: 0 件のコメント:
ラベル: ,

Educational Codeforces Round 165 (Rated for Div. 2)

　Dまで。

コンテスト後のツイート

E. Unique Array

　解説AC。

　このG問題の類題で、似た解法で解ける。

　各要素が唯一である区間を長方形と思って管理するところまでは同じ。その後、それを使って貪欲に処理していく。

　最近解いた問題なのに、コンテスト中も、今復習しようとしたときも全く思い出さなかったのはひどいのでは。
時刻: 0 件のコメント:
ラベル:

2024年5月5日日曜日

AtCoder Beginner Contest 352

　Eまで五完。

コンテスト後のツイート


 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」の和で表すという方法は覚えておきたい。
時刻: 0 件のコメント:
ラベル: ,

2024年5月4日土曜日

Codeforces Round 942 (Div. 1)

　B2まで。CombinedじゃないCodeforces Div. 1はちょっと避けたりしていたけど、今回は参加。レートが落ちず良かった。

コンテスト後のツイート


 C. Fenwick Tree

　解説AC。

　各成分の、k回後に対する寄与が二項係数になるということに気付けなかった。それが分かればすんなりAC。

　なお、コンテスト中考えていた解法だとΣのベキ乗の係数が必要そうになったのだが、その方向でも正しい答えを得る方法はあったらしい（が、理解できていない）。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 943 (Div. 3)

　時間ギリギリ全完でした。

　G2の方針自体はもっと速く思いついていたんだけど、これで計算量が良いかで迷い、またSortedSetを使わなくては実装できないのか？（使ったらTLEするのでは？）　といったあたりでも迷って時間かかってしまった。
　あと、並列二分探索でできないか？　などとも考えた（できなかった）。

　実際に実装してみたらACでした。

コンテスト後のツイート







時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)