2024年3月20日水曜日

モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

　Eが解けずABCDFの五完。

コンテスト後のツイート


E - Colorful Subsequence

　解法ツイートを見てAC。

　色の異なる価値の高い二つを持つ（TOP2を持つ）のは典型だし、他の問題では自力で思いついたこともあった気がするのに、この問題では浮かばなかった。
　DPの枠組みの中でやらなくてはいけないから気付きにくいのかな……。

　Fより難しい気がしたけど、解法を見ればEも典型で、Fより前に置いた気持ちも分かります。

　なお、雑にsortを使って書いたらPyPyだとTLE、書き直したら微妙に間違えてWAをなくすのに苦労した。計算時間ギリギリそうなんだから、sortなんて使ったらそりゃダメですね。




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

2024年3月18日月曜日

Codeforces Round 934 (Div. 1)

　問題は解いていたのだけど、提出せず。
　コンテスト後提出したら、A:WA、B:AC、D1:TLE（ちょっと修正してAC）でした。

コンテスト後のツイート


A. MEX Game 1

　自力AC。落ち着いたらすぐACできたが、本番提出してWAが出た後だったらどうだったか。

　C=Counter(A)として、
・C[i]=1となる最も小さいiについて、C[i]=2とする
・C[i]<=1となる一番小さいiが答え。

　相手がスタートだとすると、相手が取ったものを自分が取る真似っこ戦略が使える。
　最初に自分が一手おけるので、C[i]=1のものを、真似っこできるように+1すれば良い。

　



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

AtCoder Regular Contest 174

　ABDの三完でレートを下げる。
　Cは絶対解けなくてはいけない問題だと思ったが、そう思ったのがプレッシャーになってしまったかもしれない。典型ではあるけど、苦手な問題ではあったよね。

コンテスト後のツイート

C - Catastrophic Roulette

　自力AC。

　コンテスト中は、各段階での先攻・後攻の確率（これは求まっていた）に加え、それまでの罰金が遷移に関係すると思い混乱していた。
　確率さえ求まれば罰金を足していけば良いと気付きAC。

　ただ、そう気付き、それなら実装も簡単では？　と実装を始めてからも30分くらいかかってしまった。

E - Existence Counting

　自力AC。

　ある桁がxの数列は何個あるか？　その中で、各数字は何回ずつ現れるかを考えて足し合わせていく。

　考察に詰まるところはなく、実装も、やや時間はかかったものの困るところはなかった。Cを捨ててこっちに集中していれば解けた可能性はそこそこありそう。とはいえ、Cも通せなきゃいけない問題に見えたから、Cを捨てる判断はできなかった。
時刻: 0 件のコメント:
ラベル:

2024年3月16日土曜日

yukicoder contest 421 (NUPC2023)

　AB二完でした。


No.2673 A present from B

　後ろから見ると良いというヒントを見てAC。

　次のように、答えを徐々に更新していく。

・最終手まで見て、そこから配列に何かを付け足すと考えると、最終手の後できている配列のindexにより答えを更新できる。
・その一手前を見る。そのとき、A[x]とA[y]がd個離れているとすると、そこにd個挿入してA[y]をA[x]の位置へ持っていくことができる。つまり、ANS[A[y]]をd+ANS[A[x]]で更新できる。

　以下これを繰り返すと、計算回数N*N*Mになる。解説を見ると、もっと速く解けるみたい……と思って考え直したところ、ここに書いた方法でも累積minを取れば計算量N*Mになりそうですね。

No.2674 k-Walk on Bipartite

　おおまかな方針はあっていたけどWAを取ることができなかった。テストケースを見ながらデバッグしてAC。

　難しい問題ではないけれどコーナーケースを探すのが難しい。コンテスト中にACした人はえらい。

No.2677 Minmax Independent Set

　全方位木DPというタグを見てAC。

　自分の全方位木DPのライブラリをほぼそのまま使えたにもかかわらず実装で混乱した。自分の全方位木DPライブラリが良くないのではないかという気持ちに。

　辺属性のDPと考えているので、UP[x]とDOWN[x]を同じ辺に関する値にしたくて、

・UP[x]:xをROOTとする部分木（xを含み、xおよびxより葉に近い頂点たち）に関する値
・DOWN[x]はParent[x]をROOTとする部分木（xを含まない。xより根を含まない頂点たち）に関する値。

　としていたのだけど、分かりにくくない？

No.2678 Minmax Independent Set (Hack)

　自力AC。これは簡単だった。

　横に1001個頂点をつなげておき、そのうち一個は、一個の頂点がx個ついているようにする。他の1000頂点は、二個連なった頂点がx+2個ついているようにする。(xは適当な数。4とか)

　すると、最適なのは、最初の一個の頂点を選ぶことだが、問題文で与えられた解法では他の次数の高い1000個の頂点の中から選んでしまう。
時刻: 0 件のコメント:
ラベル: ,

2024年3月13日水曜日

yukicoder contest 415

　Dまで。

コンテスト後のツイート


 No.2611 Count 01

　解説AC。

　セグ木を使うとは思ったが何を乗せれば良いか全く分からず解説を見た。
　こういうのを乗せれば解けるのかと結構驚いたのだが、解説を見ながら実装しても30分以上はかかってしまった。速く解けている人はどうやってるのかな。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 933 (Div. 3)

　全完。 あまり速くはなかったけど全完できて良かった。システムテストでG落ちている人が結構いるけど、なんでだろう？

コンテスト後のツイート


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

2024年3月12日火曜日

AtCoder Regular Contest 173

　Cまで三完。レートが上がって嬉しいけど、喜んでいい程の成績でもない……と思っていたけど、ARC/AGCで2200以上のパフォを出したのは去年一回だけだったらしい。なら、喜んでいいかも。

コンテスト後のツイート

D - Bracket Walk

　解説・解説放送を見てAC。
　コンテスト中は迷走していたが、正しい解法は非常にシンプルですね。

　ただ、負閉路判定にベルマンフォード法が使えることをちゃんと覚えていなかった。ベルマンフォード法自体のやり方自体は覚えていたけども……。負の辺があるときの最短距離ではベルマンフォード法を使うというのは覚えていたけれど、負閉路判定にも使えると覚えておきたい。

E - Rearrange and Adjacent XOR

　解説・解説放送を見てAC。

　最後に残る値を実験で求めるパートも難しいし、その後の実装も難しい。
　熨斗袋さんのツイートのように、「偶数個のxorで表せる」というのを、各A[i]に61bit目が立っていると考え、そのbitが0になるような答えを考えるというのが分かりやすいですね。



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