AtCoder Beginner Contest 124をPythonで解く

Python 競プロ

最近この時間はちゃんと予定を空けておくようにしています。

atcoder.jp

今日は40分でA、B、Cを解くことができたので初全完いけるんじゃね！？と思ったまま残り1時間を過ごし3完でした。残念。
自信を持ちながら過信しない、というのは難しいですね。

第一印象

A：簡単そうなのでキレイに書きたい(叶わず)(急いだ)
B：やっぱ先週のABCのA、B問題むずかったよな...
C：法則を見つけるんや！単純化や！核心を見つけるんや！(慣れてきている)(アルゴリズムとか問われたらどうする気なのか)
D：似たようなやつ見たことある(後述)(出来なかった)

という感じです。前回も書いたのですが苦痛になるのだけは避けたいので、全完より先に目指すは「安定してサクッと3完」ですかね。

今回からA、B問題については「本番中にわーっと書いて通した回答」に加え「終わってから落ち着いて考えたキレイバージョン」も思いつけば(AC通るか確認の後に)載せていきたいと思います。



A - Buttons

2つの整数から大きい方を選び、その数から1引いた数とさっき選ばなかった方の整数のうち大きい方を再度選ぶ問題。
絶対回り道してる...と思いながらカリカリと書き起こしました。
A、Bに関してはより良い書き方よりも印象が指先から流れ出してるくらい同時的に書いてしまった方がいい気がしています。

提出ver.

a, b = map(int, input().split())

a, b = min(a, b), max(a, b)
sum1 = b
sum2 = max(a, b-1)
print(sum1 + sum2)

2数が同じならどちらも一度ずつ選ぶ、という例外を除いては「最初にデカい方を2回選ぶ」ということでしたね。

後から考えたver.

a, b = map(int, input().split())

print(max(a, b) * 2 - 1 if a != b else a * 2)

B - Great Ocean View

いくつかの整数を最初から順に見ていき「今までの数字以上」の大きさの数字に何回出くわすかという問題。

「以上」を条件式に書き忘れた(>=でなく>と書いていた)ことにテストコード試してるときに気付いて直したのですが、その変更を忘れて直す前のコードが書かれた提出ページでそのまま送ってしまいました。なんと無駄なWA。こういうのは無くしていきましょう(自戒)。

n = int(input())
hotels = list(map(int, input().split()))

view = 0
cnt = 0
for i in range(n):
  if hotels[i] >= view:
    cnt += 1
    view = hotels[i]
    
print(cnt)

変数名を分かりやすくしようというリーダブルコードを読んだ人の香りが感じられませんか？
出来ているかは別問題です。まずは気持ちが大事。



C - Coloring Colorfully

与えられた0と1からなる文字列を「0と1が交互になってる文字列」に直す最小手数を考える問題。
紙に書いてうんうん唸っているうちに「初期状態によらずゴール2パターンじゃね？近い方がどっちか考えればよくね？」と脳内のギャルが閃いてくれました。ありがとう脳内のギャル。
つまり「ハミング距離が近い方はどちらか」ということでした。脳内のギャルが院試のときに勉強した情報理論を覚えていてくれたおかげで閃くことが出来ました。

少し見づらいかもしれませんが、

  • 理想の文字列2種類を作る
  • 与えられた文字列と理想文字列の異なる部分を数え上げる
  • 近い方のハミング距離(異なっていた場所の数)を出力する

という流れです。文字列の長さがマックス10^5だったので数え上げてもいいかとチャレンジしました。

s = input()
l = len(s)

if len(s) % 2 == 0:
  ideal1 = '01' * int(l / 2)
  ideal2 = '10' * int(l / 2)
else:
  ideal1 = '01' * (l // 2) + '0'
  ideal2 = '10' * (l // 2) + '1'

cnt1, cnt2 = 0, 0

for si, i1i, i2i in zip(s, ideal1, ideal2):
  if si != i1i:
    cnt1 += 1
  if si != i2i:
    cnt2 += 1
    
print(min(cnt1, cnt2))

D - Handstand

0と1からなる文字列にK回「まとめて反転」命令が出せるとき、作れる連続した1の最大長を考える問題。
解説読んでも？？？って感じなので出来たら追記します。


まとめ

  • テストした時にコードを直した直してないに関わらずテスト後のコードをコピペして提出する
  • C解く速さ
  • D解ける可能性を上げていく

明日は技術書典6ですね。10時くらいに行きたいと思います。
2万円以内に収まるといいなぁ...。既に7冊くらい積ん読あるのに...。

techbookfest.org