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 枚なので) つまり初期状態から山…
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.62 リベリオン(Extra) - yukicoder No.61 リベリオン - shifth’s blogの制約強化版 鏡面反転後の座標を実際に求めるのではなくて、不定方程式を解くことで到達時間を求める。 自前の gcd, extgcd 関数が負の整数に対応していないことを忘れて WA しまくっ…
No.54 Happy Hallowe'en - yukicoder DP をやる前に、訪れる順番を決めておく問題。 最適な順番を最初から考えて詰まってしまった。 「a,b どちらが先でも同じだから、そうでないケースを考えよう。」って思考ができればよかったのかも。 class HappyHallowe…
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;…
No.101 ぐるぐる！あみだくじ！ - yukicoder 最初計算量が見積もれなかった。 各 x の周期の最小公倍数が全体の周期になる。 まあ言われればわかるんだけど...、こういうのをぱっと思いつけるようになりたい。 class GruGruAmidakuji { public: void solve(v…
No.96 圏外です。 - yukicoder バケット法 + union find + convex hull + キャリパー法。 バケット法以外は思いついた。無駄に kd 木とかないとダメなのかなぁと思っていたらバケット法でよかった。バケット法の実装は初めてなので勉強になった。 x,y の制約…
No.76 回数の期待値で練習 - yukicoder sample からサイコロの各目が出る確率を逆算するという変わったな問題。 サンプルを眺めるだけで各目が出る確率がわかってしまう人達もいるみたい。すげぇ。 下のコードは逆算を二分探索を使ってやる方法。自分でうま…
No.75 回数の期待値の問題 - yukicoder 自分自身を含む K+1 連立方程式を解く問題。確率系は苦手意識が...。いや、他のも解けないけど..。 最初なんで 2 分探索が使えるのかわからなかった。高校数学ですね...。 いろんな解法があるらしい。引き出しが多いの…
No.74 貯金箱の退屈 - yukicoder union find を使った解法。 連結成分が確定した後に one の結果を連結成分に適用しないとダメ。(忘れて WA した。) class BoredomOfSavingsBox { public: void solve(void) { int N; cin>>N; // // 同時にひっくり返せるもの…
No.31 悪のミックスジュース - yukicoder DP + 貪欲法 の切り替え問題。 解法を理解するの時間がかかった。要復習問題ですな。 dp のメモリ確保結果がたりなくて (vector dp(m*N+1, 0); とかして) で RE になってしまった。 class EvilMixJuice { public: vo…
No.61 リベリオン - yukicoder 鏡面反転のアイデアは思いついたけど、反転後の Mx,My の座標をどう求めればいいかわからなかった。 そっちの解法は Extra で学ぶとして、この問題の制約ではシミュレーションで十分だった。 格子点ごとの移動をさせるために最…
No.68 よくある棒を切る問題 (2) - yukicoder 解法を読んでも理解できるまで時間がかかった。これを解けるのはすごいなぁ。 class CuttingStick2 { public: void solve(void) { // // クエリ数が多いので二分探索では O(N*Q*log(N)) では間に合わない // そ…
