inani_waonの日記

コンテスト覚書

AHC012 - AtCoder 10th Anniversary 参加記録

AtCoder Heuristic Contest 012に参加しました。

atcoder.jp

問題はAtCoder 10th Anniversary。

円形のケーキをカットして、苺を上手く配分する問題です。

結果は得点率91.5%で、1659人(うち提出710人)中90位でした。

 

問題

円形のケーキ上に、苺がたくさんあるよ。

100回まで直線でカットして、苺が1~10個の領域をそれぞれ指定した数だけ作ってね。

要求数に対して作れた割合(苺の個数毎に、上限100%)がそのまま得点になるよ。

 

考察

んん、三角関数系か?4時間ではやりたくないなぁ。

 

まずは生成ルールを読んで、必要なブロックの数を概算する。

中心を通るように角度を変えて100回切るとおよそ200ブロック。全然足りない。

縦に50回、横に50回切るとおよそ2500ブロック。ケーキは円なので、角にあたる部分が無い分それよりは少ないが、めっちゃ余る。まぁ多すぎる分には切る回数を減らせばいいよね。

切り方はこれで行こう。斜めカットは…やるならかなり本腰入れないとなぁ。時間ありそうならで。

 

苺の数は必要最低限しか無い。満点が取れない場合、苺をたくさん(9~10個)要求する人を切り捨てた方が得点は改善しやすい。

 

ブロックの状態は苺の個数が同じなら同一なので、垂直/水平に切るなら苺2つの間の何処で切ってもいい。つまり代表位置を1つ決めれば、カット位置は垂直/水平それぞれでN-1箇所程度になる。(X位置、Y位置の重複があれば減る。)

 

水平に10分割した後、垂直に切る位置をビームサーチ、とかどうだろう。10本の帯に見立てて、いずれかの帯が苺11個以上になる切り方は不許可、とすればまあまあ枝刈り出来ない?

評価は要求苺数ごとに、[不足ブロック数^2]の総和かな。ただそうすると終盤に苺10個みたいな切り方をするのが難しい…。外周に小さくカットされる部分が出来るので、どうしても1,2辺りが余分に出来そう。中央から両端に向かって同時探索して、大きいものを優先的に作るよう探索するとか?序盤は苺10個を重視したいくせに、全体としては苺10個は軽視したい。この実スコアと相反する探索をするのが気持ち悪い。…焼くべき?とりあえずシミュレータ書きながら焼きなマシーン*1の様子を見るか。

 

時系列やったこと

~1:00

考察&入力の受け取り。

~1:07

入出力のテストがてら、20x40に固定幅で分割してみる。

70M点で420位相当。

~2:10

とりあえず焼きなまし完成。

初期解は20x40で、近傍は垂直分割(40個ある側)の追加/削除/移動。

89.9Mで108位相当。

~2:14

移動が何処にでも飛んでいく仕様だったので、近場に制限してみる。

89.0M。なんで?

あと、差分計算できるところを毎回計算して遅いので、試しに時間を10倍にしてみる。得点ほぼ変わらず。これなら高速化より、初期解と近傍を見直すべきか。

~3:15

なんとなく細長い方が得点が高そう?あと多点にしたいので、水平分割を10と11で半分ずつ回してみる。(10x40)

90.4Mで100位相当。

~3:57

初期解を10x60にする。あとパラメータ調整。

うーん、初期解から劇的に変わってる気がせず、kick的なものが無いと苦しそうな気がする。

91.5Mで90位。

 

他の人の解法を見て

斜めに線を引いている人もいるけど、格子状で大体戦えそうだった。高速化、初期解、近傍辺りを詰めてればもっと高得点取れてたかな。多点の話は全然出てない。

あとは縦横を両方動かしてる人もいたけど、速度が多少犠牲になるのでどっちが良いのかくらい。多分遅くても両方動かせた方がいいかな。

 

感想

高速化などの手を回しきれない部分もあったけど、出せる力が素直に出しきれたので短期コンの割には良い成績でした。

苺を切らずに垂直(水平)に限りなく近く切る方法があったらしく、そういう非本質な裏技で点稼ぎできるのはちょっと…と思うも、そこまで点に響くものではなかったかな。

問題のところに貼った画像のように、ユーザ歴10年の古参ユーザにだけケーキを届けることが出来ていない。すまない…。

*1:焼きなましに定評があるtakumi152さん。