2023年12月21日木曜日

Codeforces Round 916 (Div. 3)

　Gが解けず。G1を終了二分後にAC。

コンテスト後のツイート

G2. Light Bulbs (Hard Version)

　この解説の方法でACした。

　区間に値を割り振り累積xorを取ると、0のところで区間が完全に分かれるので、最低何個点灯させればよいかは分かる。
　さらに、「同じ値が二個出てくる区間」について考えると、これも他と独立していることが分かるので、そうでない部分のindexの個数を掛け合わせれば良い。

　なお、ちゃんと理解していないが「区間に辺を張るテク」（セグ木を使うもの。検索すれば出てくる）でも解けるらしいので、こちらでも書けるようになっておくべきか。




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

2023年12月20日水曜日

AtCoder Grand Contest 065

　A一完。五連続でレートを落とす。

コンテスト後のツイート

B - Erase and Insert

　後ろからDPというキーワードを見てAC。
　後ろからDPで解けると言われたらそれほど困らずに解けた。

　コンテスト中もまず、後ろから見ることを考えたのになんで解けなかったのだろう？　と思い出してみる。
　Aで詰まったときBを考えていたのだが、前後から見てどう変化するかを手で書いた後、シミュレーションのコードを書いた。その後、Aに戻ってACした後Cへと行ってしまった。

　ということで、「実験コードを書く」という手を動かすことはしたものの、後ろからDPでいけるのでは？　というのは真面目に検討していなかったと思う。

　手を動かすだけで満足せずちゃんと考えていれば解けた気がする。特に、この問題がCodeforces(Div. 2)のDあたりに置かれていたら解いていた可能性が高い。これは自分だけでなく、この問題は、そのあたりに置かれていたらもっと多くの人に解かれるような難易度だと思う。
　AGCだから、と変な心持ちになっていないか。反省したい。

C - Avoid Half Sum

　解説を見てACしたが、どうすれば思いつけるのか分からない。

　実験するしかない気がするが、実験しても分かるのだろうか……。ただ、もっとちゃんと実験すべきだったとはいえるか。
時刻: 0 件のコメント:
ラベル:

2023年12月17日日曜日

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）

 　Eまで五完でさらにレートを落とす。

コンテスト後のツイート

F - Bomb Game 2

　三乗DPはまあまあすぐ分かったけど、遷移の式を見て高速化できない気がして、「別の方針で二乗になるのかな？」と思ってしまった。
　でも自分は三乗しか思いつけなそうだから埋め込みを試みよう、と思ったが思ったより埋め込む個数が多くなりそうで困り、C++へ書き換えたりとかしているうちに時間切れ。

　落ち着いて自分の書いた式を見返せば、確かに二乗に落とせた。
　埋め込みしようとか考えず計算量を落とすことに集中していれば解けた気がしないでもない。

　Unratedで出ているときと違い、Ratedだと雑念も混じってしまうしね……。

G - Nearest Fraction

　解説AC。

　Stern–Brocot木を使って小数を既約分数で近似する問題。知識問題という感じですね。Pythonではライブラリでも解けたようだけど、実装もそれほど難しくない。

　まずleft=[0,1],right=[1,1]としておき（第一要素が分子、第二要素が分母）、mid=[left[0]+right[0],left[1]+right[1]]とrの大小を比較する。
　そして、たとえばmid<xならばleftを更新したいのだが、その際、[left[0]+k*right[0],left[1]+k*right[1]]が条件を満たすような最大のkを求め、それで更新すれば良い。
時刻: 0 件のコメント:
ラベル: ,

2023年12月13日水曜日

Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)

　60位でTシャツ圏内に入れず。悔しい。

コンテスト後のツイート

H. Sum of Digits of Sums

　この問題とかなり似た問題だった。

　似た問題を解いたことがあるとは思ったし、そのおかげで解法も思いつけたのだが、ここまで似た問題だとは思っていなかった。最初に検索したらコンテスト内に解き終ったかもしれないね。
時刻: 0 件のコメント:
ラベル:

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）

　pretest121位→システムテスト118位でした。

コンテスト後のツイート


　解説放送を見たら、理想的な周回ペースとしては1/√dおきに周るものだ、という話をし、それを使っていた。これは金曜あたりまでずっと考えていた内容だったのに、点数が伸びず断念したものだった。思いついていたのに使えなかったのは残念。

　なお、数学的にではなく二分探索で求めた（ので、比率は同じだが、1/√dに比例するとは気付いていなかった）。
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 332

 　Eまで五完。Fが約一分間に合わず。

コンテスト後のツイート

F - Random Update Query 

　非可換な場合の遅延セグメント木をあまり書いたことがなかったため時間をくってしまった。抽象化した捉え方ができておらず、どのノードで何が起こっているか、みたいなことを考えないとできないのが時間がかかっている原因だと思う。ちゃんと抽象化を理解すべきか。

　なお、双対セグ木でも解けるという解法ツイートを見たが、よく理解できていない。自分より上のノードを毎回更新すればできるってことかな？　それなら理解できるが、そういう双対セグ木を書いたことがないので、どっちみち時間がかかったと思う。
時刻: 0 件のコメント:
ラベル:

estie プログラミングコンテスト2023 （AtCoder Regular Contest 169）

 　AB二完で青に落ちる。

コンテスト後のツイート


 C - Not So Consecutive

　解説AC。

　コンテスト中は、DPでやるなら「各数字iについてj回連続しているvalidな個数」を各indexについてもたなければいけないから無理そう→包除原理を使うのでは？　と考えていた。
　実際包除原理でも解けたらしいが、自分の実力では難しそう。

　ただ、DPで解けたかというと、解説を見て、DP[i][j]をindex iでjで、index i-1でjでないvalidな個数、DP2[i][j]をindex iでjなvalidな個数としたとき、

・DP2[i][j]がDP[l][j]+DP[l+1][j]+...+DP[i][j]という形で表せる

　というのを見て全く意味が分からず十分以上考えてしまったくらいだから、思いつけた可能性は低そう。
　ある数を連打しているときは、その個数は変わらないのですね。言われてみれば確かにそう。

　そして、その後の実装も苦戦した。

　DP2[i][j]を累積和で表したいが、その途中に-1でもjでない数が現れていると、そこまでの和にしなくてはいけない。なので、最後に-1でない数字が表れたindexを二つ保持しておく必要がある（と思うけど、解説に言及されてないし、ここに気を配らずにやる方法があるのか？）。このことになかなか気付けなかった。

D - Add to Make a Permutation

　解説AC。

　解説を追うこと自体は難しくないが、条件を整理・きちんと立式することが求められている気がした。理解して実装したつもりが答えがなかなか合わず、自分でもう一度式を整理し書き直してAC。
　しかし、実装に中国剰余定理が必要になったりしたが、本来の解答では使っていなさそうなので、まだ何か勘違いしているのかも。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)