問題：No.951 【本日限定】１枚頼むともう１枚無料！ - yukicoder 解答：#472788 (C++14) No.951 【本日限定】１枚頼むともう１枚無料！ - yukicoder 解法： dp[i][j][l] := i番目のピザまでで、所持金がj円であるときの美味しさの最大値、l=[0/1]なら無料ピ…

問題：No.995 タピオカオイシクナーレ - yukicoder 解答：#472646 (C++14) No.995 タピオカオイシクナーレ - yukicoder 解法： Xi：i回目のパワー後にミルクティーにいる確率、Yi：i回目のパワー後にキッチンにいる確率とすると Xi+1 = Xi * (1 - p/q) + Yi …

問題：No.909 たぴの配置 - yukicoder 解答：#472634 (C++14) No.909 たぴの配置 - yukicoder 解答：mn = min(xi + yi)とすると、0番めのたぴは座標0、N+2番目のたぴは座標mnに置くことができる。 このとき、i番目のたぴはmax(mn - yi, 0)に置くとよい。これ…

問題：No.921 ずんだアロー - yukicoder 解答①：#472427 (C++14) No.921 ずんだアロー - yukicoder 解答②：#472421 (C++14) No.921 ずんだアロー - yukicoder 解法： ①dp[i][j]：i番目の項までで i=0⇒前の項がずんだ餅でないときのずんだ餅の個数の最大値 i=…

問題：No.1011 Infinite Stairs - yukicoder 解答：#472406 (C++14) No.1011 Infinite Stairs - yukicoder 解法：dp[i][j]：i回目の移動でj段目にいる通り数とする。 dp[i][j]はd[i]の最大d個の累積和になるが、累積和はj-1の計算結果を使いまわしてO(1)で計…

問題：No.929 よくあるボールを移動するやつ - yukicoder 解答：#472383 (C++14) No.929 よくあるボールを移動するやつ - yukicoder 解法：b[i] = 0であるiを覚えておくキュー(zero)とb[i] >= 2であるiを覚えておくキュー(pos)を準備しておく。また、解答変…

問題：E - Two Currencies 解答：Submission #12471668 - AtCoder Beginner Contest 164 解法：dp[v][s]を「頂点vに銀貨s枚で到達するときの最短時間」とし、ダイクストラする。（拡張ダイクストラ） 辺自体は最初に与えられた(v, a, b) = (行き先の頂点、辺…

問題：No.1015 おつりは要らないです - yukicoder 解答：#471337 (C++14) No.1015 おつりは要らないです - yukicoder 解法：次の手順で行う貪欲法。証明は解説参照。 あらかじめa[i]に1を足しておく。a[i]はpriority queue（変数名pq）として管理。 pqのtop…

問題：No.933 おまわりさんこいつです - yukicoder 解答：#470999 (C++14) No.933 おまわりさんこいつです - yukicoder 解法：各位の和の合計はその数のmod9と等しい（0以外の9の倍数は9）。なので、p[i] mod 9 を掛け合わせていけばよい。（多倍長整数が使…

問題：No.935 う し た ぷ に き あ く ん 笑 ビ － ム - yukicoder 解答：#470603 (C++14) No.935 う し た ぷ に き あ く ん 笑 ビ － ム - yukicoder 解法：敵と壁のHPの累積和、敵の数の累積和を前もって計算してゆく。各クエリに対し、攻撃する位置を…

問題：No.939 and or - yukicoder 解答：#470215 (C++14) No.939 and or - yukicoder 解法：AとBのビットを先頭から見てゆくとき、Aが1でBが0となるような桁があると、X & Y = A、X | Y = Bの条件から不適。よって AとBのビットが相違しているとき、必ずAが0…

問題：No.944 煎っぞ! - yukicoder 解答：#470208 (C++14) No.944 煎っぞ! - yukicoder 解法：最終的なコーヒー豆数を決めると、一つ当たりのコーヒー豆の美味しさが決まる。一つ当たりのコーヒー豆の美味しさ（tarとする）が決まった際、どのようにコーヒー…

