2015-07-01から1ヶ月間の記事一覧
No.31 悪のミックスジュース - yukicoder DP + 貪欲法 の切り替え問題。 解法を理解するの時間がかかった。要復習問題ですな。 dp のメモリ確保結果がたりなくて (vector dp(m*N+1, 0); とかして) で RE になってしまった。 class EvilMixJuice { public: vo…
No.61 リベリオン - yukicoder 鏡面反転のアイデアは思いついたけど、反転後の Mx,My の座標をどう求めればいいかわからなかった。 そっちの解法は Extra で学ぶとして、この問題の制約ではシミュレーションで十分だった。 格子点ごとの移動をさせるために最…
No.68 よくある棒を切る問題 (2) - yukicoder 解法を読んでも理解できるまで時間がかかった。これを解けるのはすごいなぁ。 class CuttingStick2 { public: void solve(void) { // // クエリ数が多いので二分探索では O(N*Q*log(N)) では間に合わない // そ…
No.67 よくある棒を切る問題 (1) - yukicoder 単純な二分探索の問題。 のはずが while ループの中で L'[i] -= mid を繰り返して L'[i] からもう mid が切り出せなくなったら ++i するみたいなループで TLE してしまった。下のコードにあるように割り算を使っ…
No.66 輝け☆全国たこやき杯 - yukicoder TDPC でほぼ同じ問題があった。Typical DP Contest - C トーナメント - shifth’s blog i round 目の x が所属する区間 [l,r) の計算方法は覚えておこう。 TDPC 復習しないと...。 class TakoyakiCup { public: void s…
No.60 魔法少女 - yukicoder いもす法。はじめ Segmetn Tree を2つ用意して...とかと思ったが違った。 いもす法のことは知ってたけど、使うのは初めてだったんで勉強になった 右上を +1 拡張しわすれそうになった。 class MagicGirl { public: void solve(vo…
No.59 鉄道の旅 - yukicoder 典型的な RMQ っぽい問題。 蟻本で BIT の存在はしっていたけど使うのは初めてだった。 この問題では sum は a[i]+...+a[maxW] なんだけど BIT では逆で a[1] + ... + a[i] 。それゆえに a[i] = sum[i]-sum[i+1] となる。これを…
No.53 悪の漸化式 - yukicoder トリッキーな問題と書いてあったので、おそらく精度落ちかなーとおもってたら案の定。long double で試してもダメだった。 高校レベルの漸化式を解いて一般項をだせばよい。一般項を計算しようとせずまず DP でやろうとするあ…
No.50 おもちゃ箱 - yukicoder 数が少ないので全探索で ok。 c++ なら next_permutaion が使える。 全然関係ないけど yukicoder は自分の解いた問題に色がつくんでなんか達成感があるな。 class ToyBox { public: void solve(void) { int N, M; cin>>N; vect…
No.41 貯金箱の溜息（EASY） - yukicoder 10^5 くらいの再帰をやろうとして stackoverflow してしまった...。 累積 DP がなんで必要かが一瞬わからなかった。 カテゴリ的には座標圧縮も入るのか。確かに。 class SighOfSavingsBoxEasy { public: void solve(…
TopCoder Statistics - Problem Statement 復習。解き方がさっぱりわからず SRM 663 div2 hard:CheeseRolling - mayoko’s diary を見て解いた。kmjp 先生然り、日本語の解説ページは色々助かる。 解法理解するのに時間がかかった。 それにしても、みんなよく…
復習。本番 TLE しそうだな。と思いながらも愚直な実装で撃墜されたやつ。 target からは一意に復元ができそうな気はしていたものの、やり方が思いつかなかった。 単純に末尾から削っていく逆変換をすればよいだけだった class ABBA { public: string canObt…
Problem - C - Codeforces Problem - E - Codeforces 復習。本番普通に DP しようとして MLE した。 よく読むと h,w の制限が 10^5 とかなんで座標圧縮とかしないとダメなのかなー、座標圧縮ってどうやるのか？とか思っていたがそもそも方針が違った。 総経…
Problem - B - Codeforces Problem - D - Codeforces 復習。TLE するかもなぁ。と思いつつも他に解法が思いつかず提出して、案の定 TLE した問題。SRM なら撃墜されてんだろうな。 各再帰での 4 通りの分岐を事前の正規化で回避する。できる人には自然に出て…
No.38 赤青白ブロック - yukicoder 自力でとけなかった。計算量見積もりがまだまだちゃんとできてない。 Kr 個となりが同じ色かの判定で変なフラグ管理をしようとして WA になってしまった。一発で通せるようにりたいなぁ。 再帰をうまく使うともっと効率の…
No.37 遊園地のアトラクション - yukicoder アトラクション i を訪れるたびに満足度が半減するのをどう表現するか。 v[i]/2^k, C[i] のアトラクションがあると考える。 class AmusementParkAttraction { public: void solve(void) { int T,N; cin>>T>>N; vec…
No.34 砂漠の行商人 - yukicoder 計算量が O(N^2*V) とかになるのでどうしたもんかなーと悩んだ問題。 砂漠のレベルが 9 までしかないので実質計算量が落ちるという問題だった。ココらへんの計算量見積もりが甘い...。あと問題の性質への気付き力がたりない…
No.33 アメーバがたくさん - yukicoder X[i] が最大 10^9 とかなんでまともに配列を確保したりすると TLE する。T 時間後に同じ座標に到達するものたちを一つにまとめて、間と前後を埋めるようにすればよい。 方針はあっていたのに abs(X[i]-X[j]) と書くべ…
No.30 たこやき工場 - yukicoder TLE するかなーと思ってたら案の定 TLE した問題。予測してるなら対応せんと。 いまいち累積をメモ化する方法が思いつかず、頂点への入力辺が全て辿られてから次の頂点へ移動する。みたいな遅延評価でやってみた。N 以外のノ…
No.28 末尾最適化 - yukicoder 問題をみた瞬間なんじゃこりゃーってなった問題。 解答をみると難しくはないとわかるけど。 class TailCallOptim { public: void solve(void) { int Q; cin>>Q; REP(_,Q) { int seed, n,K,B; cin>>seed>>n>>K>>B; vector<ll> x(n+1</ll>…
No.25 有限小数 - yukicoder 高校時代を思い出した。こんな感じの問題解いた記憶があった。 コメントのとおり overflow してしまった。くそー。 class FiniteDecimal { public: void solve(void) { ll N,M; cin>>N>>M; ll g = gcd(N,M); // 互いに素にしてお…
No.23 技の選択 - yukicoder 確率・期待値・ゲーム戦略的な問題は苦手...。 試行回数の期待値についてはyukicoder No.23 : 技の選択 - ぱーぽーの競プロ記が参考になった。 最初 Exp[h] = 1/3*Exp[h] + Exp[h+A] + 2/3*Exp[h+D] + 1 を解いてモゴモゴしよう…
No.19 ステージの選択 - yukicoder topological sort すればいいのはすぐ思いついた。sample テストでエラーになって強連結成分分解しないとダメなことに気づいた。 ライブラリを引っ張ってきてもいいんだけど、そこまでやらなくても解けそうだなーと思って…
No.15 カタログショッピング - yukicoder 蟻本ででてたやつ。前半・後半全列挙 + 二分探索 方針もあっていたし、コードも間違っていないっぽくて手元のローカルではサンプル通ったのにサーバ側でWAになってしまった。 最後の出力時に無駄に空白が入っていた…
No.14 最小公倍数ソート - yukicoder 印象深かったのでメモ 最初方針はあっていたのだけど、O(N^2) で TLE してしまった。 以下は他の人のコードを見て修正して通したやつ。 swap で pivot の位置をずらしてループの回数を減らすのはうまいと思った。(solve1…
No.12 限定された素数 - yukicoder 印象深かったのでメモ a[i] の出現が必要十分であることを確認するのに最初 map とかでカウントしようとしてコードがぐちゃぐちゃになっていた。 a[i] が 0,...,9 までしかないなら bit フラグで管理すれば簡単じゃん。っ…
Problem - E - Codeforces そもそも counting sort というのを初めて知った。使用制限があるが O(n) でソートできる高速ソート。それでも O(N*Q) になってしまう計算量をどう落とすか？ 想定解法は segment tree を使うやつらしいけど、segment tree まだち…
Problem - D - Codeforces 「[x,y] の区間に含まれている」という条件から区間を絞るのは簡単なんだけど、「[x,y]に含まれていない」という条件から区間を絞るのは大変。(区間が分割されてしまう可能性があるから。) 下のコードは他の人のものを参考にした。…
Problem - C - Codeforces 本番これ以降の問題は溶けなかった...。なかなか C 問題の壁を超えられない...。 実は全探索＋枝刈りっぽい話。 bfs + メモ化でなんとかなってしまうのか...。 solve2,solve3 は Codeforces Round #312 (Div. 2) Editorial - Codef…
Problem - B - Codeforces 本番は下のコードの cnt のかわりに map を使った O(n*log(n)) の解法で通した。ソッチのほうがバグも少なくてすむと思うけど、勉強のため O(n) のコードを書いてみた。 要は beauty となる a[i] の値の先頭と末尾を見つけておいて…
