Codeforces Round#8 - simezi

参加。
1:00からだと思ってたら0:45からだった！！

気づいたときには既に7〜8分経過orz
ICPC形式だからペナルティ痛いよ。。。

2AC,1WAの126位でレート微減。演習の成果が出てない気がして鬱い。

焦りながら問題を読む。

各駅には色のついた旗がある。
ある駅から出発して、寝て起きていくつかの区間旗を覚えて、また寝て起きていくつかの区間旗を覚えてまた寝て目的地に着いた。

各駅の旗の色が与えられるとき、覚えている区間の旗から下り電車に乗ったか、上り電車に乗ったか、両方の可能性があるか、どちらもありえないかを答えよ。

見た旗の文字列二つが順に駅の旗の文字列に現れるか検索する。下りは駅の旗の文字列を逆にしてチェック。

送信→AC.

Aを既に80人以上解いてたorzこれはまずい。。。

グリッド状の平面を移動するロボットがある。
平面には障害物がありロボットは障害物のマスには入ることができない。ロボットの移動経路が上・下・左・右の文字列として与えられたとき、この移動経路が最短経路でありえないならBUG、ありえるならOKを出力せよ。

最短距離？ってことは経路で同じマス２度踏んでなければいいんじゃない？

書く→Submit→WA.

え、あ、ぐるぐるうずまき書いたりするとダメか。
通れるところ全部幅優先で調べよう。

書く→Submit→AC.

現在90位くらい。むーでもCむずそうだぞ。。。

座標平面上にn（≦24）個のアイテムが落ちている。同時に２個までアイテムを持てるとき、座標平面上のある地点にあるバッグにアイテムを回収したい。
最短時間で移動するような移動の時間と移動の仕方を出力せよ。
なお座標平面の移動時間は、始点と終点の距離の二乗に等しい。

な、なにこれ全然わからない……
総当りでやると数千億通り……？(24!/2!/12!)
考える。わからない。

一時間以上考えても全然わからないのでもう探索で書くことに。
こんなん絶対TLEだろ...orz

訪問済みノードをビットで持って、二つずつまたは一つずつ回収してくのをダイクストラで探索。
二つばらばらに回収したほうが早いようなアイテムについては最初に計算して持たないようにしておく。

15分くらいで書いて送信。→queue混んでる。

数分後に返事がきた。WA.ゲームセット。

今回のセットは大分難しかった。。。のでやっぱり僕のレベル帯では時間勝負の要素が大きい。のに何遅刻とかしてるんだろう。

Cは結局探索らしい？後で復習する。