ABCD4完、1WA。

しかし、Eがいけると思って先に考えて無駄に時間を使ってしまったので、順位がえぐいことに・・・。

各問題

A - Curtain

基本はA - B * 2ですが、これがマイナスになった場合は代わりに0を出力します。ifで分けるでもいいですが、max(0, A - B * 2)の方がちょっとだけ楽。

何も考えず、2重ループを回しておいしさの積を足し続けるだけです。

特に変な条件はないので、文字列を先頭からなめていって、違う文字が出てきたらカウントアップする、でOKです。

~~単純に3重ループを回すとTLEします。（しました）~~

3重ループでTLE、しません。

どうやら私は不要な処理をごちゃごちゃ書いていたせいで定数倍マシマシになっていてTLEしてしまったようです。もったいない・・・。

（追記ここまで）

なので、aとbの2重ループにしてcは二分探索（c++ならlower_bound）で許容できる上限を探して、個数を計算して求めます。もちろんあらかじめソートが必要です。

まず下準備として、C > Lのときはその道は使えないので除外した上でグラフを作ります。それに対してワーシャルフロイドで最短経路を計算します。

ここで私は、「最短経路を復元」したらいいと思ったのですが、これがWAでした。なぜなら、たとえばLが50のとき、30の道を4本使うと給油は3回ですが、41の道を3本使うと給油は2回で済むのです。つまり、最短経路を通ればいいという話ではなかったのです。

結局、私は正しい経路を探す方法がわからずタイムアップでした。

どうやら、経路を探すためのグラフを別に作ってもう一度ワーシャルフロイドをすればよかったらしいです。なるほどなぁ・・・。

みてません。

素直に前から解いていくのがベターって最近自分で言っていたのに、またやらかしてしまいました。

レートも冷えたし、今日はさすがにちょっと前向きな材料が見つからんですね。まあ、次回からよほどのことがない限り前から解いていくと心に誓ったということで。

f:id:mdstoy:20191019230944p:plain