AtCoder-ABC183 C - Travel【python解答例】

AtCoder Beginner Contest183 C問題に挑戦です。

実際にコンテストに出たときは解けませんでしたが、前回の記事のように順列の勉強を行いましたので再挑戦してみたいと思います。
ebisuke33.hatenablog.com

AtCoder Beginner Contest183 C - Travel

atcoder.jp

問題文

N個の都市があります。都市iから都市jへ移動するにはTi,jの時間がかかります。
都市1を出発し、全ての都市をちょうど1度ずつ訪問してから都市1に戻るような経路のうち、移動時間の合計がちょうどKになるようなものはいくつありますか？

制約

・2≤N≤8
・i≠jのとき1≤Ti,j≤10^8
・Ti,i=0
・Ti,j=Tj,i
・1≤K≤10^9
・入力はすべて整数

解答例

import itertools

n, k = map(int,input().strip().split())
tlist = []

for i in range(n):
    array = list(map(int, input().strip().split()))
    tlist.append(array)

counter = 0

per_list = list(itertools.permutations(range(1,n))) # (※1)
# print(per_list)

for i in per_list:
    # print(i) (※2)
    i = [0] + list(i) + [0]
    # print(i) (※3)
    t_sum = 0
    for j in range(n):
        t_sum += tlist[i[j]][i[j+1]] # (※4)
    if t_sum == k:
        counter += 1

print(counter)

解説

順列を学びましたが簡単にはいきませんでしたので、細かい説明をしながら進めたいと思います。
まず、※1の部分では順列を作成しました。
ですがn = 4の場合、次の行で出力した結果は[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]のようになります。
問題文から都市0から出発し、都市0に戻らなければならないのでその途中の経路を作成したイメージです。
私は公式解説だけではここが理解できず、かなり悩みました。
※2ではさきほど作成した順列のなかからひとつづつ取り出してループさせています。
例として(2,1,3)を取り出した場合で説明します。
※2の次の行における出力は(2,1,3)となり、都市2からスタートし、都市3に到着して終わりとなってしまいます。
したがって、i = [0] + list(i) + [0]の部分でリストの最初と最後に0を追加します。
これで※3の出力は(0,2,1,3,0)となり、都市0からスタートし、都市0に戻るという問題文通りの経路の順列を考えることができます。
※4ではt_sum変数にどんどん都市移動の時間を足していっています。
例に挙げた(0,2,1,3,0)では①tlist[0][2]（都市0から2への移動時間）②tlist[2][1]（都市2から1への移動時間）③tlist[1][3]（都市1から3への移動時間）④tlist[3][0]（都市3から0への移動時間）と順に足していきます。
その後、移動時間を足し終えたt_sumとkが一致していたらcounter変数を1増加させていき、すべての場合において確認が終わったら、counter変数を出力しています。
以上の考え方でプログラムを作るとACとなりました。

順列を学べば簡単にできるとたかをくくっていましたが、実際には問題にあわせて工夫が必要で難しかったです。
頭をつかって応用することが大事なんですね。

次はABC183のD問題に挑戦したいと思います。
学ぶことが多くて大変ですが、新しいことを覚えていく感覚を大事にして頑張りたいです。

ABC183についての以前の記事はこちら
ebisuke33.hatenablog.com

Pythonで順列と組み合わせの勉強

AtCoder ABC183 Cに取り組みましたが、
残念ながら解くことができませんでした。

今回は公式解説に出ていた順列（と組み合わせ）について勉強したいと思います。

順列とは

はじめに順列について確認します。
順列とは「n個のなかからr個を順番に選ぶ」場合の数です。
例えば(1,2,3,4)の全4個のなかから3個を選ぶ順列は4P3のように表記し、その値は4×3×2 = 24通りとなります。
(1,2,3,4)のなかからひとつ目の数字の選び方は4通り、次の数字はひとつ目を除いた数になるので3通り、その次は2通りと、順番に減っていく場合の数の掛け合わせたものが求める場合の数になります。

組み合わせとは

