| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
50 分 2 ペナ → 50位。
F がすぐに解けて、「優勝か？」と思ったものの、D と E で詰まりまくりました。むずー。
問題A – Payment
# a / b の切り上げ
x = (a + b - 1) // b
x = -(-a//b)
# a の下側の最寄りの b の倍数
x = a // b * b
x = a - (a % b)
# a の上側の最寄りの b の倍数
x = (a + b - 1) // b * b
x = a + (-a) % b私は特に書き方を固定していないです（良いことではないかも）。
math.ceil(a / b) といった書き方も見かけますが、計算誤差の問題も生じますし、わざわざ小数を経由することでパフォーマンスも悪くなるので、あまり良くないです。本問題の制約であればこれでも正解になります。
問題B – Judge Status Summary
counter = Counter(words)
for x in ['AC', 'WA', 'TLE', 'RE']:
n = counter[x]
print('{} x {}'.format(x, n))数え上げには、collections.Counter がお手軽です。出力部分は4 種をまとめて実装しました。
問題C – H and V
残す行、残す列を全探索しました。
- 一部の行、列を 0 埋めする：https://atcoder.jp/contests/abc173/submissions/14979765
- 部分行列を抽出する：
https://atcoder.jp/contests/abc173/submissions/15008075
残す行だけ決め打って、列について dp すれば、$2^H \times (多項式)$ の時間でも解けそうです。
問題D – Chat in a Circle
しばらく誤読していて消耗（$|A_i-A_j|$ を計算したりしていた）。のあと、すぐに解けなかったので雑を投げてWA。すこし証明に手間取りました。ABC-Dにしては結構難しい問題？？
例えば $10$ 人いて、フレンドリーが $1, 2, \ldots, 10$ だとします。
[10] → [10,9] → [10,7,9,8] → [10,7,9,5,8,6] → [10,4,7,3,9,5,8,6] → [10,4,7,3,9,5,8,1,6,2]といった要領で、各時点で最大スコアが得られる場所にすわっていくことで、$10+9+9+8+8+7+7+6+6$ の点数が獲得できます。このように、降順にソートして、1回・2回・2回・…ととるのが最適です。これを証明します。
フレンドリーさの上位 $n$ 人が合計で $2n-1$ 回しか合計点に寄与しないことを示します。この証明において、上位 $n$ 人とそれ以外の $2$ 種の人間に分けて考えればよいです。
上位陣が上位陣からスコアを得る回数は、高々 $n-1$ 回です（最初に訪れる上位陣が $0$ 回、他は $1$ 回以下）。下位陣が上位陣からスコアを得る回数も、高々 $n$ 回です。最終的な位置関係において、上位陣に囲まれる領域ごとに $1$ 人以下であることから分かります。
※ （本番中、「上位から順に来訪するとしてよい」を示そうとして失敗しましたが、公式解説にあるように簡単でした。）
問題E – Multiplication 4
おおよそどうなるかは一瞬で分かるものの、正確に場合分けなどをこなしきるのは難しいという問題です。
$A_i = 0$ は場合分けする必要がなくて、$A_i \geq 0$ と $A_i < 0$ の $2$ 種があると思って考えます。
負の数は、偶数個をつかって正の数を目指しつつ、絶対値を大きくするのが良さそうだという気持ちにはすぐになります。これを詰めていきましょう。
- 積を$0$以上にできない場合
計算結果がマイナスになることを覚悟した瞬間、絶対値の小さい方を優先することになるので、この場合分けを考えました。
これは、「$N=K$」または「全ての $A_i$ が負」に限られることが分かります。そうでないときに積が正となるように選べることを確かめます。「全て負」でないとしたので、$A_1 > 0$ としてよいです。$A_2$ 以降を適当に $K$ 個選びます（$K < N$ より選べる）。積が負であれば、使った負の数と $A_1$ を取り換えることで積が正の選び方になります。
示されました。「$N=K$」「全ての $A_i$ が負」いずれも戦略は簡単なので、あとは実装すれば解けます。
- 積を $0$ 以上にできる場合
負の数は、必ず偶数個で使うことになります。特に絶対値が大きいものから、$x_1,x_2,x_3,x_4,x_5,\ldots$ とすると、負の数は「$x_1x_2,x_3x_4,x_5x_6,\ldots$」という $2$ 個組ずつで選ばれます。
正の数と合わせて考えると、次のようになります：
- 正の数がたくさんある。
- コスト $1$ で手に入る数と、コスト $2$ で手に入る数がある。
- コスト $K$ で積を最大にせよ。
符号がどうでもよくなったので、だいたい大きい順から貪欲すればよさそうです。
私はここから、
- $K$ が奇数なら、コスト $1$ の最大の数をとる。あとは $K-1$ の場合に帰着
- $K$ が偶数なら、コスト $1$ の数も全部で偶数個とることになるので、$2$ 個セットにしてしまう
- あとは $2$ 個組を強い方から $\frac{K}{2}$ 個貪欲に選ぶ。
としました。
こういうの、なかなか一瞬で方針を整理できないのが課題です。上手い人の実装いろいろ見てみよう…。
問題F – Intervals on Tree
閉路のないグラフにおいて、
- 連結成分の個数 = 頂点数 – 辺の数
が成り立ちます。AGC-C の過去問でもでてきて、綺麗に解けたので強く印象に残っています。
これさえあれば、解くのは簡単です。
$$\sum_{L,R}連結成分の個数 = \sum_{L,R}頂点数 – \sum_{L,R} 辺の数$$
と書き換えます。頂点、辺ごとに分解して、頂点 $v$、辺 $e$ に対してそれを含むグラフの個数を $f(v), f(e)$ と書くと、答は $\sum_v f(v) – \sum_e f(e)$ で、$f(v), f(e)$ は簡単に計算できます。
