AtCoder水色になりました

こんにちは、にゃにゃんです。これは競技プログラミングに関する記事です。

昨日、AtCoder(日本の競技プログラミングの会社)で東京海上日動プログラミングコンテスト2020がありました。そこでついにAtCoder水色となりました！

ということで今回はいわゆる色変記事を書きたいと思います。

東京海上日動プログラミングコンテスト2020で何があったのか

東京海上日動プログラミングコンテストはARC級のコンテスト(普通よりちょっと難しいコンテスト)でした。このコンテストで6問中3問解け、一気にレートが上がりました。ちなみにパフォーマンス(そのコンテストでどれくらいのレートの成績を残したかを示す数字)は1994と、黄パフォ(めっちゃすごい)すれすれでした。とても嬉しいです。

この問題を少し振り返ってみたいと思います。

A問題

問題へのリンクはこちら
私の提出へのリンクはこちら

見た瞬間、「あ、入力されるSの最初3文字を出力すれば良いな」と思ってすぐ書き提出しました。提出時の言語選択で手間取り、開始33秒での提出でした。

#A問題
s = STR()
print(s[:3])

B問題

問題へのリンクはこちら
私の提出へのリンクはこちら

これは鬼と逃げている子供の座標のどちらが大きいかで場合分けしました。少し冗長な書き方ですが、ささっと書けたのでまあ良しです。提出は開始から3:03でした。

#B問題
a, v = MAP()
b, w = MAP()
t = INT()
if a <= b:
   c = a + v * t
   d = b + w * t
   if c >= d:
       print('YES')
   else:
       print('NO')
else:
   c = a - v * t
   d = b - w * t
   if c <= d:
       print('YES')
   else:
       print('NO')

C問題

問題へのリンクはこちら
私の提出へのリンクはこちら

さて、運命を決めたのはこの問題です。解法がパッとは浮かばず、とりあえずO(NK)でTLEしそうな解法を書いてみました。そこでこれを入力して値がどのように変化するのかの過程を見ました。

10 1000
0 0 0 0 0 0 0 0 0 0

早い段階で全部10になってそれ以降は変化しないことに気づきました。そこで、とりあえず変化しなくなったらbreakするようにしてペナ食らってもいいやという気持ちで提出しました。そしたらなんと通ったのです！提出は開始から20:37でした。本当にびっくりしました。

#C問題
n, k = MAP()
a = LIST()
for j in range(k):
   prea = [i for i in a]
   num = [0 for _ in range(n + 2)]
   for i in range(n):
       l = max(1, i + 1 - a[i])
       r = min(n + 1, i + 1 + a[i] + 1)
       num[l] += 1
       num[r] -= 1
   for i in range(1, n + 2):
       num[i] += num[i - 1]
   #print(num)
   a = [i for i in num[1:n + 1]]
   if a == prea:
       break
a = [str(i) for i in a]
print(' '.join(a))

どんな勉強をしたのか

さて、これが本題と言っても過言ではありませんね。私は緑の間に大きく2つのことをしました。

・とりあえず精進をする
・蟻本を読む

それぞれ解説しましょう。

とりあえず精進をする

春休み、大学受験も終わり学校も(新型コロナもあって全く)なく、暇でした。そこで精進をしたのです。

精進グラフ(細い方)でギュインと上がっているところがありますね。これが春休みです。毎日最低でも1問解いていたのでstreakが長くなりました。

解いた問題のdiffは基本的に茶から緑で、サボった日は灰diffでstreakをつないだりしていました。その結果、ある程度問題が埋まってきました。

この効果がやっと現れてきたのでしょうか…わかりません。

蟻本を読む

ところで第3回アルゴリズム実技検定(PAST)が無料になっていましたね。ありがたい限りです。私はこれを受けることに決め、蟻本を少し読み進めました。現在は身についたかはともかく、ダイクストラ法のところまで一応読んであります。

緑の間に身についたことは主に、

・貪欲法
・全探索(DFS&BFS)
・dpの難しいやつ(語彙力)
・いもす法
・グラフの簡単なやつ(語彙力)

です。

余談ですがなぜかdpが好きで茶色時代には簡単なdpを書けていた気がします。

このほとんど(いもす法以外)は蟻本を読んでAtCoder版蟻本で演習して身についたものです。この2つに大感謝です。

今後

私は果たしてどこまで行けるのでしょうか。AtCoder社長のchokudaiさん曰く「アルゴリズム能力はカンストしている」そうですが(こちらの記事)、個人的にはまだまだ知らないことがいっぱいある印象です。これは頑張れば伸びしろになるということで、今は青まで行けたらいいな…と思っています。

今後も競技プログラミング、そしてもちろんソフト・ハード問わず開発を頑張っていきます！