yukicoder
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>
No.173 カードゲーム（Medium） - yukicoder ARC003 D - シャッフル席替え - shifth’s blogでやったモンテカルロ法の復習問題。というかこの問題を解くために ARC003 を解いたんだけど。 等確率を計算したつもりが等確率になっていなくてバグに悩んだ。でき…
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…
No.127 門松もどき - yukicoder 幅DPで解く問題。 dpL のように片方だけ最後のインデックスをもっておき、もう片方では探索終了位置をもたせるポイントなのだと思った。 そうすると幅を 1 つづつ大きくしていくことで、 次に取りうる複数の j を全部探索する…
No.125 悪の花弁 - yukicoder 回転して一致するものを同じとみなしたときの数えあげ問題。 解法を理解してから、実装に超手間取った。g%pd とするところを T%pd にしたり、最後の 1/gs が抜けたりとひどかった...。 実装力がなさすぎるな...。 蟻本では似た…
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 うまくグラフを作って最小カットにもってく問題。 最小カットをつかっての最小コストでの二値分類ができるのは知っていたけど、この問題の場合は三値分類になってしまうのでどうしたものかと思っていた。 二値分類の…
