読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

ABC

AtCoderBeginnerContest 054 D

ABC

問題 abc054.contest.atcoder.jp 考察 薬品を買うか買わないかの2通り,その選択をN回行う 通り 通りの買い方の中から,比がになる薬品の買い方を見ていく。そして、その買い方の中で最小の予算を求める 番目の薬品までを見た時,タイプの総量が,タイプの総量が…

AtCoderBeginnerContest 010 D 浮気予防

問題 abc010.contest.atcoder.jp解説見て蟻本写経して通しました。 考察 当初、複数のを含む連結成分を探して,橋を見つけてそれを消していけば良いのかなぐらいに考えてたけど、そこから何も分からなかったので解説を見て最大フローを求める問題と分かった。…

AtCoderBeginnerContest 021 D 多重ループ

ABC

問題 abc021.contest.atcoder.jp過去問埋めで久々のABC D問題の自力AC 考察 という性質から,内の複数のの間で重複した値が許されるということが分かる。これは結局,までの範囲の数値から個の数値を重複を許し,取り出すことと同じ。例えば,までの範囲の数値か…

AtCoderBeginnerContest 050 D

問題 abc050.contest.atcoder.jp解説見て通しました。 考察 これ以下の記述は自分が公式解説放送見ながら書いたメモみたいなものです。・(は問題文での) ・(は問題文での) 以上の式がある。 (aのiビット目)と(bのiビット目)に注目して考えると、とを入れ替え…

AtCoderBeginnerContest 044 D

ABC

問題 abc044.contest.atcoder.jp 考察 解説見てAC。・bを探索したいが,全探索をしてしまうと最大になってとなり、間に合わない。・ここでの場合にnをb進数で表現すると2桁以下になることに気付くととの範囲に分けてbを探索できることに気付ける。・nをb進数…

AtCoder Beginner Contest 014 D 閉路

ABC

問題 abc014.contest.atcoder.jp 考察 追加辺を(a,b)間につなげた場合に出来る閉路の長さ(辺の長さ)を求めるということなので、aのノードとbのノードから追加辺以外の辺を辿って最も早く合流できるノードcが分かれば、 cとaの間の長さ + cとbの間の長さ = (a…

AtCoder Beginner Contest 017 D サプリメント

ABC

問題 abc017.contest.atcoder.jp 考察 部分点まで自力で行けたけど、満点解法は解説を見ながら、AC。解法としてはしゃくとり法をしつつ、DPをしていく。dp[i] = i番目のサプリメントまでを見た時の摂取方法の組み合わせdp[i] := dp[i - 1] + dp[i - 2] + ...…

AtCoder Beginner Contest 023 D 射撃王

ABC

問題 abc023.contest.atcoder.jp 考察 まず解法として最初に思い浮かんだのは、その時点の高さが最大の風船を割っていく貪欲だが、 風船iと風船jがあり、H[i] S[j]であると、ある時点では風船jの方が割られる風船だが、 最終的な高さは風船iの方が高くなる可…

AtCoder Beginner Contest 038 D プレゼント

ABC

問題 abc038.contest.atcoder.jp 考え 部分点までは自力で行けたけど、満点解法は分からずで、解説などを見て通しました。主に2通りの解き方があるらしい。1つ目は公式解説であるようなセグメントツリーというデータ構造を使う方法。セグメントツリーは蟻本…

AtCoderBeginnerContest 005 D おいしいたこ焼きの焼き方

ABC

問題文 abc005.contest.atcoder.jp 考え 一度に焼ける個数Pが、ある区画内( 最左上(y , x)で最右下(y + H,x + W)である範囲 )の焼ける場所の個数(H * W個)以上であれば、その区画内の場所をすべて使ってたこ焼きを焼くことが出来る。 まず、たこ焼きの美味し…

AtCoderBeginnerContest003 D AtCoder社の冬 (メモ用)

問題 abc003.contest.atcoder.jp 考え 部分点解法はX * Y = D + Lなので、X * Yの範囲内でD個のデスクを置く組み合わせ(X * Y)C(D)と残ったX * Y - Dの範囲内でL個のラックを置く組み合わせ (X * Y - D)C(L)を掛け、それを(R - X + 1) * (C - Y + 1)回掛けつ…

AtCoderBeginnerContest030 D へんてこ辞書 (メモ用)

問題 abc030.contest.atcoder.jp 考え 単語を調べるステップ数kが(1 ≦ k ≦ 10^100000)の範囲なので、long型でも収まらない。だけど今回は公式の解説でもあるように多倍長を使わずに解ける。 参考:AtCoder Beginner Contest 030 解説 一度調べた単語をもう一…