問題：E - Sum of gcd of Tuples (Hard) 解答：Submission #11906400 - AtCoder Beginner Contest 162 解法：gcdが等しくなる(a1, a2, ..., an)ごとに計算する。gcdがdの倍数の場合は考えやすく、#{(a1, ..., an) | gcd(a1, ..., an) = x * d (x ≧ 1)} = (k …

問題：No.1010 折って重ねて - yukicoder 解答：#463175 (C++14) No.1010 折って重ねて - yukicoder 解法：サンプルサイズから、折る回数の上限は多くとも60回程度。縦にi回、横にj回折るのが可能である状態から、縦に折る・横に折るの再帰をしてゆく。再帰…

問題：No.1021 Children in Classrooms - yukicoder 解答①：#463089 (C++14) No.1021 Children in Classrooms - yukicoder 解答②：#463090 (C++14) No.1021 Children in Classrooms - yukicoder 解法①：i=0とi=n-1が吸収壁になっている。 lp：もともとi=0で…

問題：B - 天下一リテラル 解答：Submission #11754337 - 天下一プログラマーコンテスト2015予選B 解法：{}はdictである。そうでないなら{}のどの階層にいるかの変数levelをもち、{がでたらlevelを1加算、}が出たらlevelを1減算する。:がlevel1の時に出たら…

問題：D - 大ジャンプ 解答：(100点解法)Submission #11654098 - AtCoder Beginner Contest 011 (101点解法)Submission #11681204 - AtCoder Beginner Contest 011 解法：d | xかつd | y でないと到達不可能。よってx' = x / d, y' = x / d , d' = 1とし、以…

問題：C - 億マス計算 解答：Submission #11627090 - AtCoder Regular Contest 037 解法：愚直にai * bjを全て計算してソートすると空間計算量・時間計算量ともに厳しい。 ai * bjを全て列挙し、昇順ソートした数列をvとする。 K番目に位置する数xが持つ特性…

問題：A - 一次元オセロ 解答：Submission #11569003 - CODE FESTIVAL 2015 あさぷろ Hard 解法：以降、初期盤面で連続している黒または白はひとまとまりにして考える。 初期盤面をoxoxoとする。oが白、xが黒を表す。初手の黒は一番左に置くか一番右に置くか…

問題：E - Yutori 解答：Submission #11561483 - AtCoder Beginner Contest 161 解法：まず、左から貪欲に仕事をすることを考える（なるべく前に仕事を終わらせる）。vl[i]：i日目に仕事の割り当てがあれば何番目の仕事か（割り当てがなければ-1）とするとき…

問題：F - Division or Substraction 解答：Submission #11560428 - AtCoder Beginner Contest 161 解法：まず、NがKで割り切れない場合は、後者の作業がずっと続き、最終的にN%Kとなる。よってN%K=1のものをカウントすればよいが、これはN-1の約数の個数を…

問題：D - 道路の老朽化対策について 解答：Submission #11483588 - AtCoder Beginner Contest 040 解法：各頂点について連結かどうかを確認していくと間に合わない。 年度が新しい方から見てゆくと、使える道がどんどん増えてゆくので、道が増えたらUnion-F…

問題：https://atcoder.jp/contests/abc035/tasks/abc035_d 解答：Submission #11481223 - AtCoder Beginner Contest 035 解法：待つのは1種類の頂点でよい。なのでa[i] * (t - d[0, i] - d[i, 0])を全てのiで試せばよい。 d[0, i]はダイクストラで間に合う…

問題：C - タコヤ木 解答：Submission #11472903 - AtCoder Regular Contest 023 解法： -1になっているところに順番に数を入れていく。入れる数は直前の数以上の数になる。 これは-1直前の数をx、-1直後の数をx + n、-1の個数をkとすると、1からn+1までの数…

問題：F - Many Slimes 解答：Submission #11471423 - AtCoder Beginner Contest 140 解法：アルゴリズムとしては下記の通り。 Ａ:「今までに生んだ子の集合」、B：「ソート済みのこれから生む子の集合」とする。A = {sの最大値}からスタートする。Aの各要素…