てこずった

APRIL18B VAIMIN : April Challenge 2018 Division 2 - Vaibhav and Ministers

問題リンク https://www.codechef.com/APRIL18B/problems/VAIMIN 概要 組合せをO(1) で求められるように前計算をし、 障害点を考慮しながらゴールまでたどり着く経路の総数を求めます。 for 文DPで書き、 O( (p + q) log MOD + M^2 ) 考察 経路について repu…

AOJ 2741 : インビジブル

インビジブル | Aizu Online Judgeゲーム系の問題。困るのはスタックで配列で持っていたりすると解けない。 しかしよく考えてみると「最後に-1を出したのはいつか」 を持てばスタックの状態を表現できる。 (これだけでは不十分で最後にパスしたインデックス…

Codeforces Round #380 (Div. 2) A B C D

codeforces.com A めっちゃ実装に時間がかかった。どう書けばスマートか分からない。 ogoにhitしたらgoが続くまでfor文内のindexを増やす方式にしてAC。Submission #22346247 - Codeforces B actorがいないマスで上下左右に一つでもactorがいればカウントア…

AtCoder Beginner Contest 026 D : 高橋君ボール1号

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

AtCoder Beginner Contest 027 : A B C

abc027.contest.atcoder.jpむずかしめに感じた A int cnt[11]のような配列を用意して cnt[ni()]++とする。したら配列に入っている奇数のときの インデックスが答えSubmission #960459 - AtCoder Beginner Contest 027 | AtCoder B 島の合計人数がsなら、 1つ…

yukicoder No.443 GCD of Permutation

嘘解法でコンテスト終了後に落ちました。 あとで書き直します。 何回か再提出したらACするクソ解法が出来上がりました。精神が不安定になるので放置します。 記事を消すのは卑怯な気がしたので、 歴史として残しておきます。

DDCC2016 予選 A B C

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

AtCoder Beginner Contest 030 : A, B, C

AtCoder Beginner Contest 030 - AtCoder Beginner Contest 030 | AtCoder A 計算式通りに計算する。 doubleでやったらやばそうだけど、大丈夫だった。 絶対に通分したほうがいい。Submission #959910 - AtCoder Beginner Contest 030 | AtCoder B 360度のう…

AtCoder Beginner Contest 031

abc031.contest.atcoder.jp A 2通りを試して大きいほうを出力Submission #959337 - AtCoder Beginner Contest 031 | AtCoder B 場合分けを丁寧に書くSubmission #959348 - AtCoder Beginner Contest 031 | AtCoder C 青木くんが最善の手を尽くしたときの、高…

Codeforces Round #378 (Div. 2) A B C D

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

AtCoder Regular Contest 044 B : 最短路問題

arc044.contest.atcoder.jp 解法 まず、深さについて分けて考えると、 前段(個数n)と次段(個数m)の組み合わせの数について考える問題になる。前段は、完全グラフのように辺を取りうる。 その辺の中で自由に選んでいいので、となる。次段には、前段から辺…

CODE FESTIVAL 2016 qual C : E - 順列辞書 / Encyclopedia of Permutations

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

AtCoder Beginner Contest 033 D : 三角形の分類

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

AtCoder Regular Contest 055 B : せんべい

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

AtCoder Regular Contest 057 B : 高橋君ゲーム

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

AtCoder Beginner Contest 034 D : 食塩水

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

Codeforces Round #377 (Div. 2) A, B, C, D

codeforces.com A kを足していって、10で割った余りが0かrになればいい。Submission #21523193 - Codeforces B 2つを足して、足りない分を後ろに足せばいい。n = 1のケースのときは、何もしなくていいらしい。これが分からない。出したやつがそういう実装に…

AtCoder Beginner Contest 035 A, B, C

abc035.contest.atcoder.jp A 幅を4で割ってみて、その商を使って高さを割って3かどうかチェックSubmission #924362 - AtCoder Beginner Contest 035 | AtCoder B '?'のときは最大の場合、離れていき(マンハッタン距離+1)、 最小の場合、近づいていく(マ…

AtCoder Beginner Contest 038 D : プレゼント

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 のケースで落ち…

AtCoder Beginner Contest 038 A, B, C

abc038.contest.atcoder.jp A 最後の文字だけみて判定Submission #923339 - AtCoder Beginner Contest 038 | AtCoder B 全探索。頭が回らなくててこずるSubmission #923340 - AtCoder Beginner Contest 038 | AtCoder C ひとつずつ考えないで、増加した部分…