tookunn’s diary

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

ABC

京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) D - Happy Birthday! 2

ABC

問題 atcoder.jp 考察 数列Aから異なる部分数列B,Cを探してB,Cそれぞれの総和のmod200が同じものを出力する問題。重要な点としては 数列Aから見つかる部分数列は2^N-1通り 部分数列の総和のmod200は200通り 数列Aの長さがある長さ以上になったら、総和のmod2…

AtCoder Beginner Contest 188 D - Snuke Prime

ABC

問題 atcoder.jp 考察 となっていて、区間として範囲が大きいので いもす法という手法を使って、単純に各区間の増減の累積和を取ることができないことが分かる。最初は各区間についてを一組としてまとめて、うまくソートなりなんなりをすれば良さそうと考え…

ZONeエナジー プログラミングコンテスト “HELLO SPACE” C - MAD TEAM

ABC

問題 atcoder.jp 考察 基本方針は 5種類すべての能力がチーム全体として以上にできる3人の組み合わせが存在するかを二分探索で探っていく。3人のチーム全体の各能力は以下の通り、3人の能力の最大値となる。 そして、チームの総合力は以下の通り、チーム全体…

ZONeエナジー プログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ

ABC

問題 atcoder.jp 考察 重要な点は 文字列反転のコストをどう工夫するか 連続した2文字が同じ文字の場合の削除のコストをどう工夫するか 文字列反転については 文字追加の操作を行いながら、反転しているかどうかの状態を持っておき 反転している場合は文字列…

ZONeエナジー プログラミングコンテスト “HELLO SPACE” B - 友好の印

ABC

問題 atcoder.jp 考察 コンテスト本番では上る高さを二分探索で決めて、UFOからその上った高さの位置までの直線を 一次関数y = ax + bの式に当てはめて、各iについて、x = d[i]の時にh[i]以上かどうかで探索していた。 これだと実装が複雑になるし、バグも出…

AtCoder Beginner Contest 190 D - Staircase Sequences

ABC

問題 atcoder.jp 考察 まず、公差1の等差数列の総和の特性を見つけるために 公差1の等差数列の総和を求める式を考える。総和をN、初項をA、項数をLとすると 扱いやすいように両辺に2を掛けて となる。この式から は、またはで割り切れる値だということが分か…

パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195) B - Many Oranges

ABC

問題 atcoder.jp 考察 重要な点としては Aグラム以上Bグラム以下というみかんの重さに下限と上限があること。 みかんの重さが整数とは限らない。 重さの合計がぴったりW(キログラム単位)であること。 みかんの個数Nが分かっている場合、 が成り立てば、N個…

AtCoder Beginner Contest 198 C - Compass Walking

ABC

問題 atcoder.jp 考察 原点(0, 0)からユークリッド距離でRずつしか移動できない。 移動先の座標は整数でなくてもよい。 ぴったり(X, Y)にたどり着かなければならない。 これがこの問題を解くときに大事なポイントだと思われる。原点(0, 0)と(X, Y)間のユーク…

AtCoder Beginner Contest 082/AtCoder Regular Contest 087 D - FT Robot

問題 D - FT Robot 解法 x座標、y座標に分けてDP 文字列Sを連続する'T','F'で分割して考えると、x座標だけ変化する、y座標だけ変化する区間が存在することが分かる。 よって、x座標、y座標の変化は独立して考えることが出来る。 あとはdp[i個目の連続する'F'…

AtCoder Regular Contest 086 C - Not so Diverse

問題 C - Not so Diverse 解法 整数がK種類以下になるまで、個数の少ない整数から書き換えていく(整数を消していくと考えても良い)。まず、各整数ごとに個数をまとめて、次に個数で整数の種類数をまとめていく。 あとはK種類以下の整数になるまで、整数を書…

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 解説 一度調べた単語をもう一…