TopcoderのMarathonMatch141に参加しました。
問題名はTrafficController。交差点の信号を制御する問題でした。
結果は58人中36位でした。（事前テスト順位も36位。）
問題
車が突っ込んでくるので信号を制御してね。
車は前の車が進まなくても交差点に進入するし、
交差点の中で信号が赤になると交差点から出ようとしないよ。
やったこと
試行錯誤
全ての信号を縦方向に解放して、一定ターンごとに向きを切り替える。5から始めて、3が一番良さそう。車の挙動がヤバいこと、デッドロック（グリッドロックと言うらしい）が発生することは察していたので実際の挙動を確認する。
正の点を得る
ふと、縦横のいずれかを全開放してもう一方を封鎖すれば、理論値の半分強の得点が見込めることに気づく。流れで交差しない最大の道路数を求めたくなるが、探索すると最大を2^30未満には落とせない？なんとか過去の知見を活かせないものか。
縦横一方の使用道路を決めれば、もう一方はO(1)で求まる。縦横一方の使用道路を状態として、0.5秒焼くと相対62点*1が得られた。
真面目にやる
正の点を得る解法は投げ捨てて、状況に合わせて信号を変える。
直進可能になるよう信号を変える。
相対81点。
もうちょっと真面目にやる
交差点に進入する際に閉路チェックする。あまり上手く機能しなかったので、最終的には4辺からなる閉路のみチェックし、各辺の使用率が25%以上なら進入禁止とした。
またデッドロックが発生した場合は、影響する道の交差点へは進入禁止とした。*2
道路の優先順を付けたり車の発生率を考慮に入れたりしてみるが、結局のところ何も考えずにやるのが一番点が取れてうーん。
サボる
車列の長さなどを一切考慮していないのでまだまだやれそうな事はあるが、あまり気が乗らないのでお手軽な追い込みをする。
2つの解法ではっきり明暗が分かれがちなので、ケースによって解法を切り替える。L/N、L/R、(L^2)/Rなどを試し、手元1000ケースでは(L^2)/R>279が一番基準として良さそうだった。
相対84点。
感想
何も分からなかったけど、皆も何も分かっていなかったらしい。
やるならやりたい事はいくらかあったけど、今回は気が乗らず…。