本題から外れますが順列とセットで習う組み合わせについても記載します。
組み合わせとは「n個のなかからr個選ぶ」組み合わせの数です。
順列では例えば(1,2,3)と(2,1,3)は選ぶ順番が違うので別のものとカウントしますが、組み合わせでは選ばれているものが同一なので同じものとしてカウントします。
組み合わせはnCkと表記し、その計算はn!/{k!×(n-k)!}となります。

itertoolsについて

Pythonで順列や組み合わせを考えるときにitertoolsモジュールを使用するととても便利です。

itertoolsモジュールによる順列リストの作成

import itertools

nums = [1, 2, 3]  # 順列を求めるリスト

perm = itertools.permutations(nums)

print(list(perm))

# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

itertoolsモジュールをインポートします。
permutations関数を上記のように使用すると6通りすべて挙げることができました。

itertoolsモジュールによる組み合わせリストの作成

import itertools

nums = [1, 2, 3]  # 組み合わせを求めるリスト

comb = itertools.combinations(nums,2) # numsの中から2つ選ぶ組み合わせ

print(list(comb))

# [(1, 2), (1, 3), (2, 3)]

combinations関数を用いてnumsから2つ選ぶ組み合わせも簡単に求めることができました。

こんな簡単に順列や組み合わせを求めることができるなんて知りませんでした。
次回はこの内容を活かしABC183 C問題に挑戦します。

AtCoder-ABC183 A - ReLU / B - Billiards【Python解答例】

先日AtCoder Beginner Contest183を受けました。

結果はA・B問題だけACでしたが、
そのときの私の解答を書きたいと思います。

AtCoder Beginner Contest183 A - ReLU

atcoder.jp

問題文意訳

整数xが0以上ならx、0より小さければ0となるReLU関数に対して、
整数 xが与えられるので ReLU(x)を求めてください。

制約

・xは整数
・−10≤x≤10

解答例

# coding:utf-8

x = int(input())

if x >= 0:
    print(x)
else:
    print("0")

解説

入力xが0以上ならそのままxを出力、
0より小さい値なら0を出力する問題でした。

AtCoder Beginner Contest183 B - Billiards

atcoder.jp

問題文

高橋君は2次元平面上でビリヤードをしています。
x軸は壁になっており、球をぶつけると入射角と反射角が等しくなるように球が跳ね返されます。
いま高橋君の球が (Sx,Sy)にあります。
ある座標を狙って球を撞くと、球はその座標へ向かって直線的に転がっていきます。
x軸で球をちょうど1回反射させたのち、(Gx,Gy)を通過させるためには、x軸のどこを狙えば良いでしょうか？

制約

・−10^6≤Sx,Gx≤10^6
・0

解答例

# coding:utf-8

sx, sy, gx, gy = map(int,input().strip().split())

if sx < gx:
    dx = gx - sx
    dy = sy + gy

    k = dy / dx
    xzero = sx + sy / k

    print(xzero)
else:
    dx = sx - gx
    dy = sy + gy

    k =  dy / dx
    xzero = sx - sy / k

    print(xzero)

解説

この問題は最初ボールが置いてある(Sx,Sy)のx軸に対称な点(Sx,-Sy)を考えて、
点(Sx,-Sy)と点(Gx,Gy)を結ぶ直線とx軸の交点を求める方法を思いつきました。
上記は実際のコンテストでの解答で、次のように2つの場合分けを行いましたが、
コンテスト後に考えてみると別にこの場合分けは不要だとわかりました。（なんともまぬけですね…）
・SxがGxより小さい場合
・SxがGxより大きい場合
とにかく、Syを-Syとした点を考えて、
まずSxとGxの差dxを求め、
次に-SyとGyの差(Gy-(-Sy)=Gy+Sy)dyを求めて、傾きkを求めました。
最終的にx軸との交点xzeroを上記のように求め、出力することでACでした。

その後C問題はすべての組み合わせ求め方がわからず、D問題はTLEとなり解けませんでした。
解説を見ると知らない方法の記載がありましたので次は新しく学習した内容を書き、
C問題とD問題を解いてみたいと思います。

