c++
TopCoder Statistics - Problem Statement 本番では自作の points class みたなのでごちゃごちゃやっていた。 絶対もっと簡単に書けるだろうなと思っていたらTopCoder SRM 668 Div2 Medium IsItASquare - kmjp's blogとかみつけたので参照にしてコードを書い…
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 うまくグラフを作って最小カットにもってく問題。 最小カットをつかっての最小コストでの二値分類ができるのは知っていたけど、この問題の場合は三値分類になってしまうのでどうしたものかと思っていた。 二値分類の…
No.114 遠い未来 - yukicoder 最小シュタイナー木問題。蟻本に載っていなかった、Dreyfus-Wagnerのアルゴリズムを勉強するよい機会だった。 与えられる条件によってアルゴリズムを変える。Dreyfus-Wagnerr が使えない場合はターミナル以外の点を全探索して k…
No.153 石の山 - yukicoder grundy 数を使う問題。 分割によって複数の「山」ができてしまうが、grundy(A and B) = grundy(A) xor grund(B) なので vector などで状態を持たせなくても大丈夫。 Nim に帰着できないか...的なことを考えてしまった。(grundy 数…
M-N の差が小さいことを利用して計算する。 p^2 == M のときの罠にはまって WA した。コーナーケースの処理が甘い...。 class NFactorialModM { public: void solve(void) { int T; cin>>T; // // N >= M なら N*(N-1)*...*(M+1)*M*(M-1)*...*1 = 0 mod M //…
No.103 素因数ゲーム リターンズ - yukicoder 最初 grundy 数とか計算してたけど、素数を山の種類、冪を山の高さとする Nim と考えと素因数分解して xor を取るだけだった。 初期状態で決まる勝ち負け状態を保ったまま山の高さを k%3 まで遷移させることがで…
No.102 トランプを奪え - yukicoder 結局最後の山の最後のトランプをとれた方が勝ちになる。ということは初期状態で勝敗が決定する。 勝敗を決定するのは山の高さが 3 以下のときの配分となる。(とれるカードの枚数が 1,2,3 枚なので) つまり初期状態から山…
TopCoder Statistics - Problem Statement 復習。復習。 本番全く手が付けられなかったので、解説記事を見て書いた。 木の探索途中で部分 dp をやる。 与えられたグラフが非有向グラフなので par!=u の判定が必要なんだけど、dp 側でうっかりわすれてバグっ…
No.100 直列あみだくじ - yukicoder 1,...,n の順列(置換)のなかから該当のものを抜き出すという問題。 愚直にやると n! だが置換が巡回置換の積であるということを用いれば、各巡回置換(下のコードでは group)を独立して確定してやればよいので O(N^3) grou…
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.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;…
