AtCoder-ABC216 C - Many Balls【Python解答例】

AtCoder Beginner Contest216のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 216 - AtCoder

AtCoder Beginner Contest216 C - Many Balls

C - Many Balls

問題文

空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。

魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする
合計 120 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

・1≤N≤10 ^18
・入力は全て整数

解答例

n = int(input())

res = ""
while n > 0:
    if n % 2 == 0:
        n = n // 2
        res = "B" + res
    else:
        n -= 1
        res = "A" + res

print(res)

解説

魔法Aでボールを1つ増やし、魔法Bでボールを2倍にするとき、ちょうどN個のボールを作る方法を答える問題です。

魔法の使う順番の文字列はresとしました。

魔法の順番を逆から見ていき、Nが偶数なら魔法Bを使い、奇数なら魔法Aを使うこととしてresに文字を格納していきました。

nが0になるまでwhile文でループさせ、nが偶数ならnを2で割り、文字列resの先頭にBを足します。
nが奇数ならnから1だけ引いて、文字列resの先頭にはAを足していきました。

この操作をnが0になるまで繰り返すことで求める答えとなりました。

ABC216の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC216 A - Signed Difficulty / B - Same Name【Python解答例】

AtCoder Beginner Contest216のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 216 - AtCoder

AtCoder Beginner Contest216 A - Signed Difficulty

A - Signed Difficulty

問題文

実数 X.Y が与えられます。ただし Y はちょうど 1 桁です。

0≤Y≤2 ならば、X-
3≤Y≤6 ならば、X
7≤Y≤9 ならば、X+
と出力してください。

制約

・1 ≤ X ≤ 15
・0 ≤ Y ≤ 9
・X と Y は整数

解答例

x, y = map(int,input().split("."))

if 0 <= y <= 2:
    print(str(x)+"-")
elif 3 <= y <= 6:
    print(str(x))
elif 7 <= y <= 9:
    print(str(x)+"+")

解説

整数部がX、小数部がYの実数が与えられ、Yの値にあわせて+や-を付け加えて出力する問題です。

正直、入力の受け取り方に戸惑いましたが、split(".")とすることで.の前をX、.の 後ろをYに代入することができました。

あとは問題文の通りにYについて場合分けを行い、Xの後ろに+や-をつけて出力すればOKでした。

AtCoder Beginner Contest216 B - Same Name

B - Same Name

問題文

N 人の人がいます。i(1≤i≤N) 人目の人の姓は S i​ 、名は T i​ です。

同姓同名であるような人の組が存在するか、すなわち 1≤i

制約

・2≤N≤1000
・N は整数
・S i​ ,T i​ は英小文字のみからなる長さ 1 以上 10 以下の文字列

解答例

n = int(input())

S = []
T = []
for i in range(n):
    s, t = input().split()
    S.append(s)
    T.append(t)

flag = False
for i in range(n-1):
    if flag:
        break
    for j in range(i+1,n):
        if S[i] == S[j] and T[i] == T[j]:
            flag = True
            break

if flag:
    print("Yes")
else:
    print("No")

解説

同姓同名の人がいるかどうか答える問題です。

制約が厳しくないのですべての人の組み合わせを全探索します。

同姓同名の人がいるかはflagを用いて、もし同姓同名がいればTrueとなるように管理します。

if S[i] == S[j] and T[i] == T[j] の部分でi番目とj番目の人の姓(S)と名(T)を比較し、両方一致していればflagをTrueとします。

最後にflagにあわせて答えを出力すればACでした。

ABC216の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

【AtCoder版！蟻本】AtCoder-ABC084 D - 2017-like Number【エラトステネスの篩】

AtCoder版！蟻本のエラトステネスの篩の例題としてあげられているABC084 D - 2017-like Number をPythonで解いていきます。

リンク

ABC084 D - 2017-like Number

D - 2017-like Number

問題文

「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。

Q 個のクエリが与えられます。

クエリ i(1≦i≦Q) では奇数 l i​ ,r i​ が与えられるので、l i​ ≦ x ≦ r i​ かつ 2017に似た数 となる奇数 x の個数を求めてください。

制約

・1≦Q≦10^5
・1 ≦ l i​ ≦ r i​ ≦ 10^5
・l i​ ,r i​ は奇数
・入力は全て整数

解答例

解説

「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 として、与えられたQ個のクエリについてLi <= x <= Riかつ2017に似た数となるxの個数を答える問題です。

まずエラトステネスの篩でriの最大値10^5までの素数をprime配列に列挙します。
エラトステネスの篩はこちらのページで記載しましたので参照してください。
ebisuke33.hatenablog.com

