AtCoder Beginner Contest 137 C - Green Bin
yukicoder No.300 平方数
技術室奥プログラミングコンテスト#4 Day1 D - スキップ
問題概要
個のマス目があり、
個目のマス目には
が書かれている。この内、任意の個数のマス目を選んだ時、選んだマス目の集合
{
}について、
点分のポイントが得られる時、ポイントの最大値を達成する
の要素数の最小値を求める。
解法
のある連続した3要素について考えてみる(下では1,3,5としている)。
ここで、5を飛ばして1から3まで行ったとしても(赤の経路)、両者の差の絶対値は2のため、2ポイントしか得られないため、この時点で最大値を達成することは不可能となってしまう。このような場合は素直に5を飛ばさないで|5-1|+|3-5|=6ポイントを得た方が良い。
反対に、これが1,3,5のような並びであった場合、3を飛ばしても得られるポイントは最終的に同じ6ポイントである。
このことから、連続する要素の内、(左端がその要素の集合中の最小値∧右端が最大値)∨(左端がその要素の集合中の最大値∧右端が最小値)が成り立っていれば両端の2要素以外は全てスキップすることができる。
よって、各について、その直前までの
が増加であったか若しくは減少であったかを見てあげて、直前までは増加しているのに
では減少している、もしくはその逆であれば答えに1を足していけばよい。
ただ、多分これが想定コーナーケースだろうと勝手に思っているが、の全要素が同じ場合、どんな選び方をしてもポイントは0になるため、問題文曰く、遊ばないという選択を取って0を答えとしなければならない。
これを実装して、AC。。
AtCoder Beginner Contest 135 D - Digits Parade
問題概要
文字列が与えられる。
に含まれる?の文字を数字に置き換えて、置き換えた後の文字列を数字と見たとき、13で割ると余りが5になるのは何通りか。
解法
当然、「それぞれの?について0~9まで試せばいいだろ!w」ではでアなのでだめ。
なんか問題がDPしろって言っているように思えるのでDPを考えてみる。
のようなDPを考える。
が?のとき、0~9までの全ての文字について遷移先を計算して、そこに足すと良い。
最終的な答えは、になる。
。
AtCoder Regular Contest 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )
問題概要
2次元平面上の個の点について、
番目と
番目
の点の間の距離が分かっている。この時の
番目の点と
番目の点の距離について考え得るmaxとminを求めよ。
解法
まず、maxは明らかに。
様々なところで言及されているが、入力をソートしても一般性を失わない場合、とりあえずソートしてみると良かったり悪かったりするので降順ソートする。
すると、例えば番目の点が移動可能な範囲は
番目の点を中心とした、半径
の円周上である。
これを拡張して考えるとminは、
\begin{eqnarray}
\left\{
\begin{array}{l}
0(d_0≦\displaystyle \sum_{i=1}^{N-1} d_i) \\
d_0-\displaystyle \sum_{i=1}^{N-1} d_i(otherwise)
\end{array}
\right.
\end{eqnarray}
となる。これを実装して、AC。。
AtCoder Beginner Contest 134 D - Preparing Boxes
問題概要
個の箱が並んでおり、各箱にボールを入れるかどうかを決めることができる。この時、
について、
の倍数が書かれた箱に入っているボールの数の総和を2で割った余りが
であるような入れ方を構成せよ。
解法
箱を昇順に見て行こうとすると、番目の箱にボールを入れるか否かを決めるためには、
番目の箱にボールが入っているかの情報が必要であるが、これは
番目の箱を見ている状態では未知の情報なのでこれではダメ。
逆に、降順に見て行くと、昇順に見て行く時に未知であった情報は既に判明しているので箱を降順に見て行く方針で考える。
これをしようとすると、
①:箱を降順に見て行く
②:①の内側のループで番目の箱を見て行く
というアルゴリズムになり、これはとなり、間に合わなそうなお気持ちになるかもしれないが、
となるため、計算量は
となり、間に合う。
間に合うため、上に書いたアルゴリズムを実装して、AC。
第１５回日本情報オリンピック 予選 E - ゾンビ島 (Zombie Island)
問題概要
個の町と
本の町
を結ぶ道がある。この内の幾つかの町はゾンビに支配されており移動できず、そのような町から
本以下の道路を使って行き来できる町は危険な町である。
町を移動するたびに危険な町かそうでない町かに応じたコスト(問題中では宿泊費)を支払う時、町1から町まで行く時の最小費用を求める。
解法
まず、危険な町の列挙を行う。これは、Dijkstra法を良い感じに使うことによって実現できる。以下にその手法を示す。
手法
町全体の集合に対して、新たに町0を追加して考える。
まず、ゾンビに支配されている町に対しては、町0からその町へ距離0の有向辺を張る。
次に、入力で与えられる辺全てについてはその町同士に距離0の無向辺を張る。
上記の操作を完了した状態で、町0でDijkstra法を行うと、ゾンビに支配されている町には、町0から距離0の辺が伸びているため、最短距離が0で確定する。
それ以外の町については、町0からゾンビに支配されている町への最短距離が0であるから、危険な町からDijkstra法をしているのと同じことになる。つまり、町の町0からの最短距離というものは、町
に最も少ない本数の道を使って行き来できる、ゾンビに支配されている町からの最短距離を表すことになる。
つまり、これにより本以下で辿り着ける全ての町が列挙できた。
以上の操作により、危険な町とそうでない町が判別できるため、入力で与えられる辺の集合を順番に見て行き、辺が町を結ぶ辺である時、
\begin{eqnarray}
\left\{
\begin{array}{l}
A_iが危険な町ならA_iからB_iに対してコストQ、危険な町でないならコストPの無向辺を張る \\ B_iが危険な町ならB_iからA_iに対してコストQ、危険な町でないならコストPの無向辺を張る
\end{array}
\right.
\end{eqnarray}
という操作を行うことにより、移動する上でのコスト面での実装が終了する。
あとは町1からDijkstra法を行うことにより、町への最短距離が求まる。
長かったが、これを実装して、AC。
