各ボールの色の偶奇性に着目すると、各色円筒に入れられるボールの数が奇数であれば、その色のボールは最後に最低1個は円筒の中に残る。答えの自明な下界として、#{色c|円筒に入れられる色がcのボールは奇数個}が考えられる。以下この答えを達成可能であることを示す。状態B:円筒に1個のボールが入っている状態C:円筒に2個のボールが入っている状態D:円筒に3個のボールが入っており、この3個は異なる色であり、更に次に入るボールと同じ色が端に存在するか、もうボールは入らない実は、操作中、円筒がこの4種類の状態のみを取るように出来る。状態Aのとき次のボールを入れれば状態B状態Bのとき次のボールが円筒の中のボールと打ち消し合えば状態Aへ遷移する。ないならば状態Cへ遷移する。状態Cのとき次のボールが既に円筒に入っている2つのボールのいずれかと同じ色なら、それと打ち消し合うように入れれば状態Bに遷移するそうでないならば、更にもう1つ先のボールを見つつ適切な方から入れれば、状態Dに出来る。状態Dのとき状態Dの定義から、適切な方からボールを入れれば状態Cに出来る以上より、操作中常に円筒を状態A,B,C,Dのいずれかに保つことが出来る。以下、このように操作を行った際の最終状態を考える。0のとき偶奇性に着目すると最終状態はAかCだが、Cになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はA。#{色c|円筒に入れられる色がcのボールは奇数個}=1のとき偶奇性に着目すると最終状態はBかDだが、Dになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はB。#{色c|円筒に入れられる色がcのボールは奇数個}=2のとき偶奇性とボールの個数に着目すると、最終状態はCであると分かる。#{色c|円筒に入れられる色がcのボールは奇数個}=3のとき偶奇性とボールの個数に着目すると、最終状態はDであると分かる。これらは全て前述の下界と一致する。2019絶対に許さないからな。2019お恥ずかしい限りです...その後3社目のHuaweiへ行き、解散する新宿で集合してICPC勢とボドゲカフェに行ってたっぷり遊んで解散イルカショー感動しました。はじめまして!今日の練習試合お疲れ様でした。参加記HTTF2020予選に参加しました。結果は22位(4963718点)でした。方向転換はコスト1のedgeを張って、拡張Dijkstraをする。「このマスでこっちを向いているロボットがいるとき、いくつの方向案内を新たに置けばゴールに着けるか」を求める。コストが正であるロボットのうち、最小のコストを持つロボットについて、ゴールに着けるように方向案内を置く(そのようなロボットが複数存在する場合は、インデックスで最小のロボットを採用する)再び拡張Dijkstraを行う。これを、(ゴールまで到達する道が存在するような)全てのロボットがゴール可能になるまで繰り返す。ロボットのインデックスシャッフル(4963153点)2はロボットのインデックスに応じて結果が変わる。一杯まで、毎回ロボットのインデックスをシャッフルして2を繰り返す。不要な方向案内削除(4963718点)最後に不要な方向案内を削除する。atcoder.jpその他試したけど無意味だったことコストが同率な複数ロボットが存在するとき、ゴールまでの距離が最小(最大)のロボットを採用する。スコア下がったロボットのインデックス順で焼きなまし一回のシミュレーションで100ms掛かるのに焼きなまし、意味ある?無いね試すべきだったことDijkstraの代わりに0-1BFSで高速化コスト1種類しか使ってないので当然0-1BFSでokこれ気付かなかったの酷すぎる...「本職がマラソンじゃなくてアルゴだから」とか言い訳も出来ないレベルの失態ですね...非通過のマスを通過するときボーナス上位陣のコードをいくつか実行して確かめたのですが、自分のコードと上位陣のコードを比較したところ、Bの差はほぼ無く、Cの差で負けている状態でした。これは熱かったBについて話し合うが、全員口を揃えて「これ最大流問題を部分問題として含むし、フローは明らかに無理だし、何かおかしくないか?」と言うということでclarを投げる仰る通りでございます。「全てのedgeのcapが等しいならdinicは速い」ということを知らなかったせいで、このようなクソclarを投げてしまいました。JAGの方々、作問チームの方々、本当に有難うございました。会場に着き、運営からのチーム説明や会場使用上の注意等を聞いていると、チームメイトのシナモロールからDMが飛んできましたは?ご丁寧にチームアカウントが作成されていました。「アイコンに丁度良い画像無い?」と言われました。FA狙いで最初の1問だけ実装して」こ「ok」となりました。「そっかぁ」でHが終わる相変わらずK不可能にしか見えない病を患っているのでKはやろうとしないLは開かないNは詰めれば出来ると思っていたが、順位表を見て流石にやめるということで、残りがIJMになる相談した結果、残り時間的にもあと1問通せば御の字だろうし、お互いに通せそうな問題を頑張って考えようという話になる。NHK本当に神バランスの良セットだったと思います。東京工業大学の皆様、FUTURE様、有難うございました。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。