Twin book report | Aizu Online JudgeDPだと思うけど大変そう。 最初rを2つ分けたときの大きいほうの最小値を求め、 余った時間に感想文を詰め込もうとしたが 無限にWAを重ねた。 半日頑張ってダメだったので諦めて解説を見る。2013/Practice/模擬国内予選/…

夏合宿の朝は早い | Aizu Online Judge確率は苦手…。システムの稼働率みたいに考えるのかなと思ったけど、 サンプルが単純な例で複雑なグラフになったとき結果がどうなるか分からず。 あきらめて解説を見る。2016/Practice/模擬国内予選B/講評 - ACM-ICPC Ja…

Rectangular Stamps | Aizu Online Judge盤面の状態を2bit * 16の32bitで表現できるなあ、と考えたが 大きすぎてメモ化はできない。A*などで頑張るが無理。検索する。d.hatena.ne.jpああ～確かに1bitだけで十分だった。 そうすれば到達済みのところは行かな…

D: 動的計画法 - AtCoder Beginner Contest 024 | AtCoderぼくも動的計画法好きだけれど解けなかった。 愛が足りない。 当初の方針 えーどうするんだろう。愚直にはできないし・・・。諦め 解法を見て はい。こういう風に式をいじくってみる心意気というか …

abc025.contest.atcoder.jp 当初の方針 分からない・・・。 全体の数（0の数の階乗）からルール違反のものを引いていくのかな。 でも重複があるし、それを取り除けなさそう・・・。諦め 解説をみて 1から置いていく、という発想が大事だったっぽい。 すでに…

