ラベル ダブリング の投稿を表示しています。 すべての投稿を表示
ラベル ダブリング の投稿を表示しています。 すべての投稿を表示

2024年9月9日月曜日

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）

　Eまで五完の上、ペナルティをたくさん出してまずい。

コンテスト後のツイート

F - Cake Division

　解説AC。

　二分探索するのは分かるが、全点から試さなくてはいけなそうで、どうすれば良いか分からなかった。コンテスト中はそこを高速化することは思いつかず、全部試さなくてもいくつか点を試せば良いのかなぁ、というのを提出してWA。
　ダブリングで高速化できるのはなるほど、でした。

　あと、コンテスト中は、全点を試す→二分探索の順番で考えていたことも思いつかなかった原因かも。順番を変え、二分探索→全点を試すで考えるのが重要だった。

　結構難しいが、以前、類題を解いたことがあったことを考えると解けなくてはいけない問題だった。


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

2023年7月18日火曜日

freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）

　Fまで六完。

コンテスト後のツイート

G - Takahashi And Pass-The-Ball Game

　解説を読んだけど、ダブリングの解法がすぐには理解できず、解説放送も参考にしてAC。

　ダブリングでいけそうということは分かっても、実装するのが難しい問題だった。
　ダブリングでさくっと求められるのは、「xさんのボールがy回の操作後どこにあるか？」だが、ダブリングの途中で二回の操作を一回にまとめていかねばならないため混乱しやすい。

　ダブリングをこういう風に使ったことがなかった気がするので、ちょっと新鮮だった。

　コンテスト中は行列累乗なんかを考えたりしていて的外れでした。

Ex - Negative Cost

　解説放送を見てAC。

・ナップザック問題で重みが大きいときどうするか？

　という問題の解法を知っていないと解くのが厳しかったと思う。
　最大効率に着目するのは直感にも合致していて、確かにそうだな、という感じ。

　この問題に帰着しようと思えたのなら、帰着する部分は思いつけなくはなさそう。


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

2022年6月5日日曜日

AtCoder Beginner Contest 254

　Fまで六完。

コンテスト後のツイート

G - Elevators

　解説放送を見てAC。

　確かに一つ一つのステップは典型なので難問ではないと思うが、実装は非常に大変。

　特に、

・各ビルについてのエレベーターをマージする
・ダブリングするために、エレベーターをまとめ、使う必要のないエレベーターは削除

　をする際、どう処理すべきかで迷った。

　両方、低い階の方でソートする（これも、区間スケジューリングが頭にあると、高い階でソートしたくなり間違う）のだが、その後の処理は少し違う。（後者ではマージするわけではないので）

　時間をかけられ、また、サンプルが強ければ解けなくてはいけない問題だろうが、今回解き切るのはかなり難易度が高かったのでは。

　さらに、ダブリングの実装でミスり、デバッグにかなりの時間を要したのは良くない。ダブリングは大きいステップで行けるかどうか調べて（つまり、1<<i進むこのiを大きい方から見る）更新していくのが良いのですね。なるほど。

Ex - Multiply or Divide by 2

　大きい方から貪欲にやれば良いということにはコンテスト中に気付いたが、Bについては、(2x+1)→xの遷移ができないことに気付かず。
　惜しかった。


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

2021年8月18日水曜日

AtCoder Beginner Contest 212

　Eまで五完。


F - Greedy Takahashi

　解説動画を見てAC。
　コンテスト中はGの方が解かれていたため飛ばしてしまったが、発想が難しい問題ではなかった。

　ただ、実装は結構しんどいね。
　あまり綺麗な実装を思い付けず、添え字でもミスってしまった。他の方のコードを見てこういう実装も勉強すべきかなぁ。

　→　ダブリング解法だと実装がある程度大変になるのは仕方なさそう。
　

G - Power Pair

　解説AC。
　解説の論理は理解でき、ACはした。が、しっくりきてないので解説動画を見たい。

