AtCoder 400 点問題
問題 解法 解答 問題 atcoder.jp 解法 まず，最も長くなるような 1 の連続する部分列をただ 1 つ作るのが最適になる．なぜならば，わざわざ間に 0 をいくつか挟み複数の 1 が連続する部分を作るのであれば，複数の 1 の部分のうち最も長いものの両端の 0 の…
問題 解法 解答 問題 atcoder.jp 解法 XYZ 通り列挙していては当然間に合わないので，まず XY 通り全て列挙する．この XY 通りのうち，K + 1 番目以降は最終的な答えの K 個の中に入らない（これは実験すると明らか）．なので XY 通りをソートし，大きいもの…
問題 解法 解答 問題 atcoder.jp 解法 最大の長さの回文１つとあまりの文字で長さ 1 の回文をたくさん作るのが最適．O(|S|)． 解答 atcoder.jp
問題 解法 解答 問題 atcoder.jp 解法 まず，A 枚のクッキーを B 枚のクッキーにするとき，2 枚以上増えなければ得をしない．なぜならば，2 回かかる操作をただクッキーを 1 枚あたらしく得ることに費やした方がよいから．そうでないとき，まずクッキーを A …
問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k, l) := 今 i - 1 文字目まで考えて，i - 3 文字目が j，i - 2 文字目が k, i - 1 文字目が l のときの，i 文字目から先の通り数 と DP を定義する．次の１文字（すなわち i 文字目）を決めるとき 'A', 'T', …
問題 解法 解答 問題 atcoder.jp 解法 前から操作を見るのは実は困難なので，後ろから見ていく．このとき，問題は「場所 i で数字 i を消すことができる．この消し方とは？」と言い換えられる．また，消す場所は消せる場所の中で一番右がよい．なぜならば，…
問題 解法 解答 問題 atcoder.jp 解法 グラフから辺を取り除いていくのではなく，辺を追加していくと考える．辺を後ろから追加していった時の「不便さ」を逆にしたものが求める答えになる． 辺を１つ追加したときに改善される「不便さ」は辺の両端の頂点それ…
問題 解法 解答 問題 atcoder.jp 解法 各クエリごとに x_i より左にある最寄りの神社・寺，x_i より右にある最寄りの神社・寺の場所を計算する．これは std::lower_bound() や std::upper_bound() を用いて O(logA), O(logB) で計算できる．あとは，神社と寺…
問題 解法 解答 問題 atcoder.jp 解法 A, B >= 10^12 と大きいので愚直な計算では TLE となってしまう． ここで，答えとなる数の k bit 目を明らかにすることを考える．0 から順番に数を 2 進数表記で書いて眺めてみると，1 bit 目は 0, 1, 0, 1, ... と 0, …
問題 解法 解答 問題 atcoder.jp 解法 dp(i) := マッチ棒を i 本ちょうど使って出来る最大の数 と DP を定義する．このとき，遷移時に A_i を全て試し，その中で最大の数を DP の答えにすればよい．答えとなる数は非常に大きくなるので，文字列として扱う．O…
問題 解法 解答 問題 atcoder.jp 解法 K の i bit 目を K_i，K より小さい数 X の i bit 目を X_i とすると， K_40 = X_40 K_39 = X_39 ... K_i > X_i (0 <= i <= 40) となる．ここで，X_(i - 1), X_(i - 2), ... , X_0 は 0 でも 1 でもよい（K との大小に…
問題 解法 解答 問題 atcoder.jp 解法 自分と相手にとって幸福度の高いものを食べたいと考えると，(a_i + b_i) が大きいものから食べていけば最適だと気付く．言い方を変えると，最初に求める答えが -(b_1 + b_2 + ... + b_N) だった場合，ここに最大の (a_i…
問題 解法 解答 問題 atcoder.jp 解法 まず，N 個の寿司を「おいしさ」が大きい順にソートし，大きいものから K 個選び答えの候補にする．このとき選んだ寿司のネタの種類数が k だとしたとき，1 ~ (k - 1) 種類のネタだけで K 個選ぶことは不可能 or 最適で…
問題 解法 解答 問題 atcoder.jp 解法 まず，A_i < B_i の状況であるものは必ず A_i を B_i まで上げる必要があるのでこれらは答えの個数に加わる． 上げる必要がある準備度の総和を sum とし，準備度が十分であるものの余剰分（B_i - A_i）を降順ソートした…
問題 解法 解答 問題 atcoder.jp 解法 問題文の条件より，i 枚目のコインをある頂点 v に置くと決めた場合，(i + 1) 枚目以降のコインを頂点 v とその子孫の頂点に置くことが出来なくなる．よって，1 枚目のコインから順に置く場所を決めていく． (i - 1) 枚…
問題 解法 解答 問題 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 を満たす整数） …
問題 解法 解答 問題 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 解法 自然数 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 解法 2^31 の位から 2^0 の位の順に答えを決定していくことを考える．なぜならば，2^k の位が 1 にすることが可能であるならば，2^k の位をパスしより小さい位で 1 としたとしても答えを 2^k の位を 1 としたときよりも…
問題 解法 解答 問題 beta.atcoder.jp 解法 P_i の最大値を maxP，Q_i の最大値を maxQ とおく．この時，maxP を 1 ~ N で動かすとき，maxQ は [ N / maxP ] になる．P の通り数は maxP^10 - (maxP - 1)^10 になる（なぜならば，最終的な通り数を求める段階…
問題 解法 解答 問題 beta.atcoder.jp 解法 ぱっと見 DP をしたい気持ちになるので，以下のように DP を定義する： dp(h, w) := スタートから h 行 w 列に行くまでのあみだくじの通り数の合計 後は，DP の遷移を考える．この時，今いる行の次（すなわち h + …
問題 解法 解答 問題 beta.atcoder.jp 解法 (x, y) の組をグラフ上の１つの頂点に対応させて考える．(x, y) に１回操作してなる数の組 (tx, ty) から (x, y) に辺を張る．そうすると，(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる…
問題 解法 解答 問題 beta.atcoder.jp 解法 問題を読むと DP という気持ちになるので，以下のように DP を定義する： dp(i, f) := i 番目の要素まで見たときの最大値（f が true の時，効用を０にすることが可能で，f が false の時，効用を０に出来ない） f…
問題 解法 解答 問題 beta.atcoder.jp 解法 偶数行・列の長さの累積和と奇数行・列の長さの累積和の２つを計算しておく．そうすれば，各クエリにおいて座標が (偶数，偶数) と (奇数，奇数) の黒マスの面積の合計が O(1) で計算でき，この２つを足し合わせれ…
問題 解法 解答 問題 beta.atcoder.jp 解法 小さい数，大きい数，小さい数，... のように並べていくのが最適だと分かるので，隣り合う要素の差の合計の式を書くと， (a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n) になる．ここで，両端の要素を除いた …
問題 解法 解答 問題 beta.atcoder.jp 解法 N 個の建物から K 個選び，それらを左から高さが増加していくようにすることを考える．制約より，選び方を bit 全探索する．i 番目の建物の前までの max を前計算で求めて置き，K 個選んだあとは，前計算の結果も…
問題 解法 解答 問題 beta.atcoder.jp 解法 「ゾンビ島」（ JOI 2015/2016 予選 問題５ ）にめちゃくちゃ似ている（というかほぼそのまま）． イノシシがいるマスから BFS で各マスのイノシシのいるマスまでの最短距離を調べる．ここで，最短距離が X 以下で…
