AtCoder Beginner Contest 249 - プログラミングの備忘録

こんにちは。
今回は、前回の最後に参加した「AtCoder Beginner Contest 249」の復習をしてみます。

taq.hatenadiary.jp

参加してみたいという方は以下からどうぞ。

atcoder.jp

復習
- 振り返る
- 見てみる
また参加する
まとめ

復習

振り返る

まずは、自分のコードを振り返ります。

プログラムを書いたのは問題A~Dなので、それぞれ見てみます。
（問題文は省略します。）

問題A

「A - Jogging」

算数の問題によくあるような、2人がそれぞれある規則で走ったときにどちらがより遠くまで行けたかを計算するというものでした。

a, b, c, d, e, f, x = map(int, input().split())
 
lt = la = 0
xt = xa = x
while xt > 0:
    if xt >= a:
        lt += a*b
        xt -= a+c
    else:
        lt += xt*b
        xt = 0
while xa > 0:
    if xa >= d:
        la += d*e
        xa -= d+f
    else:
        la += xa*e
        xa = 0
 
if lt > la:
    print("Takahashi")
elif lt < la:
    print("Aoki")
else:
    print("Draw")

高橋君を例にして説明します。
時間xtが0になるまで（while xt > 0）、xtが走る時間a以上なら走った距離ltにa*bだけ足してその分と休憩の時間の和a+cをxtから引く、xtが走る時間aより短いならその残りの時間分走った場合の距離xt*bを走った距離ltに足してxtを0にする、という処理を繰り返して高橋君が走った距離を計算しています。
青木君の場合も同様です。

最後に2人の走った距離ltとlaを比較し、より長い方を出力、同じならDrawを出力することで答えとしています。

問題B

「B - Perfect String」

与えられた文字列が"素晴らしい文字列"の条件に合うか調べるというものでした。

s = input()
 
f = True
l = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
if s.islower() == False and s.isupper() == False:
    for i in l:
        if s.count(i) > 1:
            print("No")
            f = False
            break
    if f == True:
        print("Yes")
else:
    print("No")

"素晴らしい文字列"の条件は、

英大文字が文字列の中に現れる
英小文字が文字列の中に現れる
全ての文字が相異なる

まずはif s.islower() == False and s.isupper() == Falseによって全ての文字が小文字あるいは大文字となっているかいないかでふるい分け、なっているものについてはそのままNoを出力して終了です。

続いて、全ての英小文字･大文字を入れた配列lについて、if s.count(i) > 1によって文字列sの中に同じ文字が2回以上出ているものについてはNoと出力して終了です。

その文字列が"素晴らしい"かどうかを入れておくfという変数を用意しておきます。
基本的にはfはTrue（"素晴らしい文字列"である）なのですが、先程の条件if s.count(i) > 1に入った場合はFalse（"素晴らしい文字列"ではない）に変更され、条件if f == True以下は実行されません。
if s.count(i) > 1に入らなければfはTrueのままなので、条件if f == True以下が実行されてYesが出力されます。

問題C

「C - Just K」

$N$個の文字列が与えられ、そこから好きなだけ選んだ文字列の中でちょうど$K$個の文字列に登場する文字の種類数の最大値を求めるというものでした。

n, k = map(int, input().split())
s = []
for i in range(n):
    s += input()
    
c = 0
l = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in l:
    if s.count(i) > 1:
        c += 1
 
print(c)

問題文を見ても何をすれば良いかわからなかったので、サンプルを眺めて、文字列全ての中で複数回出てくる文字の種類数が答えになりそうだ、と思ってダメ元で書いてみました。
案の定ダメでしたが。

問題D

「D - Index Trio」

ある数列$A$の要素の中で$\displaystyle \frac{A_i}{A_j} = A_k$となる組$(i,j,k)$の総数を求めるというものでした。

n = int(input())
a = [int(i) for i in input().split()]
 
c = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i != j and j != k and i != k:
                if a[i]/a[j] == a[k]:
                    c += 1
                    
print(c)

