初めに
寒いですね。僕は、二次予選前、雪が、少し残っている中、普通の長袖+ビーサンで、散歩したら、歩いてたおじさんにドン引きされました。(そりゃそーだ、その日最低マイナス4度だったからな)
そして、二次予選、脱落決定しました。 ボーダーがだいたい290点、僕は219点、僕は中部ブロックの望み(少ないから)もありましたが、ボーダーがだいたい決定した瞬間消え去りました。
まあ、また来年もあるし(あと4年分ある)そろそろatcoderはアルゴ部門 もうそろ入緑だし、切り替えてがんばります。
えーとはい、初めてのrated長期コンテストでしたが、結果は最悪でした。(2日ぐらいしか、手をつけてない)
最終絶対スコアが、69714968点でした(sqrt解法思いつけば、もうちょっといけた)
僕は、短期のほうが、得意なのかな
まあその2日の、結果を話します
1日目
手を付け始めたのは、19:30分頃とりあえず、サンプルコードを投げます。
その後c++で、出力形式の確認のため、横並べの解法を提出、サンプルより悪いです。
今回そこまで自分ができる領域では、計算量があまり気にしなくてもいい、事に気づき、pythonにします。
その後、各クエリで、山登り風のコードを書くものの、スコアは、悪化しました。
2日目
6:30頃目が覚めて、いい感じのコードを思いつき色々書きます。
ですが改善せず、親に起きてコード書いてたのと言われ気づいたら9時でした。
朝飯食って、思いついたのは、一段に、置くブロックの数を$\sqrt N$にする劣化版です。
具体的には、
ブロックはすべて使うため$p_i=i$
$r_i$は、ランダムにします
$d_i$も、ランダムにします
$b_i$は、$i-1$にします
で先程の山登りの初期解に設定して提出すると、スコアは良くなりました。
ですが僕は、いい初期解+山登りで、いい感じになっているかと、思いきや、そんなはずもなく初期解が強かったのでした。
その日の16時ごろ、先程の初期解を何回もランダムにやれば、いいのではと思いつき、やったら先述のスコアになりました
で同学年でも結構いい順位だしいいやと思って、そのまま最終日になりました(最終的に同学年の中でも結構低い方でしたw)
最終日
英会話に出かける前、そういえばAHC終了直前だなーと思ってあとで解説見ようと、思いそのまま、英会話行って、晩飯食ったあと、解説を見ました。
各段に置くブロックの数を$floor(\sqrt N)$にすると良いらしく、試してみると、僕が最後に提出したスコアより$9000000$点改善しました。
そっか正方形を面積から一辺の長さを求めるには、面積のsqrtを取ればいいのかと思い、少し自分が悔しくなりました。
最後に
やっぱり数学的考察は大事ですね。
ついに、僕の、暫定のヒューリスティックのレートが、アルゴリズムのレートより上がってしまいました。(文章力がゴミですいません)
少し悔しいです。
まあ、本職はアルゴなので頑張ります。