きろく

特筆すべき記録のまとめ

2018-01-01から1年間の記事一覧

CODE FESTIVAL 2018 Final:B - Theme Color

問題 解法 解答 問題 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 する…

CODE THANKS FESTIVAL 2018:E - Union

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

AtCoder で青になるまでにやったこと

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

AtCoder Regular Contest 067:E - Grouping

問題 解法 解答 問題 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)…

COLOCON -Colopl programming contest 2018-:D - すぬけそだて――トレーニング――

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

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦:B - GCDロボット

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

Tenka1 Programmer Contest:D - IntegerotS

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

codeFlyer (bitFlyer Programming Contest):D - ハンコ

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

CADDi 2018

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

CADDi 2018:D - Harlequin

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

CADDi 2018:C - Product and GCD

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

CODE THANKS FESTIVAL 2018:D - Concatenation

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

CODE THANKS FESTIVAL 2018:C - Pair Distance

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

AtCoder Grand Contest 001:C - Shorten Diameter

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

AtCoder Grand Contest 003:C - BBuBBBlesort!

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

codeFlyer (bitFlyer Programming Contest):C - 部分文字列と括弧

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

「みんなのプロコン 2018」:C - 駆引取引

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

第4回 ドワンゴからの挑戦状 予選:C - Kill/Death

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

AtCoder Beginner Contest 061:D - Score Attack

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

AtCoder Beginner Contest 057:D - Maximum Average Sets

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

AtCoder Beginner Contest 054:D - Mixing Experiment

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

AtCoder Beginner Contest 051:D - Candidates of No Shortest Paths

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

CODE FESTIVAL 2018 Final:D - Three Letters

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

AtCoder Grand Contest 029

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

AtCoder Grand Contest 029:B - Powers of two

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

AtCoder Grand Contest 029:A - Irreversible operation

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

AtCoder Beginner Contest 114:D - 756

問題 解法 解答 問題 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 を素数とする…

AtCoder Beginner Contest 114:C - 755

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

第18回日本情報オリンピック(JOI 2018/2019)予選

結果 競技前 競技中 結果発表後 結果 2学期期末考査の初日前日に行われた(極めて大変だった).6問・600 点満点中,5問+部分点・506 点で A ランクだった.1問目を解くのに想定より時間がかかってしまったが,その後は何とか解き進めることが出来たの…

JOI '18 予選:5 - 森林伐採

問題 解法 解答 問題 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) から行くこ…