現状とこれからの勉強方法について

AtCoderを初めて1か月ほど経過しました。

現在のレーティングは（恥ずかしながら）63です。

ABCに3回出ましたが、
A問題とB問題は解けましたが、
C問題以降が解けませんでした。

頭でこう解いたらいいと思い浮かんでもプログラムに反映できないことがあり、
くやしい思いをしています。

今後はC問題とD問題の過去問を解いていくとともに、
受けたコンテストの振り返りと新しく覚えたことを中心に書いていきたいと思います。

初心者ゆえにもどかしい思いをすることばかりですが、
地道に勉強を続け、このブログに覚えたことをアウトプットしていきたいと思います。

AtCoderに登録したら解くべき過去問精選10問 #4【Python解答例】

AtCoder Beginners Selectionのpythonでの解答の最後の記事です。

ABC049C - 白昼夢

atcoder.jp

問題文

英小文字からなる文字列Sが与えられます。
Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで
S=Tとすることができるか判定してください。

・Tの末尾に dream dreamer erase eraser のいずれかを追加する。

制約

・1≦|S|≦10^5
・Sは英小文字からなる。

解答例

# coding:utf-8

s = input()

string_divide = ["dream", "dreamer", "erase", "eraser"]

new_s = s[::-1]
new_divide = []
k = 0

for i in range(4):
    alt = string_divide[i]
    new_divide.append(alt[::-1])

can = True
for i in range(len(s)):
    can2 = False
    if k > i:
        continue
    for j in range(4):
        d = new_divide[j]
        if new_s[i:i + len(d)] == d:
            can2 = True
            k = i + len(d)
    if can2 == False:
        can = False
        break

if can == True:
    print("YES")
else:
    print("NO")

解説

Tに追加できる4つの単語は前から読むと
例えばdreamerの最後のerとeraseの最初のerがかぶり、
dreamとdreamerのどちらを用いるか判断が難しいです。
反対から読むと上記のような重なりがなくなるので、
new_divideリストに4つの単語を反対にした文字列を格納しました。
同様に入力sを反対にした文字列new_sを作成し、
for分内でnew_sがnew_divideと一致するか確認し、
すべて一致する場合のみcanフラグがTrueのままループを抜けるようになっています。
文字列の一致確認にはスライスを用いました。
便利な機能だと思いましたので、しっかりと使い方を覚えたいです。

ABC086C - Traveling

atcoder.jp

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。
AtCoDeerくんの旅行プランでは、
時刻 0に 点 (0,0)を出発し、1以上 N以下の各 iに対し、
時刻 tiに 点 (xi,yi)を訪れる予定です。
AtCoDeerくんが時刻 tに 点 (x,y)にいる時、
時刻 t+1には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。
その場にとどまることは出来ないことに注意してください。
AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

・1≤N≤10^5
・0≤xi≤10^5
・0≤yi≤10^5
・1≤ti≤10^5
・ti < ti+1(1≤i≤N−1)
・入力は全て整数

解答例

# coding:utf-8

n = int(input().strip())

a = [[0, 0, 0]]
for i in range(n):
    b = list(map(int, input().strip().split()))
    a.append(b)

can = True

for i in range(n):
    dt = a[i+1][0] - a[i][0]
    dist = abs(a[i+1][1] - a[i][1]) + abs(a[i+1][2] - a[i][2])
    if dt < dist:
        can = False
    if dist % 2 != dt % 2:
        can = False

if can == True:
    print("Yes")
else:
    print("No")

解説

問題文から時刻tが1増加するごとにxかyのどちらか1のみ増加、あるいは減少します。
for分では点iから次の点(i+1)に到着するまでの時間dtと
xとyのそれぞれ何マスあるかを示す距離distを求めます。
tが1増加するごとに1マスしか動けませんので、
dtがdistより小さければ次の目的地に着くことはできませんのでcanフラグをFalseにします。
dtがdistより大きい場合、
distが偶数であれば行ったり来たりを繰り返して時刻tiで目的地に着くことができます。
distが奇数の場合、
時刻tiでは1マスずれた位置にしか存在できないので、このときもcanフラグをFalseにします。
canフラグがTrueのままループを抜ければYesを出力し、そうでなければNoを出力します。

