htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 014 参戦記

oox--- 1242->1295

A - Cookie Exchanges

結果:AC(2WA)
Submission #1263025 - AtCoder Grand Contest 014 | AtCoder
問題文の通りシミュレーションするだけ。奇数判定を最初に行うのを忘れてWAした。

B - Unplanned Queries

結果:AC
Submission #1263649 - AtCoder Grand Contest 014 | AtCoder
これって単に

  ( 1 )
 0/ 0| 0\
(2) (3) (4)

クエリ1,2↓

  ( 1 )
 1/ 0| 0\
(2) (3) (4)

クエリ2,4↓

  ( 1 )
 2/ 0| 1\
(2) (3) (4)

って問題だよね?配列を用意して入力を足していき最後に判定しただけで通ったけどtwitterの反応見てるとこれだけでよかったのか心配

C - Closed Rooms

結果:WA・TLE→終了後にAC
Submission #1269003 - AtCoder Grand Contest 014 | AtCoder
1回の魔法でK歩移動→K個壁を壊すことが可能であるため、最初のターンではスタート地点の閉領域外には出られない&次のターンで壁関係なくK歩移動できることが保証される(前のターンでそこのK個分壁を壊したことにすればいいので)。したがってやることは

  • スタート地点の閉領域を幅優先探索などして外までに一番近い距離を得る
  • 距離をKで割るなりなんなりして2ターン目以降にかかるターン数を得る

でこの方針は早いうちに気づいていたのだけれど、WAが出てたのは凡ミス(書き間違い)で、TLEが出てたのはpythonQueueが遅かったから。pythonqueue.Queue()は単なるデータ構造ではなくスレッド間通信に使われるものでパフォーマンスが出ないので、単なるデータ構造のキュー・スタックにはcollections.deque()の方を使うんだそう。実際dequeに変えただけで227msで通ったので、これからはdequeを使うようにする。

参考:python - Queue.Queue vs. collections.deque - Stack Overflow