問題 解法 解答 問題 atcoder.jp 解法 p = C(N, r_1) * C(N - r_1, r_2) * C(N - r_1 - r_2, r_3) * ... * C(r_M, r_M) / M^N となる．これを愚直に計算すると，途中で数が大きくなりすぎてしまったり小さくなりすぎてしまったりするので，全体に log10 する…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := 整数 i が j 個あるとき，これから黒板に書かれている数を１つにする通り数 と DP を定義する．このとき， dp(i, j) = dp(i + 1, (j + k) / 2) （k は 0 <= k <= a_i で (j + k) % 2 == 0 を満たす整数） …

青コーダーになりました！！！ 前日に 200 - 800 (300) - 1000 - 1000 - ... という初心者お断りな配点が発表された AtCoder Grand Contest 030，A と B 部分点でパフォーマンス 2000 越えをし，青コーダーになることが出来ました．１年半以上の間水色コーダ…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 人をグループ人数 j 以上のグループに分けるときの通り数 と DP を定義する．このとき， dp(i, j) = dp(i - j * k, j + 1) * c / k! (C <= k <= D, c = C(i, j) * C(i - j, j) * ... * C(i - j * (k - 1)…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 番目の候補の時刻から先で j 回起動するときの解の最大値 と DP をおく．このとき，愚直に全ての候補を選んでいては O(N^3) になってしまう．ここで，「今の時刻 + X を超える時刻のうち一番早いもの」と…

問題 解法 解答 問題 atcoder.jp 解法 求める整数は gcd(a_1, Z), gcd(a_2, Z), ... , gcd(a_N, Z) の公倍数である必要があるので，この公倍数のうち最小のものを求めるので，答えは lcm(a_i, Z) になる．O(N)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 K を２進数表記したとき，「0 ~ 2^(k - 1) の位が 1，2^k の位が 0，2^(k + 1) ~ 2^30 の位は K のそれぞれの位と同じ」数を考える．この数を OR で超えない中で整数を出来るだけ選べばよいので，各 k についてそれぞれ…

問題 解法 解答 問題 atcoder.jp 解法 紙の (N + 1) 行目～ (H - N) 行目，(M + 1) 列目～ (W - M) 列目 はそれぞれ同じ模様になるので，この２つの区間を座標圧縮することが出来る．また，ハンコの１つ１つの黒マスが紙を黒くする領域は長方形になるので，…

結果 C - Product and GCD D - Harlequin 結果 2 完 1 WA（800 点・25:41），747 位中 251 位，パフォーマンス 1878，新レート 1574 (+39, Highest)．目標であった２完を達成することが出来たので安心した．また，レートを Highest 更新することが出来たので…

問題 解法 解答 問題 atcoder.jp 解法 答えは「全ての色の個数が偶数であれば "second"，そうでなければ "first"．」になる． 相手に全ての色の個数を偶数で渡すことが出来れば，相手が任意の色の個数を奇数にしてきたとしても，こちら側で奇数にされたとこ…

問題 解法 解答 問題 atcoder.jp 解法 P の素因数を a_i に分配していくイメージなので，P を素因数分解し，各 a_i に (各素因数の個数 / N) 個ずつ各素因数を分配すれば GCD が最大にできる．O(sqrt(P))． 解答 atcoder.jp かける個数を単純に 1 としてしま…

問題 解法 解答 問題 atcoder.jp 解法 文字列を前から見ていき，今構成している部分文字列の先頭の文字より小さいか同じ文字が出てきたら，その箇所で部分文字列を切り，新しいものを始めればよい（シミュレーション）．O(|S|)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 絶対値がついているのが厄介というか大変そうなので，x を昇順にソートすることによって各 i について (x_(i + 1) + x_(i + 2) + ... + x_N) - x_i * (N - i - 1) も求め，足し合わせたものが答えになる．O(NlogN)． 解…

問題 解法 解答 問題 atcoder.jp 解法 「直径が K より外の頂点を削除する」と「直径が K 以内の頂点を残す」のは同じなので，後者に置き換えて，残す頂点を最大化することを考える． K が偶数の場合，各頂点から K / 2 以内の頂点を残すことになるので，全…

問題 解法 解答 問題 atcoder.jp 解法 連続する３つの要素を逆順にする操作は真ん中の要素を挟んでいる２つの要素を swap することと同じなので，A の奇数番目の要素と偶数番目の要素それぞれがソートされる．なので，ソートされた後の A で奇数番目の要素で…

問題 解法 解答 問題 atcoder.jp 解法 '(' を +1，')' を -1 として累積和 imos を取った時，当てはまる (i, j) の組は imos[i] == imos[j] - 1 imos[k] >= imos[j] - 1 (i <= k <= j) を満たしていればよい．１つ目の条件にあてはまる (i, j) の組を std::m…

問題 解法 解答 問題 atcoder.jp 解法 dp1(b, i) := 今残っている商品が b で，財宝を i 個売却した時に商品を買って取引を終了する場合，得られる最大のスコア dp2(b, i) := 今残っている商品が b で，財宝を i 個売却した時に得られる最大のスコア の２つ…

問題 解法 解答 問題 atcoder.jp 解法 A チームでの総 kill 数は B チームでの総 death 数になり，その逆もそうなる．チーム内で同じ kill 数を１グループとしてみると，グループ内で death 数を分割すると考えられるので，分割数のアルゴリズムを使える．あ…

問題 解法 解答 問題 atcoder.jp 解法 頂点 1 から N へのスコアを最大化するパス上に閉路があるならば，スコアを無限に大きくできる．これをベルマンフォード法を用いて調べればよい．辺のコストの符号を逆にすることでスコアを最大化できる．O(NM)． 解答 …

問題 解法 解答 問題 atcoder.jp 解法 v を降順にソートし，前から A ~ B 個を平均値が小さくならない間通り数を求め，その合計を答えにする．前から i 個取った時の通り数は C( (v の中にある v[i] の個数), (今まで取った中にある v[i] の個数) ) になる．…

問題 解法 解答 問題 atcoder.jp 解法 「dp(i, j, k) := 薬品 i まででタイプ A を j タイプ B を k 集めるときの最小コスト」で DP をする．O(N^3)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 N <= 100 と小さいので，ワーシャルフロイド法を用いて全頂点間の最短コストを更新していく．もし，dist[i][j] > dist[i][k] + dist[k][j] であるならば，辺 (i -> j) はどの最短経路にも含まれない．これを数えていき…

問題 解法 解答 問題 beta.atcoder.jp 解法 各文字列ごとにある場所 p より左右それぞれに文字 c があるかどうかを前計算しておき，各場所 p ごとに考えられる略称を全探索していき，数えておく．考えられる略称のうち最も数えた数が多いものが答えになる．O…

結果 A - Irreversible operation B - Powers of two 結果 １完（300 点，6:32），1758 位中 835 位，パフォーマンス 1419，レート 1535 (-12)．A 問題で WA を出さずに通せたのはよかったが，B 問題がどうしても通せなかったのが残念だった． A - Irreversi…

問題 解法 解答 問題 beta.atcoder.jp 解法 まず，A を大きい順に見ていく．このとき，今見ている要素が一番大きいので，もしペアにすることが出来る要素があるならば，それは１つに定まる．ここで，あえてペアにしないことは得にならない（最終的な答えが -…

問題 解法 解答 問題 beta.atcoder.jp 解法 それぞれの W より左にある B の数の合計が答えになる． 解答 beta.atcoder.jp

問題 解法 解答 問題 beta.atcoder.jp 解法 自然数 k を素因数分解した式を p^a * q^b * r^c とすると，k の約数の個数は (a + 1) * (b + 1) * (c + 1) であるので，これを利用して，75 は 1 * 75, 3 * 25, 3 * 5 * 5, 5 * 15 なので，p, q, r を素数とする…

問題 解法 解答 問題 beta.atcoder.jp 解法 3 を 0，5 を 1，7 を 2 として考えると３進数を列挙して考えればよいと分かる．この通り数は 3^9 なので十分間に合う．O(3 ^ log2(N))． 解答 beta.atcoder.jp 実装で少してこずったが一発 AC．

結果 競技前 競技中 結果発表後 結果 ２学期期末考査の初日前日に行われた（極めて大変だった）．６問・600 点満点中，５問＋部分点・506 点で A ランクだった．１問目を解くのに想定より時間がかかってしまったが，その後は何とか解き進めることが出来たの…

問題 解法 解答 問題 beta.atcoder.jp 解法 「dp(i, j, d) := マス (i, j) まで d 個のマス（マス (0, 0) と (H, W) を含む）を経由して行くときのコスト」と DP を立てる．マス (i, j) へはマス (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j) から行くこ…