オンサイトに行ってきた。
287,752,665,589点で48位。
動いている様子の動画。
https://atcoder.jp/contests/toyota2023summer-final/submissions?f.User=kusano
問題
ランダムな順番で来るコンテナを、倉庫に入れて、なるべく順番通りに出す。障害物や他のコンテナを飛び越えることはできない。転倒数がほぼそのままスコアになる。シンプル。
ただし、1個のコンテナが来るごとにどこに置くかを決めないといけない。これ、すごく上手いと思う。短時間のコンテストで高速化勝負は面白くないから、インタラクティブなのは良い。ただ、インタラクティブの問題はデバッグが面倒なので、その点は短時間コンテストに向いていない。この問題は、インタラクティブなのに、ファイルのリダイレクトで入出力ができる。テスターをダウンロードして使い方を見て、「あれ？ インタラクティブ用の実行コマンドを指定する方式じゃないな。間違えたか？」と思った。インタラクティブなのにテスターはインタラクティブでなくて良い。
障害物
そんなに多くないとはいえ、障害物が邪魔。このせいで配置を決め打ちすることができない。
ネットワークの調子が悪くて、スタッフが「紙で問題を配ります？」「いや、あれは修正前だから訂正表を出さないと」みたいなことを話していた。結局紙でも問題は配られた。その紙の問題は障害物が無い版だった。後からの工夫だったのか。
全域木
とりあえず、幅優先探索で全域木を作ろう。
葉から順番に詰めて、根から順番に出せば良い。幅優先だから分岐が多くなる。その分岐によって並び替えができる。
詰めるのは適当に、出すときは今出せるコンテナのうち、最も小さいものを出すようにした。
178,278,440,895点。このスコアは300,000,000,000点が満点。
まだ提出している人が少なくて、たしか20位台だった。
搬出で全域木を無視する
この状態で5を出さないのはありえないだろ。搬出するときは全域木を無視して、今出せるもののうち最も小さいものを出すようにした。
238,846,299,605点。
搬入場所の指定
こんな感じに、入口から近い順に番号を振る。
全域木の葉から順に詰めていくのだけど、複数の葉のうち、なるべくコンテナの番号に近いところに置くようにした。
284,015,153,158点。
全域木を捨てる
搬出時は全域木を無視するようにしたわけだけど、搬入時も無視して良くない？ 入口から近い順に番号を振って、ここが62だったら、いきなりここに62を置いても後が困ることはないよね。空き場所が連結という条件を満たす限り、なるべくコンテナの番号に近い場所に置くようにした。
282,829,640,701点。スコアが下がった。
最後にこういう1本道が残るのが良くない。なるほど。全域木、悪くはないアイデアだったのか？
全域木の形
幅優先探索の4近傍の順番は何も考えていなかった。
順番を変えた。全域木がこういう形になったほうが良いよね。
286,800,165,931点。
ビームサーチ
この4とか7とかは早めに掘りに行くべきだと思うが、今のコードだと堀りに行かない。貪欲に今搬出できる一番小さいものを搬出するだけなので。そこでビームサーチ。
この時点で、290G点を取れればけっこう上位にいけそうだった。搬出は貪欲なのだから、それをビームサーチに変えれば、そのくらいはスコアが伸びるだろう。勝ったな。
287,752,665,589点。
微妙……。
ビームサーチだから途中の状態を評価しないといけないのだけど、そこをどうして良いのかが分からない。コンテナを搬出するときに、(すでに搬出した自分より番号の大きなコンテナの個数) + (まだ搬出していない自分より番号の小さなコンテナの個数) を加えて評価値とすると、ダメなコンテナを搬出するときの評価値への影響が大きくて、ダメなコンテナの搬出を先送りしてしまう。(まだ搬出していない自分より番号の小さなコンテナの個数) だけを評価値にして、このスコア。ペナルティがあるのが自分より番号の小さいコンテナだけだから、番号の小さいコンテナが自然に優先される。でもあまり良い評価値な気はしない。
あと、この記事を書くためにビジュアライザを見ていて気が付いたけど、今の搬入の仕方がわりと優秀というのもあるのかもしれない。「これは掘りにいかないとダメだろ」というシーンがあまりない。
トヨタの話
トヨタの人「車が好きな人 ﾉｼ」
トヨタの人「車を持っている人 ﾉｼ」
で手を上げる人が少なくてかわいそうだったw まあ、でも、コンテストは採用試験ではなく、企業アピールの場だから、「車大好きです！」「トヨタで働きたいです！」という人ばかりの場だったら、意味が無いだろう。
chokudaiさんが運転席と助手席の間にあるあれのことを「カーナビ」と呼んで渋い顔をされていた。IVI（In-Vehicle Infotainment）らしい。へー。今どきはカーナビ以外の機能が大量にあると。
ソースコードの行数が数千万行規模と増えてきてソフトウエア人材が欲しいとか、車本体だけではなくて工場とかでもアルゴリズムが重要だとか。数百人規模の大会を年に2回も開くくらいだから、たしかに人は欲しがっていそう。
ITエンジニアのキャリアプランとしてどうなんだろうか。IT企業は年齢と給料にあまり差が無いイメージがあり、若い頃はIT業界で、その後JTCに行くのが勝ち組パターンの可能性ある？
懇親会
コンテストはちょっと不完全燃焼感はあるが、まあ、呑むか……と思ったら、早い時間の懇親会は酒が出ない。なるほど。
コンテストが終わった後に昼食で、懇親会が夕方で、あまりお腹が空いておらず、「お代わり要りませんか」「肉がまだまだありますよ」とアナウンスがされていたw
「ビームサーチの評価関数？ 貪欲で末端まで進めたけど」という話を聞いた。たしかに。貪欲でそれなりなスコアが取れるのだから、それで良かったのか……。
