c問題は解けたが、D問題は解けなかった。
https://atcoder.jp/contests/abc095/tasks
C問題
方針
これはよく考えると以下の購入の仕方が3通りしかないことに気づく
(1) ABピザのみ買う
(2) ABピザを買わずにAピザ,Bピザを買う
(3)ABピザとAピザ、Bピザを買う方法
これらの中で最小の値が答えになる。なお(3)の時は、(x,yのうち小さい方の数*2)枚分のABピザを買い、そのあとx,yのうち多い方から残った枚数分の金額を足せば会計額が出せる。
D問題
方針
まず問題条件から全探索は一個の変数にしかできないことがわかる。高橋くんが歩く範囲をイメージすると以下のように左端と右端が決まる。
よって左端と右端を全探索すれば答えが求まりそうだが、そうすると計算量が制限時間を超えてしまう。なので、もう少し考えてみると、もし、左側を固定した時、右端の最適位置は一意に決まっていることがわかる。なぜなら、この最適位置は、寿司のvとxによってのみ決まるからである。よって、反時計回りに寿司のvについて累積和をとっておき、反時計回りに各寿司iについて、(寿司iの地点での累積和-xi)を更新していくことで、左端を固定した時の右端の位置を定数で求めることができる。よって、この左端と右端について左から右に行った時と右から行った時の両方を求めよりスコアが大きい方について採用し答えを更新していく。これを時計回りにもすることで最終的な答えが求まる。