TopCoder Statistics - Problem Statement 本番では開いただけの問題。最短経路が複数あるとき、指定の経路を含むもの以外の最短経路を見つけるのがミソな問題。 どうやって見つけるのかは思いつず、以下のブログを参考にした。最短経路のパターン数を持って…

TopCoder Statistics - Problem Statement 復習。復習。 問題文の意味がわからなくてタイムロスしてしまった。 ある時間での勝者を探す。時間の範囲は 0~10^9 なので単純なループじゃ TLE するが、各 submit time とその前後 1 秒くらいだけ調べればよいので…

TopCoder Statistics - Problem Statement ここ1ヶ月くらいサボりまくっていて久しぶりの SRM だった。 本番ナップザック的に DP でやれるんじゃないか？と思いつつも、i i へ移動するほうが最短な場合もあるし、だめかなーと思って幅優先っぽい手法で解いた…

TopCoder Statistics - Problem Statement 本番普通にとけなかった。DP じゃ時間に間に合わないってのはわかってたんだけど。 SRM 668 Div2 Hard AnArray - shifth’s blog とかとほとんど同じようなパターンの問題だった。まだ復習してなかったので...。 w[a…

TopCoder Statistics - Problem Statement 本番では自作の points class みたなのでごちゃごちゃやっていた。 絶対もっと簡単に書けるだろうなと思っていたらTopCoder SRM 668 Div2 Medium IsItASquare - kmjp's blogとかみつけたので参照にしてコードを書い…

TopCoder Statistics - Problem Statement 復習。復習。 本番全く手が付けられなかったので、解説記事を見て書いた。 木の探索途中で部分 dp をやる。 与えられたグラフが非有向グラフなので par!=u の判定が必要なんだけど、dp 側でうっかりわすれてバグっ…

TopCoder Statistics - Problem Statement 復習。復習。 最後の桁と最初の桁だけ例外判定が必要。 こういう dp はまだまだパッと思いつかない。 class LuckySum { public: // // a,b を 1桁目から確定させていく。 // 各桁は 0,4,7 の組み合わせ(0 は leadin…

TopCoder Statistics - Problem Statement editorial を見て解いた。 問題見た時 DP とかかな？と思いきやそんなことはなかった。 mergeSort なんでソート済みの部分列の段階で最終結果と前後が変わっていてはダメ。 class BearSortsDiv2 { public: vector<int> w</int>…

TopCoder Statistics - Problem Statement 本番普通に解けんかった...。orz しょげてもしょうがないので復習。復習。 ポイントは以下だと思っている。二番目に気づけたら全探索+memo化は思いつけたかも。 操作の前後で総和が変わらない。 多変数でも制約があ…

TopCoder Statistics - Problem Statement 復習。解き方がさっぱりわからず SRM 663 div2 hard:CheeseRolling - mayoko’s diary を見て解いた。kmjp 先生然り、日本語の解説ページは色々助かる。 解法理解するのに時間がかかった。 それにしても、みんなよく…

復習。本番 TLE しそうだな。と思いながらも愚直な実装で撃墜されたやつ。 target からは一意に復元ができそうな気はしていたものの、やり方が思いつかなかった。 単純に末尾から削っていく逆変換をすればよいだけだった class ABBA { public: string canObt…

TopCoder Statistics - Problem Statement 復習。本番通せたとおもったら system test で落とされた。 与えられた点が三角形をなし、かつ原点がその三角形含まれるとき、その三角形から脱出するための safe level を計算する必要がある。 本番では三角形の内…