htkb-proconの日記

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

AtCoder Regular Contest 075 参戦記

o— 1281 -> 1293

C: Bugged - AtCoder Regular Contest 075 | AtCoder

結果:AC
Submission #1323396 - AtCoder Regular Contest 075 | AtCoder

数列をソートして合計を取り10の倍数だったら数列の中の10の倍数ではない最小の数字を捨てて合計をチェック……を繰り返した。←これ今思えば繰り返す必要なかった(10の倍数から非10の倍数引けば非10の倍数になることは自明なので)

D: Widespread - AtCoder Regular Contest 075 | AtCoder

結果:わかんなかった

ソートした数列を取り出したり泥臭いやり方をしようとしてた時点で負けだった。てかにぶたんなんて全く思いつかなかったよ……!

Tターンで全滅させられる、とは、各モンスターに対してT*B+(A-B)*nn(切り上げ)の合計を求め、それがT以下であるということ。(A-B)*nとは何度そのモンスターを中心にして攻撃したかということなので。

A = 3, B = 1
h = [3, 3, 9] 

T = 3 とすると、
h1: 3 = 3*1+(3-1)*n
    3 = 3 + 2n
    n = 0 # 3ターン全て中心に選ばなくても倒せる
h2: 同上
h3: 9 = 3*1+(3-1)*n
    9 = 3 + 2n
    n = 3 # 3ターン中心に選べば倒せる

T >= nの合計 より、3ターン以内で倒せた

以上の考え方で、Tの値を二分探索する。
ACコード:Submission #1329512 - AtCoder Regular Contest 075 | AtCoder
pythonだと1787msもかかってるんだけどやり方悪いのかな……?

Codeforces Round #416 (Div. 2) B 平方分割

B. Vladik and Complicated Book

適当訳:数列と3つの数字からなるクエリl, r, xが与えられるので、元の数列とそれのl番目からr番目までを昇順にソートした数列を比べて、x番目の数字が変わってないか調べてNE!

数列 5 4 3 2 1
クエリ 1 3 1 → 変換済み数列 3 4 5 2 1 → 1番目は元の数列と違うので No
クエリ 2 4 3 → 変換済み数列 5 2 3 4 1 → 3番目は元の数列と同じなので Yes

f:id:htkb:20170530205829j:plain

_人人人人人人人人人人人人人人人人人人_
> あ!これ蟻本でやったところだ!! <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄

でも覚えてなかった!!平方分割してそれぞれのバケットごとにソートするのは覚えてたんだけど、そこからわからなくてWAとTLEを食らった。跨いでる各バケットについて二分探索するんだった。

元の数列 1 7 4  3 9 2  6 5 8
√n個のバケットに分割してソート
バケット[1 7 4][3 9 2][6 5 8]
↓
ソート  [1 4 7][2 3 9][5 6 8]

クエリ 3 8 5 の場合:元の数列の5番目の数は 9
3〜8番目の中でまるまる含まれているバケット(この例では2番めのバケット)について
二分探索などで9が各バケット内の何番目こに入るか高速に調べる。
           ↓ここ!
    [ 2  3  9 ]

バケットの一部しか含まれない左右の部分は、元の数列から引っ張ってきて
くっつけてソートし、同じように何番目に入るか調べる。
左の切れ端 右の切れ端
    [ 4 / 6 5 ]
         ↓
    [ 4  5  6 ]
             ↑9が入るのはここ!

つまりソート部において9の左に5個数字がある=ソート部の6番目に入る
=ソート開始地点より左の2つも合わせて、変換済み数列の8番目に9がくる
元の数列では5番目だったので答えは No

pythonならばbisectモジュールのbisect_left()を使うことで簡単にある数字がリストのどこに入るのか二分探索で調べてくれる。
提出コード(汚い):http://codeforces.com/contest/811/submission/27383788

蟻本に載ってるPOJの問題はこちら 2104 – K-th Number

AtCoder Grand Contest 015 参戦記

oo—- 1305 -> 1281

A: A+...+B Problem - AtCoder Grand Contest 015 | AtCoder

結果:AC(3WA)
Submission #1312681 - AtCoder Grand Contest 015 | AtCoder

0通り・1通りなどのケースを場合分けしたら、数列に含まれる最小の数字と最大の数字は確定しているので、

4,_,_,8
  ↑
このケースでは中に入る数の総和は
4*2 〜 8*2 の間なので答えは 8*2 - 4*2 + 1

なかなか思い浮かばなくて後回しにしBからやったし3WAも出して駄目だった。

B: Evilator - AtCoder Grand Contest 015 | AtCoder

結果:AC(1WA)
Submission #1311287 - AtCoder Grand Contest 015 | AtCoder

最下階は上行き、最上階は下行きで固定なので、目的地と同じ方向なら乗る回数は1回、そうでなければ最上階/最下階経由で2回。これを全ての階に対して足すだけ。しょうもないミスで1WA。

C: Nuske vs Phantom Thnook - AtCoder Grand Contest 015 | AtCoder

コンテスト中は解法が全く思いつかなかったけど、解説を見たら意外とシンプルな問題だったのでやってみた。頂点の数を数えるのは簡単だけど、連結成分を数えるのが面倒くさかったというかうまくいかなかった。縦の連結成分と横の連結成分をそれぞれ別に累積和を取って、考え方は以下のような感じ(横の連結成分)。

f:id:htkb:20170530013423j:plain

横の場合は始点のX座標とその左との連結を切るために被るように引かなければならない。縦も同様にやる。

でこれを素直に実装すると

Submission #1316989 - AtCoder Grand Contest 015 | AtCoder

で全然TLEで、ACコードを見ながらnumpy使って累積和取ったりしたもののどうしてもTLEが取れない。最終的に

AC:Submission #1317391 - AtCoder Grand Contest 015 | AtCoder
TLE:Submission #1317397 - AtCoder Grand Contest 015 | AtCoder

クエリを受け取るループ内で答えをprint()しているほうはTLE、一度リストにappendしてループを回し直したほうは無駄なループが増えているのにACになった。理由はよくわからないしググっても情報が得られなかったけど、input()の直後に出力しているのが原因としか思えないので、とりあえず当面はそういうものだと覚えておく。

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ということにした。類題をいくつか解いておきたいところ。