[AtCoder 参加感想] 2019/10/19:ABC 143

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■	■	■	■	■	■
結果	AC	AC	AC	AC	AC	AC

全体感想
問題B – TAKOYAKI FESTIVAL 2019
問題D – Triangles
問題E – Travel by Car
問題F – Distinct Numbers

全体感想

94分6完（2ペナルティ）で88位でした。

ふああーーー。

一時期、大真面目な全力プレイで、2000位をうろうろしていました。4桁順位は過去にないのですが…。普段この順位帯は意識していないのですが、D問題まで参加者の半数が解いちゃうんですね。

・C：Bより簡単？
・D：誤読等、色々やらかしたあげく大変なことになりました。
・E：脳内で解けたのが22:29台だったのです。そこから5分でミスなく実装しきったのはエラいぞ！ここは自画自賛していきます。

E,Fともに綺麗な問題で満足度が高かったです。

私の出来としては…最後まで追い詰められた徒労感はありましたが、意外とEFはスムーズに解けていてそこは良かったかな。

問題B – TAKOYAKI FESTIVAL 2019

$O(N)$ 解法を2つ挙げておきます。

(1) 右側のタコで場合分けをします。$d_id_j(i<j)$ としたときの $j$ ですね。広い探索空間を上手くまとめて扱う際には、明確に場合分けの基準を設定するのが基礎ですね。式としては
$d_2(d_1) + d_3(d_1+d_2) + d_4(d_1+d_2+d_3) + \cdots$ という計算になります。累積和の事前計算（$O(N)$）のもと、1件あたり $O(1)$ になります。

解答例 → ■

(2) 次の数式を利用します：$(d_1+\cdots+d_N)^2 = \sum_{i=1}^N d_i^2 + 2\sum_{1\leq i<j\leq N}d_id_j$. したがって、和の2乗から2乗和を引いて2で割ると答です。記号が苦手な方は、$(x+y+z)^2 = (x^2+y^2+z^2) + 2(xy+xz+yz)$ のような式の項が $N$ 個あるバージョンと思えばよいでしょう。

解答例 → ■

問題D – Triangles

三角形の合同類を数え上げてしまって爆死。サンプルも合うし、ランダムなテストケースを作って愚直計算と突き合わせても反例が出てこない。同じ長さの棒も区別してたーーー(>_<)

次のように解きました。

・棒の長さをソートして、$L_1\leq L_2\leq \cdots$ としておく。
・添え字の小さい順に $(L_i,L_j,L_k)$ とする。
・$(i,j)$ に対して $k$ の個数を数える（明確な場合分けの基準を作って考える）。
・$k$ の満たすべき条件は、$j < k$ かつ $L_k < L_i+L_j$ となる。

よって、$L_k < L_i+L_j$ となる $k$ の上限（ソートされているので、$k$ の個数といってもよい）を手に入れればよいです。

これは、各 $x$ に対して、$L_k \leqq x$ となる $k$ の個数を事前計算しておくことで達成できます。この事前計算は、$L$ の度数分布を求めて累積和をとればよくて、$O(\max L)$ です。

全体では$O(N^2 + \max L)$ となっています。

問題E – Travel by Car

$Q\leqq N(N-1)$ という制約から、「クエリごとに上手く計算する」ではなくて、結局「全2点対に対して計算しなくてはいけない」ことが分かります。これを考察の基礎とします。

全点対距離の計算アルゴリズムとしては、ワーシャル-フロイド法が思い浮かびます。

これはおおざっぱに言えば、「$i$ から $j$ に向かう経路の経由地 $k$ をとったとき、$(i,k)$ 間、$(k,j)$ 間での最短経路をつないたものが $(i,j)$ 間の最短経路である」という性質に依っています。

今回の問題は色々と厄介です。「$i$ から $j$ への距離」と言っても、燃料の残量に応じて挙動が変わります。特に、「$(i,k)$ 間の情報」「$(k,j)$ 間の情報」を上手くマージして「$(i,j)$ 間の情報」とする方法がなかなか見当たりませんでした。

