AHC001
前回までのあらすじ
最近AtCoderを始めた人は、存在を知らないであろう「ふみこん」で正の得点が取れず、HTTF2019予選でも成長が見られなかったので、とりあえず虚無記事を作成したのが、私とマラソンの今まででした。
今回ついに、AtCoderでratedマラソンの第1回目であるAHC001が開催され、正の得点が取れたよって記事です。
今回の結果
提出1回目 823090
提出2回目 4302096900
提出3回目 4342447260
提出4回目 44054627088
最終順位723位でした。
------
(2021/03/16 追記)
03/15の夜間にシステムテストが行われました。
最終得点 880,827,768,563点、最終順位 688位でした。
------
問題は以下のURLでどうぞ。
https://atcoder.jp/contests/ahc001/tasks/ahc001_a
やったこと
今回は、rated第1回ということもあり、「できることをできるだけやろう」という方針でした。(できないことはできないので。)
1回目の提出は、「問題の理解とWAにならない提出の確認」です。いつもはここまでで終わっていたので、これを1回で通すのも個人的には大事な作業でした。
問題の入力生成方法を読むと、「異なる座標をランダムに 個サンプルすることで生成される」とあるので、全ての広告を1*1のサイズで指定位置に貼れることが分かります。
これを提出すると823090点でした。今のところ、これより上を正の得点と呼んでいます。
2回目の提出は、「x軸方向のみに限定して、得点を最大化」しました。本当は、この段階で、y軸方向のみで最大化したものと比較して大きい方を提出すべきなのですが、x軸の方を実装した段階で、満足して提出してしまいました。
また、この実装時に同一y座標に2つ以上の広告を置きたい場合の実装ができなかったのですが、「10000の範囲に最大200個までランダム配置」なので、放置しても良さそうだと判断して、同一y軸に1つのもののみを操作しました。
これを提出して、4302096900点、y軸方向も同様の操作をして、点数が多い方を提出した3回目が4342447260点でした。
ちなみに、この段階で参加していたPHPerは3人で、1人は823090点、もう1人が450億点ほどだったのと、方針として、「同一軸上に2点以上ある場合の処理をする」と「残りの軸についても動かす」の2つが思いついていたので、430億点くらいまでいければ良いかなと思っていましたが、twitterでは過少申告をしました。(そもそもつぶやかないのが正解なのですが、「順位表から分からない情報」にあたる「思いついている方針数と期待される得点」をごまかすためにしました。)(順位表から分からない情報の判断基準は難しくて、私のように、開始直後の順位表を眺めていた人間からは、「430億点くらいまで単純な操作で行ける」という予測は順位表から得た情報ですが、単に順位表を眺めた場合に得られる情報かといわれると微妙なので、次回以降は気をつけようと思います。(今回は、初めての正の得点でちょっとテンションが高かったのがあります。))(TLの他の方なのですが、提出の度に自分の得点画像だけを貼っている方がいて、たぶんそれが正しいコンテスト中のtwitter所作だと思います。)
4回目の提出は、「同一軸上に2点以上ある場合の操作」と「残りの1軸についても同様に広げていく操作」をしました。
「同一軸上に2点以上ある場合の操作」は、前述のとおり、「複数点ある場所がそれほど多くなさそうなこと」と、実装中に入力生成方法を読み直して気づいた「異なる値をランダムに個サンプルし、それをソートした列を とする。 、 とする。」ことから、「100000000/200=500000なので、10000より小さい場合ってほぼなくね？」と思い、「得点を最大化できそうなもの(rが最小のもの)以外を端に寄せて、残りの範囲で1つを最大化する」という操作に簡略化しました。
残りの1軸についての操作も、本当は、「尺取りの要領でmin(s,r)/max(s,r)を最大化」したかったのですが、そんな実装力は持ち合わせていないので、「rを超えるまで可能な限り広げる操作」に簡略化しました。
これを提出して、44054627088点で、提出時点で約700位でした。無事、目標達成です。めでたい。
ちなみに、いつの間にかPHPerが4人に増えていて、1位が480億点、2位が465億点で、私は3位でした。(もう1人の方は、最初の823090点のままだったので、時間が取れなくて記念提出をされたのだと思います。)(理由は不明ですが、最近PHPでのAtCoder参加者が増えていて、なんとなくうれしいです。最初の通過点アカウントとしてご利用ください。)
感想とかあとがきとか
一番テンションが上がったのは、実は自分の目標達成ではなく、1回目の提出で全体1位にhakomoさんが入ってきた時でした。かっこよかったですね。
今回、初めて正の得点が取れたわけですが、マラソン的には440億点から上が正の点数だと認識できるようになる必要があるのだと思います。(提出を見ると分かるのですが、4回目の提出が実行時間40msなので、マラソン的な「時間ギリギリまで微小な更新を繰り返して、より良いものを提出する」にたどり着けていないので。)
実際、もう少し実装力があれば、「4回目の提出の状態を初期値として、広告が接している境界の位置を変更して、より良くなるなら採用」とかをやってみたかったですが、「そんな能力があれば、5年も茶色erをしてないんだよなぁ」というお気持ちです。
これよりも有用な記事を他の真面目にマラソンをしたerが書いてくれているはずなので、AtCoderClans等から探して読みましょう。
個人的には、次回はマラソン的な正の得点を目指したいなと思えた良いコンテストでした。
------
(2021/03/16 追記)
上にも書きましたが、システムテスト後に順位が35上がって、最終順位 688位、最終得点 880,827,768,563点でした。
おそらく、マラソン的な操作をしていた方々が、一部テストでTLEしたか、局所解ではまったかで、40msの実行時間が生きた結果になりました。(50ケース440.5億点→1000ケース8808億点なので、ほぼそのままの比率ですね。)(例の823,090点は、システス後22,914,631点らしいので、こちらはちょっとお得になってますね)
ちなみに、PHPerの3人の順位が以下のとおり等差数列で、ちょっとうれしかったです。
1位(全体204位) 963,070,689,510点 dicecuさん
2位(全体446位) 929,928,517,699点 yoichiroさん
3位(全体688位) 880,827,768,563点 inaba3(私)
最上位桁の数字が9だとマラソンに参戦できてる感じがして、やっぱりかっこいいですね。
ということで、運営さん含め、皆さんお疲れ様でした。
------
