AtCoder Beginner Contest 103に参加してみた
今回はノーミスで全完したのだが、C問題にあまりにも時間がかかってしまい、実感としてはかなりまずい印象だった。
前回のABCから三週間ぶりで感覚がおかしかった気がする。
第１問
「最小→真ん中→最大」あるいは「最大→真ん中→最小」のどちらかの順番ですすむのが最善で、結果は最大-最小の差になる。
xs = [int(x) for x in input().split()] print(max(xs) - min(xs))
いきなりWAを飛ばしてびっくりした。何回見直しても大丈夫そうだったので放置しておいたら、AtCoder側の不具合があったらしくリジャッジでACになっていた。
第２問
ある文字列が別の文字列を回転させたものかどうか、という質問。文字列の長さが最長100なので愚直に書いて問題ない。
s = input() t = input() print('Yes' if any(s == t[i:] + t[:i] for i in range(len(t))) else 'No')
ただ、ツイッターでprint('Yes' if s in t+t else 'No')を見たときには、自分で思いつかなかったのが悔しかった。
第３問
何故かこの問題に１時間ほどかかった。
- 規則性？LCM?とかうだうだと考えるのに四十五分ほど
- (a1 * a2 * ... an) - 1 だとどの数でも割り切れないし最大化されるな、しかし巨大数になりそう((10 ^ 5) ^ 3000)だからどうするか・・・ と悩むのに十分
- 「あ」と解法に気づいた瞬間から実装するのに一分かからなかったと思う
n = input() xs = [int(x) for x in input().split()] print(sum(x-1 for x in xs))
(a1 * a2 * ... an) - 1で「すべての数字が割り切るのに１足りない数」を作れるので、その数の結果はsum(a - 1)になる。気づいてしまえばなんということはないのだけど、何故かなかなか気付かなかった。
第４問
西から東へ一直線に並ぶ島をつなぐ橋を最小でいくつ消せば、「島aと島bは繋がっていない」という要望をすべて満たせるか、という問題。
残り三十分ほどだし無理かな、と思って眺めていたら蟻本初級編「Saruman's Army」の類題だった。
まず要望を西側の島がもっとも小さい（西側によっている）順に要望をソートする。あとは西端から貪欲に要望を満たしていく：
n, m = map(int, input().split()) lrs = [[int(x) for x in input().split()] for _ in range(m)] lrs.sort() ans = 0 m = -1 for l, r in lrs: if r < m: m = r if l >= m: ans += 1 m = r print(ans)
最初はプライオリティキューを使うことも考えたのだけど、まったく必要なかった。
感想・結果
ノーミス全完ながらも消費時間が93:46で順位は526、パフォーマンスは1271でちょこっとだけしかレートが上がらなかった。
それも仕方ないな、というくらいにCの解法が盲点に入ってしまっていた。実装自体は全問非常に簡単だったし。
どう考えればよかったのか・・・ 解法やアルゴリズムに入るまえに「そもそも想定し得る最大はいくつだ？」「その最大になりえる条件は？」と考えていればsum(a - 1)が早い段階で見えたかもしれない。
考察のやり方のまずさと、精神力の弱さ（AがWAだったことによる動揺も大きかった）が露呈したコンテストだった。
ただ、D問題も読んでみて「歯が立たないな」という印象はなく、最終的に今持っている知識で解答に確信を持って全完できたのは良かった。ここ２ヶ月弱の競プロ精進のひとつの成果だと思う。
考察の仕方や精神力は、もっと場数を踏むことで培っていこう。