これもダメ元でしたが、i、j、kの組全てに対してa[i]/a[j] == a[k]で計算をするという方法にしてみました。
だいたい実行時間制限超過になってました。

見てみる

さて、ここまでで本番で書いたプログラムを振り返りました。
ここからは答えを見ながらにはなりますが、改めてコードを書いてみます。

以下、他の方のコードを参考にしつつ自分がわかりやすいように変えて載せています。

問題A

while文の中の処理を数式として表すこともできるようです。

a, b, c, d, e, f, x = map(int, input().split())

def calc(a, b, c, x):
    q = x // (a+c)
    r = x % (a+c)
    return (q*a + min(a,r)) * b

lt = calc(a, b, c, x)
la = calc(d, e, f, x)
    
if lt > la:
    print("Takahashi")
elif lt < la:
    print("Aoki")
else:
    print("Draw")

Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

//は割り算の結果を小数点以下切り捨てで出すもので、q = x // (a+c)によって走る+休憩のサイクルが何回できるかがわかります。
%は割り算の結果の余りを出すものなので、r = x % (a+c)で走る+休憩のサイクルを目一杯した後に何秒残るかがわかります。

関数calc()は走った距離(q*a + min(a,r)) * bを返します。
走った距離にサイクルの繰り返し数qで走れる距離q*aを足し、残りの時間rはa+cで割った余りなのでaよりも大きくなることがあり、min()を使ってaとrを比べて小さい方の時間分min(a,r)*bだけさらに足しています。

問題B

わざわざ全ての英子文字･大文字で繰り返さなくても、与えられた文字列の中にあるもので繰り返せば良かったことに気づきました。

s = input()

if s.islower() == False and s.isupper() == False:
    for i in range(len(s)):
        if s.count(s[i]) > 1:
            print("No")
            break
        if i == len(s)-1:
            print("Yes")
else:
    print("No")

Submission #31332708 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

問題C

「bit全探索」という方法を使うと良いらしいです。
bit全探索は、2進数を使って全ての組み合わせを試す、というような方法です。

もっと詳しくはこちらがわかりやすいかと思います。

qiita.com

では書いてみます。

n, k = map(int, input().split())
s = []
for i in range(n):
    s += [input()]

def judge(b):
    a = [0]*26
    for i in range(n):
        if b>>i & 1:
            t = s[i]
            for j in range(len(t)):
                a[ord(t[j])-ord('a')] += 1
    c = 0
    for i in a:
        if i == k:
            c += 1
    return c

ans = 0
for b in range(1<<n):
    ans = max(ans, judge(b))

print(ans)

Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）
Submission #31318717 - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

judge()では引数を2進数としており、この1、0をそれぞれ文字列を選ぶ、選ばないに対応させて全組み合わせを探索をします。

aは、後述するord()を使って各英子文字が登場する回数を保存しておくものです。

if b>>i & 1は、引数として与えられたbを右にi文字分だけビットシフトさせ、そのときの一桁目が1のときにTrueとなります。

ord()は、引数の文字をUnicodeで対応する数字（10進数）に変換します。
例えば、ord('a')は97（16進数では61）を返します。ord('b')は98、ord('c')は99、…というように増えていくため、ord('a')との相対位置ord(t[j])-ord('a')で各文字と配列aでのインデックスを対応させることができます。
（1つの文字列に同じ文字は登場しないため使える方法。）

そしてif i == kで、登場回数とkが同じになったものについてはカウンターcに1を足し、条件を満たす文字が1つ見つかった、ということになります。

最後の出力部分では、答えが0の可能性もあるので0とjudge(b)の大きいほうを選ぶようにしています。

ちなみに、range(1<<n)はこれもビットシフトを利用した方法で、値だけを見れば1をn文字分だけ左に動かすので1<<nは2**nと言い換えることができます。
（今回の場合は2進数で1~$2^{N}$までの値が欲しいため1<<nを使う。）
例えばn = 3であれば2進数で1000（10進数で8）になります。

疲れたので今回はこのくらいにすることにします。