読者です 読者をやめる 読者になる 読者になる

htkb-proconの日記

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

AtCoder Regular Contest 074 参戦記

ox-- 1295 -> 1305

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder

結果:AC
Submission #1297073 - AtCoder Regular Contest 074 | AtCoder

先にHとWのどちらかが3で割り切れないか確認して(割り切れたら答えは0確定)、

 Wが2で割り切れるなら両方とも W//2*上の高さ
 割り切れないなら W//2*上の高さ と (W//2+1)*上の高さ
+--+---+
|  |   |
|  |   | ← 上の高さ = H-(下の高さ)
|  |   |
+------+
|      | ← H//3*W か (H//3+1)*W か
+------+

下のボックスの高さは前述の確認によりHが3で必ず割り切れないので切り捨てか切り上げかで2通り考え、それぞれ上のボックスもできるだけ真ん中で割って面積を出しmax-minを計算する。さらにこれを90度回転させてHとWを交換したケースでも2通り出し、計4通りについてminを取った。コードがクソきちゃない。

D: 3N Numbers - AtCoder Regular Contest 074 | AtCoder

結果:WA → 終了後にAC
Submission #1300519 - AtCoder Regular Contest 074 | AtCoder

真ん中のエリアの扱いに困って困って悩んだ。でもまあ解説見ながら実装したら境界線をNから2Nの間でずらしていくだけといえばそうなんだけど……。

数列が 8 2 2 7 4 6 5 3 8 の場合、

[8, 2, 2] [7, 4, 6] [5, 3, 8]
             ↓↓
[8, 2, 2] | [7, 4, 6 / 5, 3, 8]  # 最善は sum([8, 2, 2]) - sum([4, 5, 3]) = 0
[8, 2, 2 / 7] | [4, 6 / 5, 3, 8] # 最善は sum([8, 2, 7]) - sum([4, 5, 3]) = 5
[8, 2, 2 / 7, 4] | [6 / 5, 3, 8] # 最善は sum([8, 7, 4]) - sum([6, 5, 3]) = 5
[8, 2, 2 / 7, 4, 6] | [5, 3, 8]  # 最善は sum([8, 7, 6]) - sum([5, 3, 8]) = 5 

と全通り試すのが基本的な考え方で、いちいちsum取ったりソートしたりするとTLEになるので、高速に処理するには先に左と右の合計を出してから、優先度付きキューで出し入れしてうまいことやるといいですよという話。pythonでは普通のリストで持ってheapqで出し入れする。

Typical Contest 001-B, ARC032-B, ARC037-B UnionFind

B: Union Find - AtCoder Typical Contest 001 | AtCoder

Submission #1294904 - AtCoder Typical Contest 001 | AtCoder
UnionFindの実装が面倒そうで避けてたので練習として。データ構造としては配列一本持つだけでどのように操作するか/比較するかだったので想像より簡単だった。一応クラス立ててやったけど必要なかった。__get_root()else節で親に直接つなぎ直す経路圧縮だけしている。経路圧縮だけで計算量はO(log n)くらいらしい。

B: 道路工事 - AtCoder Regular Contest 032 | AtCoder

Submission #1294948 - AtCoder Regular Contest 032 | AtCoder
UnionFindで根の数を数えるだけ……なんだけどset(v)の長さをそのまま出力してWAした。根に直接繋がれていないやつももちろんいるので、set(v)で重複を消したあとにそれぞれに対して根の確認を行わなければならなかった。

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

Submission #1295052 - AtCoder Regular Contest 037 | AtCoder
DFSで解く問題のようだけど。UnionFindで閉路を検出するにはあらかじめ頂点と同じ数のis_tree配列を作って全部1を入れておき、

  1. 同じ根の頂点同士を結合しようとした根
  2. 閉路のあるUnionと結合した根

is_treeにその都度0を入れていき、最後に根に対応するis_treeの合計を数えた。最初2に気付かずWAした。


参考にしたページ: pakapa104.hatenablog.com

ABC012-D 最短経路問題

D - バスと避けられない運命

最短経路問題の練習をいくつかこなしていたら、ダイクストラを真っ当に実装したはずなのにめっちゃTLEが出るこの問題に遭遇。おかしいと思って解説を読むと、

•注意点
– 遅い言語では通りません!
Perl, Ruby, Pythonなど
• 計算量が一定以上重い問題だと、LL系の言語では、通すことが 出来ません。
– 言語の選択もコンテストのうちです!

お?やんのか?ってことで色々いじって通した。

Submission #1289371 - AtCoder Beginner Contest 012 | AtCoder

  • やること

    • 各頂点ごとに最短経路を出してその最大を出力する
  • やったこと

    • 基本ダイクストラ
    • 計算した最短距離はメモっておき再利用する(AからBの最短距離を出したら、BからAへの最短距離に使い回す)
      • memo[n]がそれ
      • メモから読んだ頂点は訪問済みにし初期キューにもあらかじめ入れとく
    • 再帰的に隣接頂点を呼んで、隣接頂点の計算が終わったら子から親への枝を切る(これ怪しい……)
      • solve(child)後にedges[child].remove(i)で子→親方向の枝のみ切ってる
      • 逆方向(親→子)への枝を切るとWA出るので正当性は不明
    • 基本的な枝刈り
      • コストが低い頂点へは最初から行かない
      • メモしたコストを写した頂点には行かない(最短確定してるので)
      • 全訪問済みになったらwhileを抜ける

優先度付きキューを使ったダイクストラO((E+V)log V)でこれを各頂点に行うので、制約:V≦300,E≦44850から計算量はおよそ108くらい?基本的にpythonでは107の時点で無理ゲーな感じだけど、色々パズル感覚でこねくり回して通ってうれしい。

AtCoder Beginner Contest 061 参戦記

ooox unrated

A - Between Two Integers

結果:AC(2WA)
Submission #1278622 - AtCoder Beginner Contest 061 | AtCoder

早く提出しようと提出フォームに直接書いたらひどいことに……

B - Counting Roads

結果:AC
Submission #1279301 - AtCoder Beginner Contest 061 | AtCoder

グラフ問題っぽい語り口だけど出現した数字を数えるだけだった。

C - Big Array

結果:AC(1WA)
Submission #1280205 - AtCoder Beginner Contest 061 | AtCoder

[ [値, 個数], [値, 個数], [値, 個数], ... ]

みたいに入力を取って値でソートできれば楽ちん。

D - Score Attack

結果:WA → 終了後にAC
Submission #1286666 - AtCoder Beginner Contest 061 | AtCoder

よく考えたら最短経路探索のアルゴリズムを全然覚えてなかったので、無理矢理BFSしようとしたり嘘DP立てたりして結局解けなかった。終了後ベルマンフォード法でググッて実装。解説ではループ検出用の配列を用意したりなにやら難しそうなことしてたけど、ループをN回回してN回目のループ中に頂点Nが更新されたらinfということにした。類題をいくつか解いておきたいところ。

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