AtCoder Beginner Contest 097に参戦してみた

プログラミングの勉強の一貫として、昨日初めてAtCoderのコンテストに参加してみました。

問題はこちら → AtCoder Beginner Contest 097

スポンサーリンク
広告1

参加してみて

ABCまで解くことができましたが、D問題は手も出せませんでした。

特にC問題の罠にひっかかってしまって大幅な時間ロスをしてしまったことが痛かったです。

その他、分岐のミスや条件設定など、もう少しマシなアルゴリズムを考えることができたんじゃないかなと心の中で反省しています。

反省点と提出コード

公式の解説
すべてPython3で実装。

A問題

AとCが直接会話できる または Bを経由して通話する=つまりAとBが直接会話可能 かつ BとCが直接会話可能 であればOK。

◆提出コード(クリックで開閉)
# -*- coding: utf-8 -*-
 
a, b, c, d = map(int, input().split())
 
if abs(a-b) <= d and abs(b-c) <= d or abs(a-c) <= d:
    print('Yes')
else:
    print('No')

B問題

Xまでの数値における最大のべき乗の指数を求める。

理論上平方根以上の数値を探索する必要がないというところに気づけばOKでした。

◆提出コード(クリックで開閉)
# -*- coding: utf-8 -*-
import math
 
X = int(input())
sq = int(math.sqrt(1000))
 
ans = 1
for i in range(2, sq+1):
    for j in range(2, sq+1):
        if i ** j <= X and ans < i ** j:
            ans = i ** j
            continue
print(ans)

改めて振り返ったらけっこうひどいですね…平方根を求めるのは入力した値まででいいです。テストしていたコードをそのまま出してしまいました。

int(math.sqrt())はX+1を指定し、for文も2と平方根の指定だけでOKです。

C問題

適当な英小文字の文字列をsubstringで区切り、辞書順でソートしてK番目以内になるものを表示する。

理屈自体はすぐに理解できましたが、理論上K文字以上の単語が指定されることはないため、K文字以上のsubstringを探索する必要なんてありませんでした。

処理時間が大幅に伸びてしまうため、必要最低限の探索で済むように書く習慣をつけていきたいです。途中点もそれを見越したような配分でした。

◆提出コード(クリックで開閉)
# -*- coding: utf-8 -*-
import math
 
s = input()
K = int(input())
dic = []
 
for i in range(len(s)):
    for j in range(i+1, i+6):
        if s[i:j] not in dic:
            dic.append(s[i:j])
dic.sort()
print(dic[K-1])

何故か不要なものをインポートしていました。

最速を目指す場合二重ループの探索もi+1+K文字目まででOKです。

感想

こういったオンラインのコンテストに本格参戦したのは初めてで、思うように成果を出せなくて悔しかったのですが、自分の実力を客観的に測っていくには最適な手段だと思いました。

後で解けなかったD問題にも挑戦し、問題の意図の理解やコードの実装をより素早く行っていけるよう努力します。

当分の目標として、Beginnerコンテストにおいては全問正解できるようになることを目指していこうと思います。

競技プログラミングの楽しさがわかってきたので、今後もこういったコンテストを見つけたら積極的に参加していきます。

スポンサーリンク
広告1