　→　結構すっきりしました。

H - Nim Counting

　すぬけさんの解説動画を見てAC。
　ただ、アダマール変換については理解できていない……。

　とりあえず、

・愚直なDPによる解法
・xor畳み込みにより高速化できる
・アダマール変換の線形性を利用すると、等比数列の積の公式などを利用して計算できる。（線形性の証明は分かってないけど、定義から成り立ちそうな気はした）

　というあたりは分かった。

　分かっていないのはアダマール変換の部分。
　一桁の場合は解説動画通りなので分かるけれど、二桁・三桁に拡張していくというところがよく分からない。拡張するとどうしてこういう式になるんだろう……。

　いまだにFFTもピンと来てないし、畳み込みを理解するためにどうにかしないといけないんだよね。私でも理解できるような資料はないものか。
時刻: 0 件のコメント:
ラベル: , ,

2021年6月5日土曜日

Educational Codeforces Round 110 (Rated for Div. 2)

　数分遅刻してDまで四完。今回のえでゅふぉC～Eは教育的な出題だったと思う。Cは尺取り法の、Dはセグ木の、Eはダブリングの、本質的な理解を問うている感じがします。
　普段のえでゅふぉは、educationalという名前の割に教育的とは思えない問題が多い気がするけど、今回は良かった。


C. Unstable String

　尺取り法で良いのだが、左端を動かすときの条件がやや書きにくい。
　dequeを使うと尺取り法を書きやすい、というのを目にしていたのを思い出し、この問題で試してみたのだけど、「左端の条件の書きにくさ」はこの方法では緩和されず、時間がかかってしまった。
　でも、普通に（whileとかで）書くよりはちょっと楽だったかも？

D. Playoff Tournament

　図の通り、セグメント木みたいなことをするのだけど、普段多くの人が書いているセグメント木とは添え字の順番が違うことに注意。
　そこを補正するため、普段の順番と今回の順番で、添え字の対応表を作れば良い。

　私は、対応表を作るときのfor文の範囲を間違えて、対応表に-1を残してしまったためTLEが出てしまった。原因特定に苦労した。

E. Gold Transfer

　コンテスト中は、$C_i>C_{p_i}$を見落としていたのでどうしようもなかったが、この条件をちゃんと理解すれば、一番祖先から貪欲にとっていけば良い。

　なら、ダブリングするのかな、というのは思いつく。
　ということは、金がなくなっていない祖先のノードを見つけて、そこから自分の方へ降りていけば良いのだけど、降りるときどうすれば良いの？　というところで詰まった。

　落ち着いて計算量解析をすれば分かりますね。

　なお、実装したけどPyPyだとTLEだったのでKotlinでACしました。ただ、今見ると何人かPyPyで通していますね。
時刻: 0 件のコメント:
ラベル: , , ,

2021年4月22日木曜日

Codeforces Round #717 (Div. 2)

　ABでペナルティを重ね、Cまで三完。Dは解けなくちゃいけなかったようだが、全く思いつかなかった。


D. Cut

　解説AC。
　「ダブリング」というキーワードを見ても分からず、解説を読んでようやく理解した。

　ダブリングは「何歩進んだときどこへ到達するか？」を調べるときに使うイメージがあったけど、この問題のように「ある場所へ到達するまで何歩か？」を調べるときにも使えるのね。
　典型らしいので頭に入れておかねば。

　ただ、自分の実装だとlogが二つ付く気がするんだけど、これで合ってるんだろうか。

　また、その前の、全ての要素について互いの素な部分を求めるパートは、事前に約数列挙して、尺取り法によりできる。ダブリングすると分かればこのパートはできると思うけど、そんな簡単には感じないので、こちらで躓かないようにしたい。

　類題だというこの問題もACしました。
　同じ解法で解ける問題なのに、添え字などの実装でミスしてしまい良くない……。なお、解説を見ると、logは一つと書いてありますね。うーん、どうやってlog一つ落とすのだろう。


　







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