GCJ Japan 2011
出題者が強実装大好きな人達っぽくて、最近のGCJらしくない大会でしたね。
A
N本の棒を端点を一か所にまとめて、角度が等しくなるように並べる。もう一方の端点を結んでできる凸包の面積の最大値を答えよ、という問題。
要は高々2回だけ同じ値を使って良いので、乗算した和を最大化せよという問題に等しい。なので、一番でかい子はその次にでかい2個と、次の子は既に一番でかい子と組んでいて、その次の子と組んじゃまずいので、自分より2個小さい子と組んで...というのを延々とやるだけ。これで最適値になることは、取り敢えずスワップしてみると、大きい子にかける値が小さくなって、それよりも小さい子にかける値が同じだけ大きくなることから、明らかに損と分かるので、いえそう。
B
f(x)=x^xをK回適用した結果を法Mで求めよ、という問題。
うまいこと周期性を使って云々...。実装力というか、そもそもの遷移ができなかった...。
D
開くとL字型のロッカーを二次元平面に開けるように配置する。置けない場所と部屋の入り口が指定されるので、全部のロッカーを開ける(到達可能でないとダメ)ように置ける最大数を答えよ、という問題。
どう見てもタダのDPで解けそう。幅が5なので、下の行からの情報の持ち上がりが2^5と、到達可能性のための情報が、2^3(高々3つに通路が分割されていて、それらがどのようにつながっているかのパターンは5通り(どれか二個がつながってるか全部つながってるか、全部つながってないか))なので、2*5の配置をその都度やりながら置いた数をDPで云々。
E
変な数学的な繰り返し図形が与えられるので、それの中を当たらないように移動するときの、二点間マンハッタン距離を求めよ、という問題。
多分規則的に座標がたためるのだと思うけれど、やる気なし。