次に2017に似た数字の数を調べるためlike2017配列を作成し、primeに格納された数が2017に似た数か判定しました。

tmpに(N+1)÷2 を代入し、このtmpがprime配列にあれば2017に似た数なのでprime配列の該当する要素に1を足します。

2017に似た数字を調べ終えると、変数sumに累積和をとりlike2017配列をsumで更新しました。

最後に各クエリに対して、riまでの累積和num_rから li - 1までの累積和num_lを引けば求める解答です。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】天下一プログラマーコンテスト2012 予選C A【エラトステネスの篩】

AtCoder版！蟻本のエラトステネスの篩の例題としてあげられている天下一プログラマーコンテスト2012 予選C をPythonで解いていきます。

リンク

A - 与えられた数より小さい素数の個数について

A - 与えられた数より小さい素数の個数について

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

制約

・自然数 n ( 1≤n≤10,000 ) が 1 行で与えられる。

解答例

# x以下の素数列挙
def sieve_of_eratosthenes(x):
    nums = [i for i in range(x+1)]

    root = int(pow(x,0.5))
    for i in range(2,root + 1):
        if nums[i] != 0:
            for j in range(i, x+1):
                if i*j >= x+1:
                    break
                nums[i*j] = 0

    primes = sorted(list(set(nums)))[2:]

    return primes

n = int(input())

ans = sieve_of_eratosthenes(n-1)

print(len(ans))

解説

与えられた整数Nより小さい素数の数を答える問題です。

ある値より小さい素数の数をかぞえるにはエラトステネスの篩という手法があります。

こちらのページで記載しましたので参照してください。
ebisuke33.hatenablog.com

この手法を用いることでansに素数の配列が代入されますので、その要素数を答えることでACをとることができました。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

エラトステネスの篩で素数列挙【Python】

ある値以下の素数を列挙する方法のひとつにエラトステネスの篩（ふるい）があります。

この記事ではPythonでエラトステネスの篩をプログラミングしていきます。

エラトステネスの篩とは

次のように整数n以下の素数を高速にすべて列挙する方法です。

まず2からnまでの数を考え、この数字のなかで最も小さい数字をpとおき、n以下かつp以外のpの倍数をすべて消していきます。

消し終えたら、その中で最も小さい数字をpとおき倍数を消していく・・・という作業を繰り返します。

pが√nを超えたら終了です。

このときに残った数字が素数になります。

素数列挙プログラム(n = 100の場合)

# x以下の素数列挙
def sieve_of_eratosthenes(x):
    nums = [i for i in range(x+1)]

    root = int(pow(x,0.5))
    for i in range(2,root + 1):
        if nums[i] != 0:
            for j in range(i, x+1):
                if i*j >= x+1:
                    break
                nums[i*j] = 0

    primes = sorted(list(set(nums)))[2:]

    return primes


p = sieve_of_eratosthenes(100)

print(p)
# --> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print(len(p))
# --> 25

解説

nums[i] = iとなる配列を作成して素数の列挙をすすめていきます。

エラトステネスの篩は√nより大きい数字になれば終了してよいのでrootに√nを計算し、このrootを用いてループの範囲は2からroot + 1として進めます。

nums[i]が0なら次の数字にスキップし、0でなければさらにループさせ倍数を削除します。

2重ループではp[i]の倍数であるi × jを0に置き換えました。（nums[i*j] = 0）

この探索を終えるとnumsに残る値は素数か0です。

0が複数あるnumsをset(nums)としてset型を利用して0の重複を削除しました。

このset(nums)を再度list()でリスト化し、ソートします。

これで[0, 1, 2, 3, 5, 7… ,97]という配列になるので、不要になる初めの2つの要素をスライスして取り除きます。

その結果、primes = sorted(list(set(nums)))[2:] = [2, 3, 5, 7… ,97]という求める素数を列挙した配列を作成できました。

primesをlen()で個数を調べることで素数の数を数えることもできます。

上記のプログラムで高速に素数を列挙することができました！

エラトステネスの篩についてこちらの記事が参考になりました。
ありがとうございました。
club.informatix.co.jp

AtCoder-ABC215 D - Coprime 2【Python解答例】

AtCoder Beginner Contest215のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 215 - AtCoder

AtCoder Beginner Contest215 D - Coprime 2

D - Coprime 2

問題文

長さ N の正整数列 A=(A1,A2,…,AN) が与えられるので、以下の条件を満たす 1 以上 M 以下の整数 k を全て求めてください。

全ての 1≤i≤N を満たす整数 i について、 gcd(Ai,k)=1 である。

制約

・入力は全て整数
・1 ≤ N,M ≤ 10^5
・1 ≤ Ai ≤ 10^5

