2015-01-01から1年間の記事一覧
No.176 2種類の切手 - yukicoder アルゴリズム的には全探索なのだけど、計算量見積もりがうまくできなかった。 最適化対象式の対称性に気がつけば O(√T) 計算量が導きだせたかも。 T-m*B >= 0 の判定が抜けてしまった...。 class TwoKindsOfStamp { public: …
No.171 スワップ文字列(Med) - yukicoder 組み合わせ計算問題 解くべき式は単純なんだけど、1/a! mod 573 をどう計算するか悩んだ。573 が素数のようなケースは過去にやったことがあったんだけど。 式変形して nCr の積に帰着させればよい。 最後の -1 部分…
No.168 ものさし - yukicoder 二分探索を使う問題 10^9 まである座標を hypot につっこんで計算して精度落ちしてしまった...。 あと何気に最後の cout で long long にキャストせずに WA してしまった...。出力時にキャストしわすれないようにしよう。 class…
No.165 四角で囲え！ - yukicoder 座標圧縮+累積和+片側全探索+しゃくとり法/二分探索 で解く問題 累積和、座標圧縮とか久しぶりすぎて間違いまくった...。座標圧縮は c++ では insert 時に既にキーがあると insert されないので xmap.emplace(xs[i],xmap.si…
No.160 最短経路のうち辞書順最小 - yukicoder 経路復元問題 Nダイクストラならもうちょい面倒かも。 経路があるかどうかは cost[c][i] をみればよい。 class LexicographicOrderShortestPath { public: void solve(void) { int N,M,S,G; cin>>N>>M>>S>>G; c…
No.158 奇妙なお使い - yukicoder dp で解く問題。 状態数の上限が 10^7 程度なので一回の calc を高速化できればよい。できるだけ小さい金額の貨幣が残る方が Db,Dc との一致確率があがるので下記 calc 内部ではそのように実装している。 array<int,3> A,B,C; int </int,3>…
No.151 セグメントフィッシング - yukicoder No.259 セグメントフィッシング＋ - yukicoder 鏡面反転を配列を二倍にしてリング状に扱うことで解く問題。 鏡面反転のアイデアはすぐに思いついたが出力が半開区間なのでおかしな場合分けをしてなかなか実装がで…
No.142 単なる配列の操作に関する実装問題 - yukicoder 偶奇だけに着目すればよいので、ビット配列として扱えば高速化できる問題。 解法は思いついたものの、とんでもなく実装に手間取った。自分の実装力のなさに衝撃を受けてしまった...。 class ArrayImple…
TopCoder Statistics - Problem Statement ここ1ヶ月くらいサボりまくっていて久しぶりの SRM だった。 本番ナップザック的に DP でやれるんじゃないか？と思いつつも、i i へ移動するほうが最短な場合もあるし、だめかなーと思って幅優先っぽい手法で解いた…
No.127 門松もどき - yukicoder 幅DPで解く問題。 dpL のように片方だけ最後のインデックスをもっておき、もう片方では探索終了位置をもたせるポイントなのだと思った。 そうすると幅を 1 つづつ大きくしていくことで、 次に取りうる複数の j を全部探索する…
No.125 悪の花弁 - yukicoder 回転して一致するものを同じとみなしたときの数えあげ問題。 解法を理解してから、実装に超手間取った。g%pd とするところを T%pd にしたり、最後の 1/gs が抜けたりとひどかった...。 実装力がなさすぎるな...。 蟻本では似た…
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 復習してなかったので、復習。 前後半列挙のように一部だけ全探索して、各イテレーションで高速に残りを計算する問題。 二分探索とか使えないのでどうしたものかと思っていて時間切れだった。 実はイテレーションし…
No.124 門松列(3) - yukicoder 単純な幅優先探索。今来た4方向を保存しておいて再度訪れないようにする。 y 方向の向きを間違えたり、門松列の条件が抜けたりしてしまった...。 class PineDecorationSequence3 { public: void solve(void) { int W,H; cin>>W…
No.122 傾向と対策：門松列（その３） - yukicoder bit dp を使って解く問題。 他の人の解答を見て解いた。最近特に写経率高いなー。自力で解ける問題が全然ない..。 最初何やってるのかわからなかった。 a,b,c,d,e,f,g 全てことなるということから 1,...,20…
No.121 傾向と対策：門松列（その２） - yukicoder 他の人のコードを参考にした。 最後に a==c なる組み合わせを削除する。 ここのアルゴリズムは式を書いてみるまでわからなかった。勉強になるなー。 template <typename T> class BIT { public: std::vector<T> data; // [</t></typename>…
No.120 傾向と対策：門松列（その１） - yukicoder 貪欲法。 priority_queue から使える竹の数が多いもの順に取り出すのだけど、取り出すときに3つ連続して取り出して、減らして再度 push することでうまく処理する。勉強になった。 class TrendAndCounterme…
No.119 旅行のツアーの問題 - yukicoder うまくグラフを作って最小カットにもってく問題。 最小カットをつかっての最小コストでの二値分類ができるのは知っていたけど、この問題の場合は三値分類になってしまうのでどうしたものかと思っていた。 二値分類の…
No.114 遠い未来 - yukicoder 最小シュタイナー木問題。蟻本に載っていなかった、Dreyfus-Wagnerのアルゴリズムを勉強するよい機会だった。 与えられる条件によってアルゴリズムを変える。Dreyfus-Wagnerr が使えない場合はターミナル以外の点を全探索して k…
No.153 石の山 - yukicoder grundy 数を使う問題。 分割によって複数の「山」ができてしまうが、grundy(A and B) = grundy(A) xor grund(B) なので vector などで状態を持たせなくても大丈夫。 Nim に帰着できないか...的なことを考えてしまった。(grundy 数…
M-N の差が小さいことを利用して計算する。 p^2 == M のときの罠にはまって WA した。コーナーケースの処理が甘い...。 class NFactorialModM { public: void solve(void) { int T; cin>>T; // // N >= M なら N*(N-1)*...*(M+1)*M*(M-1)*...*1 = 0 mod M //…
No.103 素因数ゲーム リターンズ - yukicoder 最初 grundy 数とか計算してたけど、素数を山の種類、冪を山の高さとする Nim と考えと素因数分解して xor を取るだけだった。 初期状態で決まる勝ち負け状態を保ったまま山の高さを k%3 まで遷移させることがで…
No.102 トランプを奪え - yukicoder 結局最後の山の最後のトランプをとれた方が勝ちになる。ということは初期状態で勝敗が決定する。 勝敗を決定するのは山の高さが 3 以下のときの配分となる。(とれるカードの枚数が 1,2,3 枚なので) つまり初期状態から山…
TopCoder Statistics - Problem Statement 復習。復習。 本番全く手が付けられなかったので、解説記事を見て書いた。 木の探索途中で部分 dp をやる。 与えられたグラフが非有向グラフなので par!=u の判定が必要なんだけど、dp 側でうっかりわすれてバグっ…
No.100 直列あみだくじ - yukicoder 1,...,n の順列(置換)のなかから該当のものを抜き出すという問題。 愚直にやると n! だが置換が巡回置換の積であるということを用いれば、各巡回置換(下のコードでは group)を独立して確定してやればよいので O(N^3) grou…
No.97 最大の値を求めるくえり - yukicoder N の大小でアルゴリズムを切り替える。って発想がなかなかできない。 class MaxmumValueQuery { public: void solve(void) { int N,Q; cin>>N>>Q; vector<int> A(N); generateA(N,A); sort(RANGE(A)); vector<bool> exist(Mod</bool></int>…
No.95 Alice and Graph - yukicoder coin の大きいノードを順にみていけばよいのはわかったが、なぜ bit DP が必要なのか(というか解説コードでやっている bit DP)がわからなかった。 bit DP はどっちかというと二分探索で可能か判定しながら値を求めるやつ…
No.93 ペガサス - yukicoder 1,2,...,n の順列のうち特定の条件を満たすものを求める問題。 1,2,...,n の順番で挿入しながら順列を作ると考えることで、状態に遷移(方向性)をもたせることができるのかー。 最初 (n,n-2) の隣接フラグをなんで持たせるのかが…
No.86 TVザッピング(2) - yukicoder 一度だけ右に曲がる閉路を検出すればよいとこまではわかったが、それを普通に実装して TLE した。(計算量の落とし方がわからなかった。) 右にまがる地点をスタート地点にして、真っ直ぐか左にしかまがらないケースに限定…