これでAtCoder Beginners Selectionが一通り終わりました。
とんでもなく難しいプログラムを考えなくても大丈夫という印象ですが、
どんな場面でも問題なく答えにたどり着くロジックを考えることが大変だと感じました。
慣れもあると思いますので、今後もコンテストに多く出て経験を積みたいです。

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

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

競技プログラミングの学習にはこちらの本もおすすめです。

リンク

リンク

リンク

AtCoderに登録したら解くべき過去問精選10問 #3【Python解答例】

今回もAtCoder Beginners Selectionをpythonで解いていきます。

ABC085B - Kagami Mochi

atcoder.jp

問題文

X段重ねの鏡餅 (X≥1)とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。
例えば、直径 10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。
ダックスフンドのルンルンは N枚の円形の餅を持っていて、そのうち i枚目の餅の直径はdiセンチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

・1≤N≤100
・1≤di≤100入力値はすべて整数である。

解答例

# coding:utf-8
 
n = int(input())

s = [int(input()) for i in range(n)]

s.sort(reverse=True)

count = 1
d_now = s[0]

for i in range(n):
    if s[i] < d_now:
        d_now = s[i]
        count += 1

print(count)

解説

これも意味がわかりにくい問題でしたが、
直径の順にもちを重ねていくと（同じ直径のもちは除く）何段重ねになるかを求めました。
入力をリストsに格納しソートします。
一番大きなもち（s[0]）を初期値としてs[i]が現在のもちの直径（d_now）より小さければd_nowを更新し、count変数を1増加させました。

ABC085C - Otoshidama

atcoder.jp

問題文

日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

・1≤N≤2000
・1000≤Y≤2×10^7
・Nは整数である。
・Yは1000の倍数である。

解答例

#python
# coding:utf-8
 
n,y = map(int,input().split(" "))

res10000 = -1
res5000 = -1
res1000 = -1

for a in range(n+1):
    for b in range(n-a+1):
        c = n - a - b
        total = 10000*a + 5000*b + 1000*c
        if total == y:
            res10000 = a
            res5000 = b
            res1000 = c

print(str(res10000) + " " + str(res5000) + " " + str(res1000))

解説

この問題も3重ループを使うと時間切れになるため、
問題文から千円札の枚数cは一万円札の枚数aと五千円札の枚数bが決まれば（成立するかは置いといて）求まります。
これで2重ループにすることで時間切れにならずに問題を解くことができます。

問題の難度があがるとプログラミングの技術はもちろんですが、
数学的に簡単に問題を解くことが要求されます。
いろいろな勉強を行うことがいい成績を残すうえで大事だと思いました。

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

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

競技プログラミングの学習にはこちらの本もおすすめです。

リンク

リンク

リンク

AtCoderに登録したら解くべき過去問精選10問 #2【Python解答例】

AtCoder Beginners Selectionという初心者向けの問題を今日も取り組みます。

ABC087B - Coins

atcoder.jp

問題文

あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

・0≤A,B,C≤50
・A+B+C≥1
・50≤X≤20,000
・A,B,Cは整数である
・Xは50の倍数である

解答例

# coding:utf-8

a = int(input())
b = int(input())
c = int(input())
x = int(input())

counter = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if 500 * i + 100 * j + 50 * k == x:
                counter += 1

print(counter)

解説

目標とするx円になる硬貨の組み合わせを求める問題です。
3重ループで3種類の硬貨の組み合わせを試し、xと一致すればcounter変数を増加させています。
初心者ゆえにfor分の範囲が(a+1)のように1を足さなければならないことがわからず、
めちゃくちゃ時間をかけて悩んでしまいました。
理論的にはあっているのに間違っている場合は、こんなミスがあったことを思い出したいです。

ABC083B - Some Sums

atcoder.jp

問題文

