【競プロ精進日記】AtCoder ABC148

2020.03.26
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Round One
$$ 6 \ – A -B $$
https://atcoder.jp/contests/abc148/submissions/9054568

B

B – Strings with the Same Length
$S_i$と$T_i$を交互に出力
https://atcoder.jp/contests/abc148/submissions/9055812

C

C – Snack
$$ lcm(a, b) $$
https://atcoder.jp/contests/abc148/submissions/11205476

D

D – Brick Break
とりあえず砕かれた後にi番目の数がiという条件を満たす必要があります。
これは1番目から見ていって条件に満たさないブロックを砕くだけです。
今まで砕いたかどうかで現在何番目を把握しておけば簡単です。
最小の個数を出力するのですが、最初のブロックを砕いてしまって後のブロックを砕かない方がいいことはありません。
最初のブロックを残しておいた方が後に続くブロックの数が多くなりますからね。
また、条件を満たすブロックを作れない、つまりすべてのブロックを砕くしかない場合-1を出力します。
https://atcoder.jp/contests/abc148/submissions/9072225

E

E – Double Factorial
意外と難しいですね。
10を生み出すためには2×5です。
そのため、nが奇数のときは素因数に2を持たないため出力は0です。
偶数のときを考えると、10を生み出すために必要な2は5に比べて十分にあります。
そのため、偶数列の素因数に5をいくつ含むかを考えましょう。
単純にn/5をしてしまいそうですが、これでは1からnまでに5で割れる数の個数になってしまいます。
問題は偶数列なので、はじめにnを2で割りましょう。すると、偶数列を1からの連続する数列に直せます。素因数に5を含む数を2で割ってもその個数は変わりません。
ここまでくれば、1からn/2までに5で割れる数がいくつあるかなので、5で割った数がそのまま個数になります。
ここで終わりではなく、実際は$5^2,5^3\ldots$と続いていくので、((n/2)/5)/5,(((n/2)/5)/5)といったように数を足し合わせていったものが答えになります。
はじめに2で割るというのがポイントですね。
https://atcoder.jp/contests/abc148/submissions/11206075

F

F – Playing Tag on Tree
最適なのは高橋君が青木君より遠い最も離れている頂点（木なので行き止まり）に行き、青木君がその行き止まりで追い詰める戦略です。
木だということを考えれば、高橋君はかならず行き止まりに行きます。どの行き止まりにいくかは青木君より遠くて最も離れている頂点にいくべきということだけです。
逃げるなら遠くに逃げた方がいいですからね。同じことを2度言いました。
行き止まりに行った後は無駄に動かずに、となりの頂点と反復移動します。無駄に動くと青木君に近づいてしまうため最適ではないです。
これを適切に実装すればACです。
まず、高橋君の頂点$u$からの距離$d_u$、青木君の頂点$v$からの距離$d_v$を計算しましょう。
それから、どの頂点にいくと最適かを全通り（$N$頂点）調べます。
条件は$d_u[i]\lt d_v[i]$となる頂点です（初期状態の頂点がこの条件を満たすため必ず存在する）。
その頂点でゲーム終了までに青木君が移動する回数は、高橋君がその頂点に行くための距離$d_u[i]$＋高橋君が青木君が来るまでその場で反復移動する距離$d_v[i] – d_u[i] – 1$になります。
反復移動する距離が$d_v[i] – d_u[i] – 1$で計算できるのは、図に書くとわかりやすいです。
高橋君が行き止まりに移動するまで、高橋君と青木君の距離は一定（$d_v[i] – d_u[i]$）であることと、出力は青木君が移動する回数ということに注意してください。
以上より、条件を満たす頂点のうち計算した移動回数の最大値を出力すればACです。
https://atcoder.jp/contests/abc148/submissions/11206504