No.180 美しいWhitespace (2) - yukicoder 三分探索を使う問題。三分探索は初めて書いた。double の三分探索でWAくらったりしたが、long long で三分探索して AC。 inf = (1 二分探索でもできるらしい。 極値は線分の交点上でとるはずなんで、うまく必要な交…

No.220 世界のなんとか2 - yukicoder 桁 DP で解く問題。3 の倍数をどうやって桁 DP に組み込むのかというと、ある桁までの mod 3 の値を状態として持っておけばよい。 計算解として 10^p - 1 - 2/3 * 9^p ってのもあるらしい。 とりあえず強引にでも DP で…

No.217 魔方陣を作ろう - yukicoder やるだけ問題。でも割と楽しかった。 class MakeMagicSquare { public: typedef vector<vector<int>> Mat; void report(const Mat &mat) { int n = mat.size(); REP(i,n) { REP(j,n) { cout<<mat[i][j]; if (j < n-1) cout<<" "; } cout<<endl; } } Mat makeOddMS(int n) { Mat mat(n,vector<int>(n,0)); int i,j…</mat[i][j];></vector<int>

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

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

No.173 カードゲーム（Medium） - yukicoder ARC003 D - シャッフル席替え - shifth’s blogでやったモンテカルロ法の復習問題。というかこの問題を解くために ARC003 を解いたんだけど。 等確率を計算したつもりが等確率になっていなくてバグに悩んだ。でき…

arc003.contest.atcoder.jp モンテカルロ法を使う問題。 解法については以下のスライドを参照。技術的な内容だけではなくて表現がかなり面白かったです。こういうの好き。 ARC#003D from nullmineral www.slideshare.net Hoeffding 不等式については以下が参…

C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder 二分探索 + bfs な問題。 以前解いたのにもかかわらず間違えまくった...。 bfs では pop 直後に vis を見てはじいてしまったり(致命的)、high = 1 class C_DarknessWayHome { public: void solve(voi…

No.206 数の積集合を求めるクエリ - yukicoder A[i],B[i] の上限が高々 10^5 であることに着目して解く。 以下は他の人のコードを参考にして解いた。bitset 使うとこんなに簡単に書けるとは..。すげー。 class QueryOfNumberProductSet { public: void solve…

No.209 Longest Mountain Subsequence - yukicoder 何も考えることもない単純な DP。のはずが結構バグを作ってしまった...。 O(T*N^3) じゃ間に合わないので DP 部分を O(N^2) にしないとダメなのかなぁと思いきやそうでもなかった。 class LongestMountainS…

No.184 たのしい排他的論理和(HARD) - yukicoder uint64 を 64列 x N 行の mod 2 上の行列と考えて rank をもとめればよい。 col = 63 にすべきところを col = 64 にしたりしてハマった。 // uint64_t 吐き出し法 std::vector<uint64_t> sweep_uint64(const std::vector<uint64_t></uint64_t></uint64_t>…

No.186 中華風 (Easy) - yukicoder 中国剰余定理を使う問題。 蟻本に乗ってたライブラリを使ってしまったが、これくらい自力でかけないとダメかなぁ...。 正整数を出力するので 0 や負は変換しないとダメ。 template <typename T> std::pair<T,T> linear_congruence( const st</t,t></typename>…

No.147 試験監督（2） - yukicoder 繰り返し２乗法を使うもんだい。フィボナッチ数列が隠れているとは... 行列繰り返し2乗法で高速化できないか？というのはテクニックとして覚えておこう。(蟻本で見てはいたんだけどなぁ...) const ll Mod = (int)(1E+9)+7;…

No.205 マージして辞書順最小 - yukicoder 貪欲法。priority_queue で書くより set で書く方が綺麗にかけたかも。priority_queue の compare 関数がうまく実装できなかった...。 class MergeAndLexicographicOrderSort { public: void solve(void) { int N; …

No.202 1円玉投げ - yukicoder バケット法を使う。分割領域に含まれる一円玉の最大個数はたかだか 25 個程度なので十分間に合う。 class ThrowOneYenCoin { public: static const int r = 10; typedef pair<int,int> Pt; bool hit(const Pt &a, const Pt &b) { int ax</int,int>…

No.199 星を描こう - yukicoder 星を一筆書きするとみなして、辺を順列で表現して、一つの辺にたいして接続しない残りの２辺が条件を満たすかチェックすれば良い。 class WriteStars { public: void solve(void) { vector<Ptd> verts(5); REP(i,5) { int x,y; cin</ptd>…

No.190 Dry Wet Moist - yukicoder 貪欲法でとける問題。Moist なケースを最初に考えてとっかかりにして他のケースの解き方も思いついた。 multiset じゃなくて set にしてしまって間違えてしまった...。しょうもない。 もうちょい綺麗にコードがかけるとい…

No.189 SUPER HAPPY DAY - yukicoder TDPC E-数 でやった桁 DP を使う。桁を大きいほうから DP するのがポイント 最後は 00...0 と全て 0 のケースを除くことことが必要。 const ll Mod = 1000000009; class SuperHappyDay { public: void solve(void) { str…

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…