codeforces.com A mapっぽいもの（int[256）を用意して数えて出力Submission #22227451 - Codeforces B 256を貪欲に選んだあと、残ったもので32を生成する。 怖いのでlongにした。Submission #22231261 - Codeforces C c, dが昇順になっているので、二分探索…

abc026.contest.atcoder.jp 当初の方針 単調な関数じゃないから、二分法は使えないだろうなあ。g(t) = f(t) - 100とおけば、0となる点を見つければ良さそう。 じゃあニュートン法だなWAは？ なんで？ サンプルすら合ってないし。 手元じゃ誤差は1e-12らしい…

abc027.contest.atcoder.jp 当初の方針 DP解法はすぐに思いつく。でも満点解法はどうすれば・・・？いろいろ考察してみるが甲斐なし諦め 解説をみて >, 確かに。頭いいなあ。じゃあ>を選んだからそれより右側で 一番大きい Segment Treeかなあ。ソートするだ…

ddcc2016-qual.contest.atcoder.jp A 問題文みて頭が真っ白になったが、冷静に考えたらkを求めればよかった。Submission #968467 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder B 言っていることがわからなかった。落ち着…

abc030.contest.atcoder.jp 当初の方針 見たことある。arukuka.hatenablog.com置換の累乗を使うんだな！N log Kで死亡うーん、ループがあるのかなあ。 でも今の実装だとうまく書けないし・・・。諦め 解法を見て 落ち着いて考えてみれば、閉路でループするま…

codeforces.com A 母音間の距離の最大値を求める。 初期indexを-1にして、末尾に番兵の'A'を置くと楽Submission #21920570 - Codeforces B 全体のsumを取っておいて、列iを右左入れ替えたときに 最大値を更新できるか舐めていく。Submission #21924549 - Cod…

arc044.contest.atcoder.jp 解法 言われた通りにやるだけ。なのに他の人の解答を見なければACできなかった。 最悪。Submission #958472 - AtCoder Regular Contest 044 | AtCoder2が素数じゃない扱いされるSubmission #958485 - AtCoder Regular Contest 044…

agc006.contest.atcoder.jp 当初の方針 えーわからん。 解説を見て 非常に丁寧に書かれている解説なので、 分かりやすかった。 行列累乗の要領で置換の累乗をすると ここがパッと分からなかった。 置換と置換の積は行列で表すと、置換の積このようになる。上…

arc049.contest.atcoder.jp 当初の方針 全然分からない・・・。 解法を見て 今さっき二分探索したのに、 なんで二分探索が思いつかないんだ・・・。Submission #951841 - AtCoder Regular Contest 049 | AtCoderはークソ

arc050.contest.atcoder.jp 当初の方針 分からない・・・。貪欲？ → 違う諦め 解法を見て 頭いいなあ・・・。 俺はいつになったら頭よくなるんだ・・・。提出 → WA Submission #951662 - AtCoder Regular Contest 050 | AtCoder死。r - mid か b - midが負に…

arc051.contest.atcoder.jp 当初の方針 ええ・・・分からない・・・。aをでかい数で固定してあげたら、 bを見るだけでいいのでは？Submission #951511 - AtCoder Regular Contest 051 | AtCoder→ K=30ぐらいまでが限界無理です。 解法を見て フィボナッチ数…

TopCoder Statistics - Problem Statement通せなくてめちゃくちゃ悔しい。 当初の解法 DPだなって思ってしまった。 public class ThueMorseGame { boolean[][] dp; boolean[][] done; int n; int m; public String get(int n, int m) { this.n = n; this.m =…

code-festival-2016-qualc.contest.atcoder.jp予選落ちたのが大変悔しかったので、 ちょっと背伸びして普段じゃ絶対に解けないだろう、 最後の問題を解いてみた。 当初の方針 ちんぷんかんぷん 解法を見て ？？？？自分に理解できるように噛み砕いていく。 …

code-festival-2016-qualc.contest.atcoder.jp 当初の方針 Cが解けなくてこちらに来る 部分点解法を狙おう うーん、O(H^4)にしかならない・・・ cost[i][y1][y2]はcost[i][y1-1][y2-1]の一番下しか違いがないことに気づく 再利用すればO(H^3)になるぞ でも実…

code-festival-2016-qualc.contest.atcoder.jp青木君が東からやってくるの見落として 問題の意味を理解するまでとても時間がかかった 当初の方針 意味分からん。間違いがあればどのデータも信用ならないし、 答えが出ないのでは？ 青木くんの存在に気づき、…

abc033.contest.atcoder.jp 当初の方針 幾何は苦手意識・・・。サンプルみたいに、直角と鋭角の数をカウントして、 全体から引けばいい？（うまくだまされました）グリッド上に配置されるから、直角になるには、 x座標かy座標かが一緒になる？ （大嘘。(0,0)…

arc055.contest.atcoder.jp 当初の方針 ちょっと前に友達と一緒に学校で解いていた思い出が蘇る。そのときはさっぱりで、解説放送を見てもさっぱり。今もさっぱり。 解説を読んで ？？？？？？コードが書けるようになるまで丸一日費やした。他のブログでは独…

arc057.contest.atcoder.jp 当初の方針 DP？ →考えたDP:dp[N][K] Kが10^9ほどあるので無理 先頭から最小の勝利数で勝率が上がるような貪欲？ 実装中に全部使い切らないと行けないケース （）でうまくいかない。 諦め 解法を読んで のケースは特殊化して省く…

abc034.contest.atcoder.jp 当初の方針 DP？ でもwが大きいし・・・。分からない。 解説を読んで 二分探索。なるほど。その通りに実装してAC。Submission #935434 - AtCoder Beginner Contest 034 | AtCoderでも、なんでそれが正しいか分からない。 なぜ基準…

abc035.contest.atcoder.jp 当初の方針 満点解法を狙いにいく。結局、どこかの節に最短で行って、できるだけ長く居て、最短で戻ってくればいい。 途中で寄った先に居る必要はない。ダイクストラ法で1から各節まで、逆順のリンクから各節から1までの最短経路…

abc046.contest.atcoder.jp 当初の方針 ううーん、難しそうだけど、式変形していけば良さそう。・・・詳細は省くが、整数論を持ち出してやっている途中で、 が素数でないと成立しないことに気づく。何故なら、モジュロ演算を行うときに逆元が必要になるのだ…

abc036.contest.atcoder.jp 当初の方針 DPだろうなあ・・・（定義が分かるとは言っていない2回目） 木だから、木の嬉しい性質を利用するのかな まず全探索。白か黒で遷移してチェック。これは2^10^5なのでダメ 両端が黒になるものを列挙して、残りの組み合わ…

abc037.contest.atcoder.jp 当初の方針 DPだと思うけど、きれいな（for文で書けるような）漸化式が思いつかない。PriorityQueueを使えばトポロジカル順序ソートできるかな・・・？ →重複除去とか、dp[i][j]に値を入れる方法が分からない・・・。 解説を見て …

abc038.contest.atcoder.jp 当初の方針（WA） ふつうにDPしたらO(N^2)になりそう。きっとO(N log N)解法。ソートして大きいやつから取っていけば良さそう → WASubmission #923373 - AtCoder Beginner Contest 038 | AtCoder 3 1 9999 1 1 2 2 のケースで落ち…