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…