ABC143

ABC143 A Curtain

A と B が与えられるので、 A - B * 2 を表示する。ただしマイナスになる場合は 0 と表示する。

印象

やるだけ

解法

問題文どおり条件分岐を書けば ok

ABC143 B TAKOYAKI FESTIVAL 2019

N < 50 個のたこ焼きがあって、 i 番目の大きさが d[i] で与えられる。たこ焼きを２個同時に食べると相乗効果で d[i] * d[j] だけ美味しい。

全通りの組み合わせについて美味しさを計算して、その合計を表示する。

印象

たこ焼き問題、リアルタイムだったので懐かしいw

N が小さいので愚直に二重ループで合計していけば間に合う

解法

二重ループで足していくだけ

ABC143 C Slimes

N <= 10^5 文字の文字列が与えられる。それぞれの文字はスライムの色を表していて、同じ色のスライムが隣り合っているとこれらはいずれ合体する。最終的に何匹のスライムになるか。

印象

文字列を左から順に舐めて、文字の種類が変わったところでカウントを足せば良さそう

C にしてはやや簡単…？

解法

印象通り。たとえば aaabbbccc だったら文字の種類が a -> b, b -> c と二回変わる。これに 1 を加えて、３匹。

ABC143 D Triangles [二分探索２回]

N <= 2 * 10^3 本の棒があって、それぞれの長さが L[i] で与えられる。ここから三本選んで三角形を作りたいとき、何種類の三角形が作れるか。

ただし３つの辺 a, b, c が以下の条件を満たせば三角形は作れる：

a < b + c
b < a + c
c < a + b

印象

三本の組み合わせについて総当たりすると (2 * 10^3)^3 = 8 * 10^9 通りになるので厳しそう。逆に言えば２本ならいける。

２本 (たとえば a, b) を決めると、残りの 1 本に対する条件が

abs(a - b) < b かつ b < a + b

とはっきりするので、これを満たす b を O(log N) で数えられれば良さそう。

辺のリストをあらかじめソートしておけば、二分探索でいけそう。

解法

印象通り。

あらかじめ入力をソートしておいて、二重ループ回して棒二本の組み合わせ (1, 2) <= (i, j) <= (N-1, N) にそれぞれについて：

abs(L[i] - L[j]) < L[k1]

を満たす最小の k1 と、

L[k2] < L[i] + L[j]

を満たす最大の k2 をそれぞれ二分探索で探す（二分探索を２回やる）。

もし k1 <= k2 になったら、その範囲にある棒は条件を満たす（三角形ができる）ので、個数 k2 - k1 + 1 をカウントに加える。ただしすでに選んでいる棒 (i, j) は使えないのでその分だけ引く必要があることに注意。

二分探索がちょっと厄介で、「全ての辺が条件を満たす」パターンとか「すべての辺が条件を満たさない」パターンがありうる。「あらかじめ範囲の両端の棒について条件を満たすか調べて、二分探索するまでもない場合はやらない」とするか、「端に番兵をおいてから二分探索」するといい感じになるはず（番兵法 ... -1 など明らかに条件を満たさない項目を勝手に追加すること。条件を満たさないので結果には影響ない）。

ABC143 E Travel by car [ワーシャルフロイド２回]

N <= 300 個の街がある。 M 本の道 A[i] B[i] C[i] が与えられて、これは街 A[i] から街 B[i] までの距離が C[i] km あることを表している。

この道を容量 L l の燃料タンクを積んだ、燃費 1 k/l の車で移動したい。それぞれの街では給油してタンクを一杯にすることができる（しなくてもよい）が、道の途中で燃料が切れた場合はおしまい。

二つの街の番号 s, t が与えられるので、その間を最小何回の給油で移動できるか求めよ。移動できない場合は -1 と表示する。

印象

街 x 残オイル容量 でダイクストラしたらいけそうかな…？

と思ったけど、燃料タンクの容量がかなりでかいので厳しいか。

一度シンプルなダイクストラをして、その結果を使ってもう一度何かする系か、二種類のダイクストラの結果を組み合わせるとなんか見えてくる系に感じる。

あ、距離でワーシャルフロイドすると、適当な経由地点を取って移動するときに、スタートから経由地点までの距離と経由地点からゴールまでの距離がそれぞれ一撃で求まるので、なんか使えそうかな。

距離でワーシャルフロイドした結果を使うと、離れた２つの街に対しても「その間を給油せずに移動できるか」ももとまるな。それを使って今度は「給油回数」についてワーシャルフロイドすればいけるのでは…？

解法

概ね印象通りでいけた、これは嬉しい！

とりあえず与えられた距離の情報で素朴に「ワーシャルフロイド法」をすると、任意の二つの街について、最短何キロ走ればその間を行き来できるかが求まる (ワーシャルフロイドについてはちゃんと説明できないので検索)。これが L 以下の街は給油一発で行き来できて、 L を超える街は給油一発では行き来できない。

この情報を使って、こんどは「給油一発でいける街の間にだけコスト 1 の道が生えている」ような新しいグラフを作る。このグラフでもう一度ワーシャルフロイドすれば、こんどは任意の二つの街について、最小何回給油すれば移動できるかが求まる。この情報を使って質問に答えれば ok。

(せっかく解法思いついたのにワーシャルフロイドの添字の順番ミスで WA もらってしまった…)