AtCoder Regular Contest 106 レビュー

結果

Rated コンテスト参加 10 回目にして初の緑パフォとなりました。
だんだんと実力が伸びている実感がありとても楽しいです。

反省点としては、よく読めば避けれたはずの WA や TLE で時間をロスしているところですね。
あとは、単純に実装までが遅いので瞬発力を高めたいと感じています。

これまでの成績

ちょっと娘の子守とかの都合で全力出せなかったコンテストで灰パフォがあるものの、競プロ参戦時点から実力としておおむね茶パフォという感じでしょうか。

こうして眺めてみると、300-400 点台の問題がそこそこ解ければ色変も近いかなというイメージですね。

A 問題

普通に全探索すればいいだけの易問ですね。Python だと多倍長すら意識しなくていいので、実装の瞬発力が課題でした。

反省点としては、0 乗を含めた解で最初提出して見事に WA 食らったという点です。かなりザコいです。

コード

本当ならもっとrangeの範囲を厳密にとるべきなんでしょうが、オーバーしても Python だと怖くないので無精しました。

n=int(input())
a,b=-1,-1
for i in range(1,100):
  for j in range(1,100):
    if n==3**i+5**j:
      a,b=i,j
      break
if a==-1:
  print(-1)
else:
  print(a,b)

B 問題

かなり時間をかけてしまいました。
操作の前後で総和は変化しないので、そこはすぐに気付けたものの、制約で辺の数に 0 を含むケースがあるのとかをちゃんと読んでいなくて右往左往していました。

その後、テストケースの絵を描いたら、必要条件が見えてきたという感じです。 回答は、厳密な証明は省いて突っ込みましたが、$N=3$で成り立つなら$N=4$でも成り立つのはパッと見でいけそうだと思ったので、問題の点数とか制約的におそらくこれが必要十分条件になっているだろうと考え、そのままいってみたという感じです。

連結成分の管理方法は Union-Find しか知らなかったのでとりあえず Union-Find したのはいいものの、Union-Find で得た各グループの要素のインデックスを取得し、総和を求める際の実装が弱くて$O(N^2)$にしてしまっていたので 2 回も TLE しました。

反省点としては、以下の 3 点でしょうね。

• ちゃんと問題文（制約）を読む
• テストケースを読むだけでなく図をちゃんと描く
• ループの計算量をちゃんとチェックしながら実装する

コード

Union-Find はマージテク入れたほうがよかったかもしれません。
本当に実装速度を求めるならライブラリ化するべきなんでしょうが、ソラでの実装力を重視しているので、直書きしています。

f=lambda:map(int,input().split())
n,m=f()
a=[*f()]
b=[*f()]
# Union-Find
p=[-1]*n
def root(x):
  if p[x]<0:return x
  p[x]=root(p[x]);return p[x]
def union(x,y):
  rx,ry=root(x),root(y)
  if rx==ry: return
  p[ry]=rx
for _ in range(m):
  c,d=f()
  union(c-1,d-1)
sum_a,sum_b=[0]*n,[0]*n
for i in range(n):
  ri=root(i)
  sum_a[ri]+=a[i]
  sum_b[ri]+=b[i]
if sum_a==sum_b:
    print('Yes')
else:
    print('No')

C 問題以降

C 問題突入時点で残り 30 分とかで、パッと解法も見えず、娘が寝かしつけで寝ずにぐずっていたので離脱しました。

まとめ

今年の 5 月ぐらいにはかなり遠く見えていた paiza の S ランクとかも取れたりして、だんだんと実力の伸びを感じます。
Python もすっかり自分の中でのメイン言語という立ち位置になってきました。非常に楽しいです。

今後は AtCoder Problems などで精進して実装の瞬発力を高めていこうと思います。