結局、残量ごとの状態を持つなんて無理なので、「残量フルの状態」だけを利用して何とかするしかないと思います。すると、全体の移動を「残量フルのタイミング」を区切りとして見ることになって、

「ある点に移動 → 補充 → ある点に移動 → 補充 → …」

という単純な構造に見えてきます（補充しない連続移動をまとめる）。

ここまで来ると、一気に解法が見えました。持つ情報は「ある点で残量フルの状態から補充なしに到達できる点集合」となりますし、そこから「補充なしの移動をコスト1と考えたグラフを作る」も難しい発想ではありません。以上を実装してACを得ます。

pythonでは、floyd_warshall法は、scipyを利用することで、コード量も少なくパフォーマンスもよく実装できます。pythonは高級言語（低級処理を呼び出して組み合わせたりするのが得意）であって、低級処理は苦手ですので、世の中にある基礎的な仕組みは、1から書こうとせずに拾ってくるのが基本的な考え方です。是非確認してみてください。

なお、補給があると、単純な意味での最短経路長と、最適な経路は一致しません↓

4回と6回ですｗ
— maspy_stars (@maspy_stars) October 19, 2019

問題F – Distinct Numbers

ちょっと解説 pdf と異なる考え方となったと思います。まず最初に考えたこととして、

・個数分布しか関係ない

・たくさんあるものから処分していきたい → 貪欲戦略？

ということです。$K=2$ の場合には、

各頂点の次数が $d_1,d_2,\ldots,d_N$ であるような単純グラフは存在するか？

という問題が類似で、これも存在するならば次数が大きい所から処理していくのですが…私はこの問題をどこで見たのかな？わかんないや。

というわけで、貪欲戦略が最適と予想しながら進めます（結果的には貪欲の最適性を証明する必要はなかった）。

実例を作ってると、かなり偏らせないと全部取り切れる気持ちになってきます。

絶対取り切れないのは → 「100,4,3,2」みたいに偏った個数分布のとき → 最大個数が絶対余る！

最大個数が絶対余りそうな条件を考えます。個数を $a_1\leq \cdots a_n$ としたとき、$n$ 番目のものを1つ処分するために、$a_1$ から $a_{n-1}$ までを合計 $K-1$ 個処分する必要があります。

以下、$S = \sum a_i$ とします。

【分かったこと】アイテム $n$ を取り切るには、$S\geqq Ka_n$ が必要。
【分かったこと】 $S < Ka_n$ のとき、アイテム $n$ は必ず余る。
【示せそうなこと】 $S \geqq Ka_n$ のとき、 $\lfloor \frac{S}{K}\rfloor$ 回の操作を実現できる。

示せそうなこと、の証明を考えます。こういうの、漠然と「貪欲の最適性を示す」と思うと証明しにくいけれど、「〇〇の条件のとき××回であることを示す」と定量的な主張を書き起こせた時点で割と勝ちで、簡単です。

・反例となる最小の $S$ のときを考える。$S = Ka_n$ としてよい。
・貪欲に1回とる。$S$ は $K$ 減少する。最大個数も $1$ 減少することが示せれば、仮定が維持できて最小性に矛盾させられる。$S = Ka_n$ のもと、最大個数ものは $K$ 個以下しかないのでよい。

というわけで、【示せそうなこと】も示せました。

したがって、次の方法で問題の判定が行えます。度数分布ソートしたものを $A = [a_1,\ldots,a_n]$ と書きます。

(1) $S\geqq Ka_n$ のとき：全部取り切れる。答は $\lfloor \frac{S}{K}\rfloor$ に等しい。
(2) $S < Ka_n$ のとき：どうあがいても番号 $n$ のアイテムを取り切るのは不可能。よって、毎回番号 $n$ は選ぶとしてよい。番号 $1,2,\ldots,n-1$ のアイテムに対して、$K-1$ の場合の問題を解けばよい。

$K=1,2,\ldots$ と増やしていって、$S\geqq Ka_n$ ならば答を出す。そうでなければ、$A$ の最大値を削除、$K$を1つ減らしてリトライ。を繰り返すことで答が出ます(「$K$ を1減らす」は実装時には、実際のループ変数はいじらずに、減らす個数を $K$ と別に持つことになります）。