イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

126. AtCoder参加記録（AtCoder Beginner Contest 260）

プログラミング AtCoder

30回参加でレート 1323 です。

 

 

今回はパフォーマンス 1582 です。

ABCDを通して、EGExは未解答です。Fは通せず。

 

各問題の思考過程など。

A

4分15秒。

何とでも実装できますが、Dictionary を使ってやりました。問題の制約に対して無意味に実装が複雑化したので、あんまり良くなかったかもです。

 

B

6分25秒。

制約が小さいので書かれている通りにやればOKです。HashSet と OrderByDescending や Where を使ってゴニョゴニョやりました。業務コードっぽい。

 

C

6分34秒。

シミュレートしてみると、結局、変換できるだけ変換するのが最適だと分かります。なので、愚直シミュレートすればよいです。

レベルごとに赤い宝石の数リスト、青い宝石の数リストを作っておきます。レベル N からスタートして、降順に宝石を変換していきます。同じレベル・同じ色の宝石はまとめて変換します。最後にレベル1の青い宝石の数を出せばOK。

 

D

9分44秒。

表向きで見えているカードの数字とその山にあるカードリストを管理する Dictionary、表向きで見えているカードの数字を管理する MultiSet を用意して、後は適当に実装すればOKです。計算量は O(N \log N)。

 

E

解けず。全然方針が立たなかったので、飛ばしてFを考えていました。

 

F

解けず。この解法では間に合わないだろうと思いつつ投げましたが、案の定TLE3回でした。

  1. 問題文をよく読むと、「 V_2 のある2頂点で V_1 のある同一2頂点と接続している頂点は存在するか？」ということだと理解
  2. V_2 側が小さいので、ここを二重ループで回してよい
  3. あとは、 V_2 から取り出した2頂点それぞれと接続している頂点を見て、共通するものが2つ以上あればOK…だけど、この計算をどうやっても対数や定数時間に落とせない
  4. BitSet が少し頭をよぎったが、これやったところで O(ST^2) が64倍高速化されるだけなので無理だな…と諦め
  5. 間に合わないとわかりつつ適当にごまかした実装で投げたが、やっぱりTLE

 

G,Ex

見てないです。

 

 

Dまでは（自分としては）やるだけの問題でしたが、実装が重かったからか思った以上にパフォーマンスが出ました。ちょっと業務っぽい感じでしたね。

今日は重い実装でも落ち着いてコーディングできたので良かったです。E, F 解けなかったのであんまり競プロ感無かったですが…。

昨日と合わせて -5 なので、現状維持という感じです。やっぱり青は遠いな…。