7月21日のPKU
今日：14問
今日までの合計：35問
PKU 2654 Rock-Paper-Scissors Tournament
解法
普通にやるだけだと思うけど時間制限が厳しいみたい？
PKU 1299 Polar Explorer
問題
半径Xの円周のある位置から、Z度だけ離れたある地点へ行って帰ってきたい。燃料はYガロンあって、1ガロンで5マイル進むことができる。X,Y,Zが与えられるので燃料が足りるかどうか判定する問題。
解法
やるだけ。
Z > 180 のときは逆周りした方がよいので気をつける。また Z = 360 のときは Z = 0 と同じであるので気をつける。
PKU 1297 Supermarket
問題
通りにN個の店が並んでいて、それぞれの店ではある商品をある値段で売っている。与えられたリストにはM個の買うべき商品の番号が書かれている。通りを一回通り抜けつつ、リストに書かれている順に商品を買うとき、払わなければならない最小の金額を求める問題。1 <= M <= 100, 1 <= N <= 100000
解法
dp[n][m] を最初からn番目の店まできた時点でリストのm個目までの商品を買い終えているときに払った金額の最小値としてDP。普通にメモリをとると O(NM) のメモリが必要。今回はこれでも大丈夫だが、dp[n][m]を決めるときに必要なのが dp[n-1][m-1] と dp[n-1][m] だけであることを考えると O(M) のメモリでもいける。
PKU 3573 I18n
問題
文章中に略された単語がいくつかある。略された単語は
[最初のアルファベット] [数] [最後のアルファベット]
という形をしている。[数]はこの間に入るアルファベットの数を表す。略された単語が、それ以前に文章にでてきた単語ひとつとマッチするときに限ってそれを復元できる。
1000行以下で一行80字以下の文字列の中には32文字以下の単語がいくつかある。これを読み込んで、略された単語をできるだけ復元する問題。
解法
面倒なやるだけ。
PKU 3338 Rectangle Cutting
解法
それぞれのセルについて、自分の上・右・下・左のどこに切り込みが入っているかをビット単位のフラグ等で記録する。後は切り込みを壁のように見立ててFlood-Fillを繰り返す。
PKU 3385 Genealogy
解法
やるだけ。
PKU 2497 Strategies
解法
やるだけ。
PKU 3421 X-factor Chains
問題
正の整数Xについての以下のような整数列を考える。
1 = X0, X1, X2, ... , Xm = X
ただし、すべての i について Xi < Xi+1 であり Xi | Xi+1 である。(a | b とは b を a で割ったあまりが0であることをいう)
正の整数X (X <= 220)が与えられるので、上の数列のうちもっとも長いものの長さと、その長さの数列が何通り存在するかを求める問題。
解法
PKU 2032 Square Carpets
解法
BFS＋枝刈り
PKU 2807 Bingo!
問題
ビンゴをする。ただし通常のビンゴではなくて、与えられたX種類のパターンのうちY種類を満たす形になればビンゴしたということにする。
今、ある列の数字が何回呼ばれたかが分かっている。自分にとってもっとも都合のよい数が呼ばれたと仮定すると、最低であと何回数が呼ばれればビンゴすることができるかを求める問題。
解法
すべてのパターンで確かめる。
PKU 2004 Mix and Build
問題
単語がn個ある。ある単語に何か一文字追加して並び替えることで次の単語になるような列を考える。たとえば"ab", "bar", "crab", "cobra", "carbon"などといった単語の列。
与えられた単語の中で作れるこの列のうち最長のものを一つ求める問題。
解法
なんか最長増加部分列のDPみたいにしたら解けた。
PKU 3546 Sea Battle
問題
10x10のグリッド上に4x1の船が一隻、3x1の船が二隻、2x1の船が三隻、1x1の船が四隻ある。ただし、船どうしは交差してはならず、また船の先端がグリッドの端っこにあってもいけない。
10x10のグリッドで、船のある部分に '1' が書かれているものが与えられるので、これが正しい船の配置かどうか調べる問題。
解法
DFS