1以上 N以下の整数のうち、10進法での各桁の和が A以上 B以下であるものの総和を求めてください。

制約

・1≤N≤10＾4
・1≤A≤B≤36
・入力はすべて整数である

解答例

# coding:utf-8
 
n,a,b = map(int, input().split(" "))
 
all_sum = 0
 
for i in range(n + 1):
    k = i
    total = 0
    while k > 0:
        total += k % 10
        k = k // 10
    if total >= a and total <= b:
        all_sum += i
 
print(all_sum)

解説

このあたりから変数の使い方がぐちゃぐちゃになってきました。
all_sumが求める答えで、totalが各桁の和です。
while文による各桁の和の求め方が勉強になりました。

ABC088B - Card Game for Two

atcoder.jp

問題文

N枚のカードがあります. i枚目のカードには, aiという数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約

・Nは 1以上 100以下の整数
・ai (1≤i≤N)は 1以上 100以下の整数

解答例

# coding:utf-8

n = int(input())
a = list(map(int, input().split(" ")))

a.sort(reverse=True)

alice = 0
bob = 0

for i in range(n):
    if i % 2 == 0:
        alice += a[i]
    else:
        bob += a[i]

print(alice - bob)

解説

問題文の意味を理解することが大変でしたが、
アリスから順番に場にある一番大きな数字が書かれたカードをとっていき、
最後にその得点差を競うゲームのようです。
sortを用いてリストを大きい数字の順に並び替え、
順番にアリスとボブに点数を足していきました。

徐々に難しい問題になると頭がこんがらがり、何をどうすればよいかわからなくなることがありました。
落ち着いて問題が解けるよう練習を続けたいです。

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

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

競技プログラミングの学習にはこちらの本もおすすめです。

リンク

リンク

リンク

AtCoderに登録したら解くべき過去問精選10問 #1【Python解答例]】

AtCoderで初めてコンテストに出たものの、
まったく歯が立たずどうしようか迷っていたところ、
AtCoder Beginners Selectionという初心者向けの問題を集めてくれていましたのでそれに取り組みました。

ABC086 A - Product

atcoder.jp

問題文

シカのAtCoDeerくんは二つの正整数a,bを見つけました。aとbの積が偶数か奇数か判定してください。

制約

・1≤a,b≤10000
・a,bは整数

解答例

# coding:utf-8

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

if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")

入力を受け取って、その積が偶数かどうかを判別する問題です。
偶数か奇数かの判別は２で割って、その余りが０かどうかで判別できます。

ABC081 A - Placing Marbles

atcoder.jp

問題文

すぬけ君は 1,2,3の番号がついた3つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス iにはsiが書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約

・s1,s2,s3は'1'あるいは'0'

解答例

# coding:utf-8

s = input()

count = 0

if s[0] == "1":
    count += 1
if s[1] == "1":
    count += 1
if s[2] =="1":
    count += 1

print(count)

解説

文字列をstring型で受け取り、'1'が何個あるか数えました。

ABC081 B - Shift only

atcoder.jp

問題文

黒板にN個の正の整数 A1,...,ANが書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
黒板に書かれている整数すべてを、2で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約

・1≤N≤200
・1≤Ai≤10^9

解答例

# coding:utf-8

n = int(input())

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

flag = 0
counter = 0

while True:
    for i in range(n):
        if a[i] % 2 != 0:
            flag = 1
    if flag == 1:
        break
    for i in range(n):
        a[i] = a[i]//2
    counter += 1

print(counter)

解説

まずn個の正の整数をリストaに格納します。
while文では、リストaに格納されたすべての数字に奇数があるか調べます。
奇数があればflagを立ててwhileを抜けます。
すべて偶数であれば、リストaの数字を2で割って、counter変数に1を足します。
最後にwhileが抜けたあとにcounterを出力すれば求める答えとなります。

最初は簡単な問題でしたが徐々に難しく感じるようになりました。
問題は10問ありましたので、残りの問題もあとで投稿したいと思います。

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

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

競技プログラミングの学習にはこちらの本もおすすめです。

リンク

リンク

リンク