http://yukicoder.me/contests/160
以下、解説
No.494 yukicoder
http://yukicoder.me/submissions/159131
'?'が出てきたら、そのindexの文字列"yukicoder"の文字を吐く
No.495 (^^*) Easy
http://yukicoder.me/submissions/159172
入力に不備がない前提で処理をする。
5文字ずつ処理をしていくが、二文字目に'*'があれば、それは右向き、さもなければ左向きでカウント。
後は出力。
No.496 ワープクリスタル (給料日前編)
http://yukicoder.me/submissions/159314
クリスタルでのワープ移動と歩きの移動は独立なので、別々に考えることができる。
なので、クリスタルのみで移動するときのコストをdpで求める。
dp[i][y][x] := i番目までのクリスタルを使って座標(y,x)に移動するための最小コスト
これを計算して、最後に歩く分のコストも考慮して最短距離を求める。
No.497 入れ子の箱
http://yukicoder.me/submissions/159341
有向グラフに見立てて考える。
箱を頂点とし、箱iに箱jを入れることができるならjからiへ有向辺をつける。
箱の包含関係を取るために、xyzの長さはx<=y<=zにソートしておくと回転を考えなくて済む。
包含関係を見ると有向グラフにするのかな？という流れがある。
あとは、その有向グラフ上での最長経路が答えとなるが、これを求めるにはトポロジカルソートをすればよい。
トポロジカルソートをして、順番の早い順から子にコストを伝搬させていく。
全ての頂点のコストの最大値が答え。
No.498 ワープクリスタル (給料日編)
http://yukicoder.me/submissions/159425
クリスタルの総数が少ないので、クリスタルを使う回数について全探索する。
こういう全探索には再帰を使って実装することが多い。
各クリスタルを使う回数について、まず、そのクリスタルを使うことで頂点(0,0)が頂点(Gx, Gy)になるかをチェックする。
もし、なるならば、あとは、同じものを含む順列の計算をするように計算をして、総和を取ると答え。
同じものを含む計算の解説
http://examist.jp/mathematics/baainokazu/onajimono-jyunretu/
