AtCoder Beginner Contest 334 F問題 Christmas Present 2
問題
提出解答
解法
座標平面上の点 を とする.
動的計画法で解く. に対して, で, 問題を へ制限したときの距離の総和の最小値とする. このとき, 最終解答は になる.
ベースケースは のときで, このとき, 経由すべき点がないことから, 移動が発生しないので, である.
遷移式を考える. のときに, 連続して配るプレゼントの個数 で場合分けをする. 連続して 個配る場合における距離の総和を最小化する移動の方法は, 以下の手順をたどることになる.
- 点 から 点 へ移動.
- に対して, 点 から へ移動.
- 点 から点 へ移動.
- それ以降は を達成するように移動する.
よって, この場合における距離の総和の最小値は
となる.
これを について動かすことによって, の値は
となる.
ここで, とおくことにすると,
となる.
また, に対して,
とおくことにすると,
となる.
ここで, について,
が成り立つ.
は によらない一定の値である.
したがって, 次のことが高速にできるデータ構造があれば高速に を計算できる.
これを可能にするデータ構造としては遅延評価セグメント木がある.
よって, を遅延評価セグメント木によって適切に区間作用を行い を計算することによって, を 時間で求めることができる.
AtCoder Beginner Contest 314 F問題 A Certain Game
問題
提出解答
解法
「データ構造をマージする一般的なテク」を利用して, この問題を解く.
- 以下のものを用意する.
- を頂点に持つ Union-Find .
- に対して, とする.
- は頂点 を代表元に持つ連結成分におけるベースとなる期待値を記録する.
- は が属する連結成分の代表元を としたときの と, その時点での勝利回数の期待値との差を記録する.
- に対して, を の一要素のみからなるリストとする.
- の順に以下を行う.
- において, が属する連結成分の頂点数が, に属する連結成分の頂点数より大きいならば, を入れ替える.
- を における の代表元, における代表元に置き換える.
- において, が属する連結成分の頂点数をそれぞれ とする.
- の各頂点 について, に を加算する.
- に を加算する.
- に の全ての要素を付け加える.
- において, を併合する.
最後に残る唯一の連結成分の代表現を としたとき, のそれぞれに対する正解は, である.
AtCoder Beginner Contest 304 C問題 Subscribers
問題
提出解答
問題の概要
座標平面上に 人の人がいる. 人 は座標 にいる.
ウイルス V は感染した人から (Euclid) 距離で 以下にいる人全てに感染させる能力を持っている.
ある時, 人 がウイルス V に感染した. そして, 十分長い時間が経過した時, 各人はウイルス V に感染しているか?
制約
解法
実際に, 人 1 から距離が 以下の人に対して, ウイルス V を感染させていくシミュレーションを行えば良い. ただし, 一度感染したひとに関する調査はスキップしなければならない.
ちなみに, これはあるグラフ上の BFS となる, 実際, 次のような無向グラフ における頂点 が属する連結成分を調べていることと同等である.
は の辺の構成について, 全ての組み合わせについて見る必要があるので, 時間かかり, 最大で 本となる.
よって, 計算量は BFS によって, 時間となる.
AtCoder Beginner Contest 304 B問題 Subscribers
問題
提出解答
問題の概要
の値に応じて, 以下の処理をせよ.
- ならば, を出力せよ.
- ならば, の一の位を切り捨てた整数を出力せよ.
- ならば, の十の位以下を切り捨てた整数を出力せよ.
- ならば, の百の位以下を切り捨てた整数を出力せよ.
- ならば, の千の位以下を切り捨てた整数を出力せよ.
- ならば, の万の位以下を切り捨てた整数を出力せよ.
- ならば, の十万の位以下を切り捨てた整数を出力せよ.
制約
解法
上の場合分けをそのまま実装してもよいが, のときは命令をよく見ていみると, 上3桁以外を切り捨てろという処理であるから, 次のようにして出力すべき整数を求めることができる.
- の桁数を とする. 出力すべき整数は の上3桁に を掛けた整数である.
の上3桁については, を文字列とすると簡単に取得できる.
また, のときはそのまま を出力することに注意.
AtCoder Beginner Contest 304 A問題 First Player
問題
提出解答
問題の概要
人が時計回りに座っている. 番目の人の名前は で, 年齢は である.
人は の順に並んでいる.
なお, 人の名前は全員異なり, 年齢も全員異なる.
年齢が最も小さい人から順に時計回りで 人出力せよ.
制約
- は英小文字からなる長さ 以上 以下の文字列.
- は全て異なる.
- は全て異なる.
解法
次のようにすればよい.
- を求める.
- を満たす を求める.
- 以下を 回繰り返す.
- を出力する.
- に を加算する. その後, ならば, とする.
AtCoder Regular Contest 161 B問題 Exactly Three Bits
問題
提出解答
(※ C++ での提出) atcoder.jp
問題の概要
以下の正の整数 で以下を満たすものは存在するか? 存在するならばそのような整数のうちの最大値を求めよ.
- を 進法表記したときに現れる の個数がちょうど である.
個のマルチテストケース
制約
解法
条件を満たす のうち, 最小の正の整数は なので, の範囲では存在しないとなる.
以降では とする.
を 以下の非負整数で, 進法表記したときに現れる の個数がちょうど であるような非負整数のうち, 最大であるようなものと定義する (存在しない場合は ).
このとき, 次のようにして場合分けすることによって, 帰納的に導くことができる.
- の場合, 以下の正の整数は存在しないので, である.
- の場合, を 以下を満たす整数として, である.
- が奇数のとき, の位をどうするかで場合分けすることにより, となる.
- が偶数のとき, の位をどうするかで場合分けすることにより, となる.
これにより, 求めるべきは である. また, に出てくる引数の候補は 個であるので, を 時間で求めることができる.
これは 個のテストケースの下では, 高速な言語を使用することによって, 正解することができる.
AtCoder Regular Contest 161 A問題 A Make M
問題
提出解答
問題の概要
長さが奇数である整数列 に対して, 以下を満たすとき, は M 型であるという.
を奇数とする. 長さ の整数列 が与えられる. を適切に並び替えることによって, M 型にすることは可能か?
制約
- は奇数である.
解法
以下は同値である.
- を適切に並び替えると, M 型にすることができる.
- を昇順に並び替えた列を とし, とすると,
(下) ならば (上) は明らかなので, (上) ならば (下) を証明する.
を並び替えることによって, は M 型であるとする. このとき, の奇数項目の最小値を とする.
このとき, の奇数項目に より大きい整数が, の偶数項目に より小さい整数が存在する場合, これら 項は交換しても M 型を保ったままである.
このようにすることで, の奇数項目は全て 以下, 偶数項目が全て 以上にすることができる.
また, このときの に含まれる については以下のうちのどちらかが成り立つ.
- の奇数項目が全て で, の偶数項目は全て より大きい.
- の奇数項目にある の数と の偶数項目にある の数 (要するに にある の数) が 個以下.
どちらの場合にしても, 奇数項目, 偶数項目それぞれ昇順に並び替えることによって, は (下) での操作の結果による並び替えになり, M 型にもなる.