2015-05-01から1ヶ月間の記事一覧
問題 TopCoder Statistics - Problem Statement 解法 定式化するのが一番大事なポイント。そこをはっきりさせればすぐに解法は3分探索だと思いつく。この問題を定式化すると以下のようになる: xi = xp[i] + xv[i] * t yi = yp[i] + yv[i] * t xj = xp[j] + x…
SRM練習会に参加。easyとmed解けてしかもmedが結構早かったので良かったと思います。 問題 TopCoder Statistics - Problem Statement 解法 それぞれの場所に目的のカードを仕込んだ時i回動かしたらどこにカードが向かうかを記憶し,それぞれのシャッフル回数…
なんか久しぶりに記事書いてる気がする… この問題はあとでFFT使って解いてみたいです(まだFFTをよく理解していないのでできませんが…) 問題 No.206 数の積集合を求めるクエリ - yukicoder 解法 基本は解説(http://yukicoder.me/problems/440/editorial)に書…
SRM練習会に参加。easyだけ通しました。一応チェックしていたとはいえ,easyもちょっとあぶなかったですね(整数演算が高速だから最悪ケースでも間に合ったけどすごい勢いでchallengeされるコードを書いてしまった)。 問題 TopCoder Statistics - Problem Stat…
考えていた方針は途中までは間違ってなかったらしい。 問題 TopCoder Statistics - Problem Statement 解法 基本的な方針は二分探索。x回でSCVsを全滅させることができるかどうかを判定し,全滅できる数のうち最小のものを求めれば良い。難しいのはその判定法…
SRM 658に参加しました。結果はeasyを200ptくらいで通してそこそこでした。そろそろmedも通してみたいですね… 問題 TopCoder Statistics - Problem Statement 解法 まず木が存在するかどうかを考える。以下の条件が成り立っていることが,条件を満たす木が存…
UnKoder #04 に参加しました。結果は内緒です。 topcoder以外のコンテストはたいていサンプルが甘いのでちゃんと注意深く問題を把握しないとダメですね。これからは意識的に気をつけていきたいです(C問題を単純な期待値の線形性を使ってやろうとしてハマった…
部分点解法はできたはずなのにもったいない。 問題 D: 有向グラフと数 - AtCoder Regular Contest 038 | AtCoder 解法 基本的にこれを参考にしました。 http://www.slideshare.net/chokudai部分点解法は,ターン数がたかだか2*Nでも結果が変わらないのでゲー…
AtCoder Regular Contest 038に参加。B問題までしか解けませんでした…辛い… 問題 C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder 解法 基本的なアイデア(grundy数とか)はこちらを参考にしました。 http://www.slideshare.net/chokudai 104点解法がよ…
なんか狐につままれたような気分。問題:No.196 典型DP (1) - yukicoder解法:解説のところに書いてあるとおり,O(N^3)であるような気がする計算量が,実はO(N^2)であるというトリックで時間内に解くことができる,という感じ。ソースコード参照しながらそのこと…
これは解きたかったかな〜問題:TopCoder Statistics - Problem Statement解法:0〜L-1の座標系に木を植えていくことになる。そこで,以下のような変数を用意する。 cnt[i]:座標iに植えられている木の数 dst[i]:dst[i] = cnt[i] * i 座標xに木を植えることを考…
SRM424の練習会に参加しました。結果はeasyだけ通して200ptくらいです。hardは今では典型になってそうな問題だったので後で解きたいと思います。問題:TopCoder Statistics - Problem Statement解法:まず注目すべきことは, ・最終的なStrengthとIntellectがわ…
まず4月の目標を振り返ってみます。 競プロ ・そこそこ難しい問題(div1easyくらい)を合計10問くらい ・結構難しい問題(div2hard,div1medくらい)を合計10問くらいこれは普通にOKでした。多分easyくらい->30問 medくらい->15問 ですね。その他プログラミング …