解答例

# 約数をdivに加える
def make_divisors(n):
    i = 1
    while i*i <= n:
        if n % i == 0:
            div.add(i)
            if i != n // i:
                div.add(n//i)
        i += 1
    return


N, M = map(int,input().split())

A = list(map(int, input().split()))

# 約数列挙
div = set()

# Aiの約数を求める
for i in range(N):
    make_divisors(A[i])

# set型divから配列ansへ変換
Div = list(div)

# 答えの配列(1~M)
res = [True for i in range(M)]

# 約数の倍数をFalseに
for i in range(len(Div)):
    # Div[i]が1ならスキップ
    if Div[i] == 1:
        continue
    k = 1
    while Div[i] * k <= M:
        res[Div[i] * k - 1] = False
        k += 1

# 解答の配列(1は加えておく)
ans = [1]
for k in range(1,M):
    # resがTrueならINDEXをansに追加
    if res[k]:
        ans.append(k+1)

#答えの数と値を出力
print(len(ans))
for i in range(len(ans)):
    print(ans[i])

解説

数列Aの各要素と互いに素な整数kをすべて求める問題です。

まずAの各要素の約数を列挙しました。
make_divisors関数でAiの約数をdivに格納していきます。
重複を避けるためdivはset型にしました。

次に1からMまですべてTrueの配列resを用意し、約数のすべての倍数をFalseにしました。

解答となるans配列にresがTrueのままのIndexを格納していくことで答えが求まります。

ABC215の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC215 C - One More aab aba baa【Python解答例】

AtCoder Beginner Contest215のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 215 - AtCoder

AtCoder Beginner Contest215 C - One More aab aba baa

C - One More aab aba baa

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

制約

・1 ≤ |S| ≤ 8
・S は英小文字のみからなる
・S の各文字を並べ替えてできる文字列は K 種類以上存在する

解答例

import itertools

s, k = input().split()

k = int(k)

res = set()
for nums in itertools.permutations(range(len(s))):
    tmp = ""
    for i in range(len(nums)):
        tmp = tmp + s[nums[i]]
    res.add(tmp)

ans = list(res)

ans.sort()

print(ans[k-1])

解説

文字列Sを並び替えてできる文字列をすべて辞書順に列挙したときに、K番目の文字列がなにか答える問題です。

Sが最大で8文字と少ないので順列全探索で作成できる文字列を列挙しました。

順列について過去に勉強した記事はこちら
ebisuke33.hatenablog.com

itertoolsでSの文字数までの順列を作成しnumsとしました。
numsにしたがってSから順番に文字を抜き取っていき、tmpに加えていきます。
tmpが完成したらresに追加しました。

このとき、重複する可能性があるのでresはset型としています。

探索を終えた後にソートするためset型のresを配列ansに変換しました。

ソートした後でansのk-1番目の要素を出力すればACでした。

ABC215の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC215 A - Your First Judge / B - log2(N)【Python解答例】

AtCoder Beginner Contest215のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 215 - AtCoder

AtCoder Beginner Contest215 A - Your First Judge

A - Your First Judge

問題文

文字列 S が与えられるので、この文字列が Hello,World! と完全に一致するなら AC 、そうでないなら WA と出力してください。

制約

・1 ≤ |S| ≤ 15
・S は英大小文字, ,, ! のみからなる

解答例

s = input()

t = "Hello,World!"

if s == t:
    print("AC")
else:
    print("WA")

解説

与えられる文字列SがHello,World! と完全に一致するか答える問題です。

問題文に記載があるように「文字列 A と B が完全に一致するとは、文字列 A と B の長さが等しく、かつ全ての 1≤i≤|A| を満たす整数 i について A の先頭から i 文字目と B の先頭から i 文字目とが(英大文字か小文字かも含めて)一致することを指します。」が完全一致の条件ですが、Pythonでは == だけで比較できます。

したがって解答例のようにs == tならAC、違うならWAを出力すればOKでした。

AtCoder Beginner Contest215 B - log2(N)

B - log2(N)

問題文

正整数 N が与えられるので、 2k ≤ N となる最大の整数 k を求めてください。

制約

・N は 1 ≤ N ≤ 10^18 を満たす整数である

解答例

n = int(input())

if n == 1:
    print(0)
else:
    for k in range(100):
        if pow(2,k) <= n:
            continue
        else:
            print(k-1)
            break

解説

N <=10^18 なので ｋは最大で60程度の値になります。

したがってi を（大きすぎですが）100までループさせて、2^iとnを比較します。

nより大きくなったときのi-1（n が 1のときは0）を出力すればOKです。

ABC215の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com