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] の値の先頭と末尾を見つけておいて…

Problem - A - Codeforces 復習。本番通ったけどコードが汚かったので書き直し。無駄に dfs とかしてたけど単なる足し算で住む話だった。 書き直しして WA になったりしたあたり本当に実装力が足りないと思った。 class Div2A { public: void solve(void) { …

いつまでも Div2 から抜け出せないへっぽこ緑コーダーなのでDPの勉強にTypical DP Contest の問題を解いてみた。 Div2 Hard は DP ができればきっと解けるようになるだろう!という願望の元に。 結果血反吐を吐くことになる。(半年くらいかかった気がする。) …

T: フィボナッチ - Typical DP Contest | AtCoder kitamasa 法 ほとんどきたまさ法メモ - よすぽの日記を見て理解した。 下のコードは再帰で書いているが再帰でない書き方もあるっぽい。そっちはまだ実装できるレベルではない。(理解できてない。) これで Ty…

S: マス目 - Typical DP Contest | AtCoder dp の状態が vector で表現される dp 接続判定は union find でやる。 class s_squares { public: // // 色の全てのぬり方のうち左上と右下が連結になるようなものの個数を数える // // 列を進めながら DP する？ …

R: グラフ - Typical DP Contest | AtCoder 強連結成分分解とtopological sort が面倒だった。 dp[i][j] を最大にする path2 の経路の保存が必要か?と思いきやそんなこともなかったというのがミソなんだと思った。 class r_graph { public: SCC scc_; // // …

Q: 連結 - Typical DP Contest | AtCoder わけがわからないよ simezi_tan ...(´・ω・｀) 他の人の解説記事をみってもさっぱりわからず、悩みに悩んだ問題。 ループの処理上、いろんな状態遷移を計算しているが、結局初期状態からの遷移が可能なもの以外は消…

P: うなぎ - Typical DP Contest | AtCoder dp の更新のためにさらに dp を使う問題。 const int MOD = (int)(1e+9)+7; class p_unagi { public: // // 根を一つ決めて有向木にして考える // // dp[x][i][j] := x を頂点とする部分木からパスを i 本選び、x …