KUPC2011

oooo-x---- 400pt 42位
とあるセミナーがニコ生でも放送するという情報を直前に聞いたので、ニコ生見ながらまたーり参加。

A​ ​-​ ​K​U​P​C​

解けた。

各文字をカウントしてKUPCのうち一番小さい数字を返すだけ。提出→AC。

B​ ​-​ ​蝉​

解けた。

やるだけ、、、あんまり大きくないしdfsで大丈夫かな？提出→TLEorz
ちゃんとやる。(i,j)地点の最小値は上か左のどちらかから来るパターンしかないから、最小のセミの数をメモしながらO(W*H)で書いて提出→AC。

C​ ​-​ ​し​り​と​り​

解けた。

対話式の問題。これ面白い。
最初「a」と発言すれば、AIは2文字しか発言できないから「a?」しか発言できない。?はa〜zまでだけど、そしたら「?a」って文字を返せばどんどん言える数が減る。提出→WA。あれ？
いろいろできてない。。ちゃんと書き直す。提出→WA。おーい。
まだ抜けてる。。適当な発言を返したときの処理がない。。提出→AC。

D​ ​-​ ​列​の​構​成​

解けた。

一通りDからJまで問題を見てみて、EとIあきらめてからDに戻る。
各数字を使うか使わないか。普通に調べると明らかにTLE。こういう問題よく出るのに一向に解けない。。。
よく使われている数字から取っていって、条件の数を超えたら適当な数字を減らして、足りなかったら追加とかするのかな。かなりめんどい。。。
解って結構多いのかな？？8個のうち1〜3個って結構多い気がするぞぞぞ。もしかして、使われている数字のうち、使える最大数(＝3*N/8)だけ適当に選んで条件を満たすか調べれば結構見つかるんじゃ、、、乱数使うの、、、？random_shuffleとか使って適当に書いて提出→WAだけど、結構あたってる！？
テストケースあんまり多くないし、TLE2個ぐらいしかないし、乱数初期値変えれば行ける？初期値を時間にして提出→WAだけど、意外と増えた？？
見直す。出力すべき数字が1〜Nなのに、0〜N-1を表示してた。。提出→AC。なんだってー！？

E - F​o​x​ ​N​u​m​b​e​r​

提出していない。

どっかで見たことある問題。区間篩！区間篩ちゃんと理解できてない、、、
とりあえず愚直にやるとTLEはわかる。メモしながらdfsでできないかな、、、ぐぬぬ。あきらめ。

F​ ​-​ ​ボ​〜​ル​

解けなかった。

D解いてからあと1時間ぐらいだったので、頑張ってFをやることに。
要は、角度0〜PIまでの範囲について、原点を通る各円との接線の角度の範囲に変換して、できるかぎり領域をカバーすればいいと。最後にカバーした領域の合計/PIを出力すればいける！
各円から角度の範囲に変換。適当に接戦だからsin,atan2使って角度は求められる。書く。できた。
N個の円からできるだけ広くカバーできるK個を選ぶ。具体的にK個っていうのが怪しい。N,Kが1500もあるってことはgreedyなのかな。現在カバーされていない部分に注目して、一番カバー領域が広いやつを順番にK個選べばいけないかな。書く。提出→WA。
円の中心が0以下かPI以上のときの処理とか円同士が重なっているときの処理が怪しい。書く。提出→WA。
変換が間違っているのか、K個の選択が間違っているのか。たぶん後者だけど、タイムアップ。
[追記]反例。1-5,0-2.5,3-6の領域の場合、1-5が長さ4なので、1番に選ばれて、残りのどちらを選んでもgreedyならば合計5だけど、0-2.5と3-6のほうを選べば合計5.5なので、こちらのほうが長い。

G - X​O​R​ ​回​路​

未読。

H - あ​ば​れ​う​な​ぎ​

未読。

I - 山​

提出していない。

解けてた人が数人いたので、考えてみる。行swapか列swapを実際にするようなやりかただとTLEっぽい。なんかの数値をカウントしてその数値から判断できそう。その数値よりも下か右にある数値のなかで自分自身より小さい数値とか？？行か列全体が同時に代わってしまうことを考慮できてない、、、ぐぬぬ。あきらめ。

J - M​o​d​ ​3​ ​K​n​i​g​h​t​s​ ​O​u​t​

未読。

反省

問題Dは乱数使うのも想定解法ってtwitterで流れて驚いた。おもしろいｗ！
コンテストはどんどん参加してきたい。

いろいろ考えたり組み合わせたりっていう思考をするのに、基となる基盤がちゃんとできてないなと思った。やっぱり問題やらないとダメだ、、、やっぱり教科書もそうだけど演習問題実際に解かないと身につかない。