2/7
PKU 2465
dp[i][j] := i番目のガソリンスタンドに居て、残り燃料jの時の最小の支払額
としてDP。
PKU 2466
まず求めたい数列を a、入力の数列を s とする。ただし両方ソート済み。
そうするとまず
s[0] = a[0]+a[1]
s[1] = a[0]+a[2]
は明らか。ここで、あるiについてs[i] = a[x] + a[y]となるx, yが分かっている場合に u[i] = true、分かってなければ u[i] = false とする配列 u を用意する。するとまず u[0] = u[1] = true。
s[0], s[1]について二つの式が成り立ったが、これには未知数が3つ(a[0], a[1], a[2])含まれていて解くことができない。s[i] = a[1]+a[2] なる i が判明すれば解くことが出来る。
そこで、2 <= i < N*(N-1)/2 なる全ての i について、 s[i] = a[1]+a[2] と仮定して推論を進めてみる。最後までうまく値が求まったらそれが答となる。
s[i] = a[1]+a[2] と仮定したから、まず a[0], a[1], a[2] の値は簡単に求まる。また、仮定より u[i] = true とする。
そうすると、 u[x] = false となる最小のxについて、 s[x] = a[0]+a[3] であることが簡単に分かる。なので a[3] = s[x]-a[0] として求めることができる。それで u[x] = true と変更して、次に a[3] + a[t] (0 < t < 3) の値を s 内から探して、全部見つかればOK。もし見つからない値があればs[i] = a[1]+a[2] とした仮定が間違っていたことになる。
s[k] = a[3]+a[t] となる値を発見すれば u[k] = true と更新する。そうすれば次は u[x] = false となる最小のxについて、 s[x] = a[0]+a[4] であることが分かる。後は同じプロセスを繰り返せばよい。
PKU 2467
All roads are perfectly straight, with one lane in each direction.
問題文が読めれば解ける。
PKU 2469
やるだけ。
PKU 2363
全探索
PKU 2361
色々チェックする方法でもいいけど、どうせ状態数39 < 20000しかないのでDFSで盤面全列挙。
PKU 3640
はっしゅ
PKU 3643
局所探索的な何か
PKU 2328
やるだけ。
PKU 2304
やるだけ。
PKU 2303
入力の人形を doll として、それを大きさ順にソート。
memo[a][b][k] := Borisの一番外側の人形がdoll[a]で、Natashaの一番外側の人形がdoll[b]で、Borisの人形がk個のとき、Validな分配ができるかどうか
でメモ化再帰。
PKU 2857
PKU 2858
単語をsetで持ってたら時間間に合わないのでTrieでも作ろうかと思ったけどstringstreamじゃなくてstringを使うようにしたら間に合いました。
PKU 3282
右から左へ行く回数と左から右へ行く回数を別々に数えて、大きい方の2倍が答。ただし左から右へ行く回数の方が多かった場合はその答から1を引く。
PKU 3286
ある数n以下の数の中で、10kの位が0なものは何個あるかを計算することを考える。
まず、nの10kの位が0でない時は 10k*floor(n/10k+1) 個である。
次にnの10kの位が0の時は 10k*floor(n/10k+1-1)+n%10k 個である。
あとは引き算。
