UVa::Pre-warmup Contest
チーム3人で出場してきました。3時間5問のセットで、4問解いて16位。5問解いたのは1人だけなので問題数的には上出来だけど、速さはまだまだ伸びるかなといったところ。
前のエントリでの不調からはそれなりに回復しました。
A Unique Snowflakes
長さ1,000,000以下の数列が与えられて、同じ数字を2つ以上含まない最長の連続した部分列の長さを求める問題。
はいはい尺取尺取って言いながらチームメイトに投げたら瞬殺してくれました。
B Ocean Currents
1000x1000のグリッド上で2点間を移動する最短コストを求める問題。8近傍にコスト1で移動できる他、マス毎に8近傍のうち1つが指定されていて、そこにはコスト0で動ける。
何も考えずにダイクストラしました。1,000,000ノードのダイクストラは普通に実装するとUVaでは通らないので、高速なpriority queueを自分で作って強引に通しました。
C Colliding Traffic
動く円が最大1000個与えられて、最初の衝突時刻を求める問題らしい。
チームメイトが瞬殺してくれたのでまともに読んでないです。うちのチームがFirst Submission & First Acceptだったらしい。
D Zerg Rush!!!
グリッド上で2チームが大量のロボットを戦わせるゲームをシミュレートする問題。
条件が色々と面倒臭い上に、適当に実装するとTLEを食らうので困る。
E Scrolling Sign
Shortest Common Supersequence問題。ただし文字列は与えられた順番に連結しなければいけないという制約が付いているので、普通に書けば通ってしまう。
チームメイトが「こんな簡単でいいんですか？」って言いながら解いてました。
