yukicoder
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(…
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 フラグで管理すれば簡単じゃん。っ…
