2015-08-01から1ヶ月間の記事一覧
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 した。(計算量の落とし方がわからなかった。) 右にまがる地点をスタート地点にして、真っ直ぐか左にしかまがらないケースに限定…
No.85 TVザッピング(1) - yukicoder 星２つだけど普通に解けんかった。この手の発想系はまだ苦手。 解けるケースはすぐに思いついたけど、それ以外では解けないかがわからなかったし、法則的ところまで考察が進まなかった。 とりあえず片方が 2 の倍数でよい…
No.62 リベリオン(Extra) - yukicoder No.61 リベリオン - shifth’s blogの制約強化版 鏡面反転後の座標を実際に求めるのではなくて、不定方程式を解くことで到達時間を求める。 自前の gcd, extgcd 関数が負の整数に対応していないことを忘れて WA しまくっ…
No.54 Happy Hallowe'en - yukicoder DP をやる前に、訪れる順番を決めておく問題。 最適な順番を最初から考えて詰まってしまった。 「a,b どちらが先でも同じだから、そうでないケースを考えよう。」って思考ができればよかったのかも。 class HappyHallowe…
TopCoder Statistics - Problem Statement 復習。復習。 最後の桁と最初の桁だけ例外判定が必要。 こういう dp はまだまだパッと思いつかない。 class LuckySum { public: // // a,b を 1桁目から確定させていく。 // 各桁は 0,4,7 の組み合わせ(0 は leadin…
No.42 貯金箱の溜息 - yukicoder 勉強になった。 はじめ f(x,m) を多項式補完しないで f(x,m*C[x]+p) を多項式補完してる理由がすぐにわからなかった。f(x,m) だと次数が x とは限らないのか。 f(x,m*C[x]+p) は p に依存する。そのため補完に必要なサンプル…
No.145 yukiover - yukicoder y > u > k > i が降順なんでうまいこと再帰をすれば解けそうだなーと思ったけど、うまく再帰関数が書けなかった。 以下は他の人のコードを参照にした。こういうのも実装力なんだろうな。 const string target = "yuki@"; class …
No.140 みんなで旅行 - yukicoder 組み合わせ問題は圧倒的に練習不足だな...。 class TravelTogether { public: void solve(void) { // // F(x,y) := 夫婦が共に同じグループに入る夫婦が x 組、グループが y となる組み合わせ // // とすると // | 1 (x==y=…
No.134 走れ！サブロー君 - yukicoder bit DP の問題。最初 weigth の値も込みの dp[bit][weight] みたいな DP かと思ったが bit だけで weight が計算できることに気づけた。 問題文の重みが double だってことに気づかずに int w; に cin>>w; してしまって…
No.132 点と平面との距離 - yukicoder 三次元平面との距離を求める問題。 外積で法線を求めて、あとは公式を使う。 struct Pt3d { double x,y,z; Pt3d(double a, double b, double c) : x(a), y(b), z(c) {} Pt3d operator+(const Pt3d &other) const { retu…
No.130 XOR Minimax - yukicoder 解説を読んでもパッとソートが必要な理由(ソートしてうまく行く理由)がわからなかった。 事前にソートしておくことで分割を繰り返しても先頭 k ビット目が一致しているって条件が担保できるのか。 class XorMinMax { public:…
No.117 組み合わせの数 - yukicoder 実装が面倒だったんでライブラリを貼り付けた。が、コーナーケースと初期時の 2*maxN するべきところを maxN にして RE してしまった...。orz nComP の実装は 559C - Gerald and Giant Chess - shifth’s blog で使ったや…
http://yukicoder.me/problems/121 最初解説を見たとき、なんで期待値間の遷移に a/N じゃなくて a/total になっているのかわからなかった。 自己ループをくりかえしてから別状態に遷移するケースがあるんで 1/p * a/N = a/total になるのか。 確率 p の事象…
No.107 モンスター - yukicoder bit dp の問題 最初 16! を 2^16 と勘違いして next_permutation を使ってしまって TLE。 HP = 0 になってそれ以降の遷移がないケースを飛ばさずに WA してしまっていた。 class Monster { public: void solve(void) { int N;…
SPOJ.com - Problem MKTHNUM 2104 -- K-th Number segment tree による手法だと一発で AC した。(SPOJ) メモリをたくさん使う分やはり速い。 merge は std::back_inserter を使ってもよいが事前に resize しておくほうが速いはず。 バケット法はこちらK-th N…
SPOJ.com - Problem MKTHNUM 2104 -- K-th Number 最近 yukicoder で平方分割をやったんで(No.96 圏外です。 - shifth’s blog)蟻本にのっていた問題を復習してみた。 定数倍がきびしすぎるのか vector をやめて global 配列にして、 cin/cout を scanf/print…
SPOJ.com - Problem HISTOGRA せっかくなんでブログの過去記事からひっぱってきた。 スタックにつむときに 2 パターンあるのがポイント class largest_rectangle_in_histogram { public: // 長方形の始点と終点を回る、素朴な2重ループでは O(N^2) で TLE し…
No.101 ぐるぐる！あみだくじ！ - yukicoder 最初計算量が見積もれなかった。 各 x の周期の最小公倍数が全体の周期になる。 まあ言われればわかるんだけど...、こういうのをぱっと思いつけるようになりたい。 class GruGruAmidakuji { public: void solve(v…
No.96 圏外です。 - yukicoder バケット法 + union find + convex hull + キャリパー法。 バケット法以外は思いついた。無駄に kd 木とかないとダメなのかなぁと思っていたらバケット法でよかった。バケット法の実装は初めてなので勉強になった。 x,y の制約…
No.76 回数の期待値で練習 - yukicoder sample からサイコロの各目が出る確率を逆算するという変わったな問題。 サンプルを眺めるだけで各目が出る確率がわかってしまう人達もいるみたい。すげぇ。 下のコードは逆算を二分探索を使ってやる方法。自分でうま…
TopCoder Statistics - Problem Statement editorial を見て解いた。 問題見た時 DP とかかな？と思いきやそんなことはなかった。 mergeSort なんでソート済みの部分列の段階で最終結果と前後が変わっていてはダメ。 class BearSortsDiv2 { public: vector<int> w</int>…
TopCoder Statistics - Problem Statement 本番普通に解けんかった...。orz しょげてもしょうがないので復習。復習。 ポイントは以下だと思っている。二番目に気づけたら全探索+memo化は思いつけたかも。 操作の前後で総和が変わらない。 多変数でも制約があ…
No.75 回数の期待値の問題 - yukicoder 自分自身を含む K+1 連立方程式を解く問題。確率系は苦手意識が...。いや、他のも解けないけど..。 最初なんで 2 分探索が使えるのかわからなかった。高校数学ですね...。 いろんな解法があるらしい。引き出しが多いの…
No.74 貯金箱の退屈 - yukicoder union find を使った解法。 連結成分が確定した後に one の結果を連結成分に適用しないとダメ。(忘れて WA した。) class BoredomOfSavingsBox { public: void solve(void) { int N; cin>>N; // // 同時にひっくり返せるもの…
