2015-12-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 へ移動するほうが最短な場合もあるし、だめかなーと思って幅優先っぽい手法で解いた…
