2020-02-11

AOJ 2334 - 街を駆ける道

解法

明らかに、線分 $AB$ と $CD$ が交差しない場合は、それぞれの街を直接結ぶのが一番距離が短くて済みます。
つまり、今回考えるべきなのは、 $AB$ と $CD$ が交差する場合になります。
このとき、仮に $AB$ の経路を、 $CD$ と交差しないように迂回して作成したとすると、どのように迂回しても、 $CD$ については、そのまま直接結べることがわかります。これは $CD$ が遠回りになった場合も同様です。
ので、 $AB$ , $CD$ のうちどちらかは直接結んだまま、もう片方を遠回りの経路にした際の最小コストが求まればよいです。
遠回りの経路は、直接結んだ線分と交差しないようにしつつ、ダイクストラ法を用いることで計算できます。

2020-02-10

AOJ 2585 - 一日乗車券

ダイクストラ法

問題
 提出コード

解法

1日乗り放題になる路線をビットで表したものが $s$ となるようにする際の、1Dayパスポートの合計金額の最小値

をまず求めます。
これは、配るDPを用いて、 $v_{i OR j} = min(v_{i OR j},v_{i} + v_{j})$ を繰り返し計算していけばよいです。 $O(4^{K})$ で求まります。
では、乗り放題の路線を決め打ちして $s$ とした際の、 $S$ から $T$ へ行く方法の中で、金額が最小になるものを調べます。
これは、

$dp_{ij} = i$ 時間後に $j$ にいるような行き方のなかでの金額の最小値

