htkb-proconの日記

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

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()の直後に出力しているのが原因としか思えないので、とりあえず当面はそういうものだと覚えておく。