No.107 モンスター - yukicoder bit dp の問題 最初 16! を 2^16 と勘違いして next_permutation を使ってしまって TLE。 HP = 0 になってそれ以降の遷移がないケースを飛ばさずに WA してしまっていた。 class Monster { public: void solve(void) { int N;…
SPOJ.com - Problem MKTHNUM 2104 -- K-th Number segment tree による手法だと一発で AC した。(SPOJ) メモリをたくさん使う分やはり速い。 merge は std::back_inserter を使ってもよいが事前に resize しておくほうが速いはず。 バケット法はこちらK-th N…
SPOJ.com - Problem MKTHNUM 2104 -- K-th Number 最近 yukicoder で平方分割をやったんで(No.96 圏外です。 - shifth’s blog)蟻本にのっていた問題を復習してみた。 定数倍がきびしすぎるのか vector をやめて global 配列にして、 cin/cout を scanf/print…
SPOJ.com - Problem HISTOGRA せっかくなんでブログの過去記事からひっぱってきた。 スタックにつむときに 2 パターンあるのがポイント class largest_rectangle_in_histogram { public: // 長方形の始点と終点を回る、素朴な2重ループでは O(N^2) で TLE し…
No.101 ぐるぐる！あみだくじ！ - yukicoder 最初計算量が見積もれなかった。 各 x の周期の最小公倍数が全体の周期になる。 まあ言われればわかるんだけど...、こういうのをぱっと思いつけるようになりたい。 class GruGruAmidakuji { public: void solve(v…
No.96 圏外です。 - yukicoder バケット法 + union find + convex hull + キャリパー法。 バケット法以外は思いついた。無駄に kd 木とかないとダメなのかなぁと思っていたらバケット法でよかった。バケット法の実装は初めてなので勉強になった。 x,y の制約…
No.76 回数の期待値で練習 - yukicoder sample からサイコロの各目が出る確率を逆算するという変わったな問題。 サンプルを眺めるだけで各目が出る確率がわかってしまう人達もいるみたい。すげぇ。 下のコードは逆算を二分探索を使ってやる方法。自分でうま…
TopCoder Statistics - Problem Statement editorial を見て解いた。 問題見た時 DP とかかな？と思いきやそんなことはなかった。 mergeSort なんでソート済みの部分列の段階で最終結果と前後が変わっていてはダメ。 class BearSortsDiv2 { public: vector<int> w</int>…
TopCoder Statistics - Problem Statement 本番普通に解けんかった...。orz しょげてもしょうがないので復習。復習。 ポイントは以下だと思っている。二番目に気づけたら全探索+memo化は思いつけたかも。 操作の前後で総和が変わらない。 多変数でも制約があ…
No.75 回数の期待値の問題 - yukicoder 自分自身を含む K+1 連立方程式を解く問題。確率系は苦手意識が...。いや、他のも解けないけど..。 最初なんで 2 分探索が使えるのかわからなかった。高校数学ですね...。 いろんな解法があるらしい。引き出しが多いの…
No.74 貯金箱の退屈 - yukicoder union find を使った解法。 連結成分が確定した後に one の結果を連結成分に適用しないとダメ。(忘れて WA した。) class BoredomOfSavingsBox { public: void solve(void) { int N; cin>>N; // // 同時にひっくり返せるもの…
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 以外のノ…