とすると、グラフを拡張してダイクストラ法を使ってあげれば、 $min(dp_{iT}$ が答えになります。
初期値は、 $dp_{0S} = v_{s}$ です。
これを全ての状態 $s$ について調べ、その最小値を求めれば答えが求まります。

感想

はじめ、 $K$ が24以下であると勘違いして、間に合わないなぁ…って言ってました。状態が少し複雑になるだけでバグを埋め込みやすいので、バグ少なめでかけた点についてはよかったです。

2020-01-26

ABC153 F - Silver Fox vs Monster

貪欲法 Binary Indexed Tree(BIT)

問題
 提出コード

解法

$H_{i}$ について、 $A$ で割り、切り上げをしておきます。これで、 $H_{i}$ が

$i$ 番目のモンスターを倒すまでにかかる攻撃回数

となります。加えて、全てのモンスターを、 $X_{i}$ の昇順で並び替えます。

1番目のモンスターについて考えると、 $H_{i}$ 回どこかで攻撃しなければなりません。このモンスターへの攻撃を最適化することを考えると、 $X_{1} + D$ の地点を攻撃することが最適です。なぜなら、これより右側の地点を攻撃しても $X_{1}$ を攻撃することはできず、これより左側の攻撃を攻撃をしても、1番目のモンスターよりも左側にモンスターは存在しないので、得をしません(右側にはモンスターがまだいる可能性があるので、できるだけ右側も攻撃できるようにするべきです)。
すると、 $[X_{1},X_{1} + 2D]$ の区間内に存在するモンスターは、 $H_{1}$ 回攻撃されることになります。
すると、1番目のモンスターを除去し、先ほどの区間内に存在するモンスターについて $H_{1}$ 回攻撃を与えた後の状況について考えればよいことになります。これを繰り返すと、前から順番に、 $i$ 番目のモンスターに攻撃すべき残り回数分だけ、 $X_{i} + D$ で攻撃を行う、という操作を前から順番に繰り返せばよいです。
攻撃を行った回数のリストを作成します。範囲攻撃なので、ある区間について同じ値を足したいのですが、 $[i,j)$ についての区間加算を、BIT上でいもす法のように、 $i$ に値を加算、 $j$ から値を引くことで表現します。
すると、今までで $i$ 番目のモンスターに攻撃した回数が、BITにおける1から $i$ までの値の総和を計算することで計算できるようになります。
また、 $X_{i} + D$ を攻撃した際にダメージを与えられないモンスターのインデックスの最小値 $r$ を計算するための変数を用意しておきます。初期値は左端のインデックスとしておきます。
今 $i$ 番目のモンスターについて処理を行う際、

攻撃した回数が $X_{i}$ を超えている場合
スルーします。
超えていない場合
残り攻撃すべき回数を $P$ とします。
$r$ を計算します。しゃくとり法のように $r$ をインクリメントしていき、 $X_{j} + 2 D$ を超える最小の $j$ を新たな $r$ とします。
すると、今回の処理で $[i,r)$ に $P$ 回攻撃することになります。
答えに $P$ を加算します。
BITの処理は、 $i$ の部分に $P$ を加算し、 $r$ の部分から $P$ を減らします。

これを繰り返すことで、答えを求めることができます。

2020-01-26

ABC153 E - Crested Ibis vs Monster

動的計画法(DP)

問題
 提出コード(1)
提出コード(2)

解法

$dp[i][j] = i$ 番目までの魔法を撃ち終えて、 $j$ だけダメージを与えたときに消費する魔力の最小値
とすると、

$j \geqq A_{i}$ のとき
$dp[i +1][j] = min(dp[i][j],dp[i + 1][j - A_{i}] + B_{i})$
$j \lt A_{i}$ のとき
$dp[i + 1][j] = dp[i][j]$

となります。
初期値は $dp[0][0] = 0$ 、答えは、 $min(dp[N][j]) (j \geqq H)$ です。
見るべき $j$ の範囲は、 $H + max(A_{i})$ までなので、最大でも $2 \times 10^{4}$ 程度になり、このDPによる計算が間に合います。
これが提出コード(2)です。

$dp[i][j] = i$ 番目までの魔法を撃ち終えて、 $j$ 以上ダメージを与えたときに消費する魔力の最小値
とすると、
$dp[i + 1][j] = min(dp[i][j],dp[i + 1][max(0,j-A_{i})] + B_{i})$

となります。初期値は上と同様、答えは $dp[N][H]$ です。
これが提出コード(1)になります。

2020-01-20

AOJ 2631 - Clique Coloring

問題
 提出コード

解法

それぞれの頂点について、 $i$ 回目に選ばれたか選ばれてないか、について考えると、 $2^{n}$ パターンあります。
これらをビットで表すと、 $\sum (立っているビットの数-1)$ だけ、全体から1つ頂点を減らすことができます。
また、 $i$ 回目と $j$ 回目に同時に選ばれる頂点が2つ以上あることはありません。
つまり、2つ以上ビットが立っているパターンについては、そのような頂点があるか、ないかの2択になります。
2つ以上ビットが立っているパターンは、 $2^{n} - n - 1$ 通り(1つもビットが立ってないのが1通り、1つのみビットが立っているのが $n$ 通り)ありますが、この値を $X$ として、 $2^{X}$ 通りのパターンについて枝刈り全探索をすればよいです。
$i,j$ が同時に立っているビットを既に選択したかどうか、次にどのパターンを選択するか、そして現在いくつの頂点を削減できたか、の情報を引数にもち、再帰でDFSをしました。
今見ているパターンを選択する場合は、引数にある $i,j$ が同時に立っているビットの情報を更新(矛盾すればその場で打ち切り)、それぞれの立っているビットについて選ばれた回数を計算( $a_{i}$ を超えることはできません)し、再帰をします。

感想

数週間考えました…
このタイプは苦手です。

2020-01-19

ABC152 F - Tree and Constraints

包除原理

問題
 提出コード

解法

あらかじめ、頂点 $i$ から $j$ へのパスに使われる辺の集合を表すビット列 $T_{ij}$ を、前計算で計算しておきます。これは、任意の頂点 $i$ からBFSで辿っていけば良いです。
$M$ 個の条件からいくつか選んだ、条件の集合 $S$ に対して以下のような数を計算します。

少なくとも $S$ に含まれる条件を全て満たさないような辺の色の決め方の場合の数

すると、包除原理によって、 $S$ に含まれる条件の個数が偶数なら求めた値を加算、奇数なら減算、を $2^{M}$ 通りの全ての $S$ について繰り返すと、求める答えとなります。

上で計算したかった値を $C_{S}$ とします。
$S$ に含まれる条件は全て満たさない、という仮定があるので、 $S$ に含まれる条件に指定されている辺は全て白くしなければなりません。
逆に、それ以外の辺については何も制約がないので、黒白どちらでも問題ありません。
条件に指定されていない辺の個数を $X$ とすると、
$C_{S} = 2^{X}$ となります。
あとは $S$ に対する $X$ が求まればよいです。
これは、 $S$ に含まれる全ての条件について使われる辺を洗いだし、それらの和集合を求めれば、その個数を $N-1$ から引けばよいです。これは、最初に前計算しておいたビット列を用いると、OR演算を用いて簡単に計算することができます。

感想

問題を見た時点で包除っぽい、となってから、 $M$ の制約に気づき、素直に考察が進んだと思います。

2020-01-19

ABC152 E - Flatten

最小公倍数(LCM)

問題
 提出コード

解法

$A_{i}B_{i}$ の値は、明らかに $A_{i}$ 達の最小公倍数になります。
ですが、愚直にやっては途中でオーバーフローをしてしまうため、最小公倍数の素因数を先に列挙してあげることで、後で $10^{9}+7$ でMODを取りながら計算してあげると、オーバーフローせずに最小公倍数を $10^{9} +7$ で割った余りが求められます。
あとは、求めた値を $X$ として、 $B_{i} = X / A_{i}$ の総和を求めてあげればよいです。
素因数を求めるには、全ての $A_{i}$ について、 $O(\sqrt A_{i})$ でそれぞれを素因数分解し、素因数と、その個数を求めます。そして、それぞれの素因数について、その個数の最大値を求めてあげればよいです。