ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041）

　413位という苦しい成績。

コンテストへのリンク

コンテスト後のツイート

ALGO ARTIS プログラミングコンテスト2025 冬（AtCoder Heuristic Contest 041） 400位にも入れず厳しい。
・葉が全体にいきわたるようrootとそこから出ている芽を決め、高さ10の葉の集合が減らないように高さ9,8,7,..の頂点を固定。あとは貪欲に、できるだけ高い高さで頂点を埋めていく、という方針。

— titia (@titia_til) January 19, 2025

　高さ10の頂点をできる限り増やしたい、というのは分かるのだけれど、どうすれば実現できるか分からず上手くいかなかった。

　山登りなども考えた（し、どうやらそれをやった方が良いスコアが出たらしい）が、子たちも一斉に変えなくてはならないず、高さが10より大きいものが出た場合どうすれば良いのか？　というあたりで躊躇してしまった。

これで76,108,082点出た。
ちょっと書いてある事をストレートに解釈できなかったんだけど、以下のやり方にした。
①根(高さ=0)を決めるため、美しさAの小さい順に頂点を選択し、全頂点が根から距離10以内に入る組合せを全通り求める。
②(続 https://t.co/PtKxMCVioz pic.twitter.com/VBlif4LMPb

— ツカモ (@tsukammo) January 19, 2025

　このツカモさんのツイートを参考に、コンテスト後に話題になった貪欲を実装してみた。

　根にできるだけ小さい値を割り当てたい、という気持ちは良いのだが、そのために、「Aを小さい順に見て、全点にいきわたるよう必要なだけ取る」、というのではなく、「Aを大きい順に見て、その点がなくても全点にいきわたるようなら除く」としているのが技巧的に感じた。

　ただ、その方法にさえ気付けば後は自然ともいえるか……。

　コンテスト中どうすべきだったかは悩ましい。

　自分がコンテスト中考えていた方とこの貪欲解法は結構似ているので、そこへ辿り着けたら良かったのだが、上手くいかなかった。

　DFSを試すべきだったとは思うけど、普段再帰でのDFSを書いていないため、解説放送にあるようなDFSにはちょっと慣れていないんだよね……。解説放送のDFSを再現するのに時間がかかってしまった。それだとあまり良いスコアが出なかったので、DFSの良さに気付くのもそんなに容易でなかった気がする。

　シンプルな解法を考えて、山登り/焼きなましなり、ビームサーチなりを試す、という方針の方が良かったのかなぁ。