ICPC2014 国内予選 - れどこだ目指すよ！　(；`・ω・）

AOJ出てないので確認できてないけど、アルゴリズムだけ。

A.税率変更

消費税がx%の時、2つの商品の税込価格の和(ただし、合計に対して税が計算されるのではなく、税込の和)が与えられるとき、消費税がy%になった場合、ありえる税込価格の和の中で最大のものを返す。

B.連鎖消滅パズル

H*5のセルに1〜9までの数字が埋まっている。
各行について、同じ数字が3つ以上並んでいたら、「その数字*連続した数」がスコアになる。
また、並んでいる場合、それらは消滅し、上から数字が落ちて、また同様にスコアが計算される。
最終的なスコアの合計値を返す。

シミュレーション。スコア計算＆連続を消す→落とす→・・・を繰り返す。

C.バンパイア

地平線から太陽が昇る。ビルがいくつか与えられ、それに隠れている限り直射日光を受けない。
最初、太陽が地平線にぎりぎり隠れている時刻を0とし、上へ毎秒1の等速直線運動をするとき、最大何秒間太陽の直射日光を受けずに済むかを返す。

ビルと地平線のところででこぼこのシルエットができる。
シルエットの(整数のところの)すべての頂点のうち、下に垂直に伸ばした直線が円と交わる頂点について、円よりも上にある場合は隠れていると判定できる。
二分探索で探すか、内部に含まないよう(頂点に接するところを探索)な最大の円の座標を探す。

D.暗号化システム

以下のルールで、文字列を変換する。
1.文字列の最初に表れたbをaにする。なければ何もしない
...
25.文字列の最初に表れたzをyにする。なければ何もしない
変換後の文字列が与えられるので、元の文字列であり得る文字列を返す。

変換前の文字列は変換後と同じ文字数。
返還前の文字列としてあり得るのは「変換後の文字」か「その次の文字」になる。
文字列の長さは高々20なので、2^20≒10^6で、全部生成して、ルールで変換して変換後の文字列(25*20=500)と一致するか試してもよい。(大体5*10^8ぐらいだけど、単純な処理しかない)

ただ、100ケースあるので、適当に枝狩りしてあげた方がよさそうか。
dfs的に文字列を生成しているならば途中までの文字列で、その文字があり得るかどうかはチェックできるので、それでそこ以降の部分木の生成を削れるかも。

E.橋の撤去

木構造が与えられ、以下の操作ができる。
・今いる頂点につながっている辺の先の頂点に移動
・今いる頂点につながっている辺を消す
移動するコストおよび辺を消すコストは、辺に与えられたコストで表現される。
任意の頂点で始まってよく、任意の頂点で終わっていいとき、すべての辺を取り除く最小のコスト合計を返す。

葉ノードにつながる辺は、葉ノードの手前のノードで削除できるので移動することはない。
葉ノードとそれにつながる辺をすべて取り除いた木構造の各辺は、1回(通るだけ)か2回(行って戻る)通る可能性がある。
1回通るだけでよい辺というのは、できるだけコストの大きな辺を通る＆できるだけ長い経路がよい。
これは木の直径で、任意の頂点から一番遠い頂点を見つけて、その頂点から一番遠い頂点を見つければそこが直径になる。(double-sweep algorithm)
なので、
(葉ノードにつながっている辺のコスト合計)+3*(葉ノードとそれにつながる辺を除いた木構造の辺のコスト合計)-(葉ノードとそれにつながる辺を除いた木構造の直径)
になる(？)。