タムログ

プログラミングについての情報発信をしていきます！

蟻本 §2-1-1 部分和問題 ABC 079 C を Python で AtCoder Beginner Contest 079 C

蟻本をPythonで ABC C問題 AtcoderをPythonで

蟻本 §2-1-1 部分和問題 類題「ARC 061 C – Train Ticket」を Python で解説していきたいと思います。
類題はもう競プロ界隈ではおなじみとなっている，こちらのAtCoder 版！蟻本 (初級編)から参照させていただきました。
蟻本 §2-1-1 部分和問題の Python でのコードはこちらで解説しています。
それでは，まずは問題文から。
https://atcoder.jp/contests/abc079/tasks/abc079_c

C – Train Ticket

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。

切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。

A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。

なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。

制約

  • 0≦A,B,C,D≦9
  • 入力は整数からなる
  • 答えが存在しない入力は与えられない

入力

入力は以下の形式で標準入力から与えられる。

ABCD

出力

作った式を、=7 の部分を含めて出力せよ。

ただし、記号は半角で出力せよ。

また、数字と記号の間に空白を入れてはならない。

入力例 1

1222

出力例 1

1+2+2+2=7

1+2+2+2=7 が条件を満たします。

入力例 2

0290

出力例 2

0-2+9+0=7

この他に、0−2+9−0=7 が条件を満たします。

入力例 3

3242

出力例 3

3+2+4-2=7

解説

他のもっと簡単な解き方でも解けますが，今は深さ優先探索（DFS）がテーマなので，DFSで解いていきたいと思います。
まず 1222 の１から始めて，次に１＋２と１－２で２通りに分かれます。2^3 = 8 通りの遷移図を見ることで，１＋２＋２＋２＝７を得ることができました。
ということで，ここでは i (遷移の回数，０～３），f (その時点の文字列），s (その時点での計算の結果）の３変数を用いて DFS を書いていくと分かりやすいコードを書けると思います。先ほどの１＋２＋２＋２＝７の例でこれの遷移を考えてみます。

  1. (i, f, s) = (0, “1", 1)
  2. (i, f, s) = (1, “1+2", 3)
  3. (i, f, s) = (2, “1+2+2", 5)
  4. (i, f, s) = (3, “1+2+2+2", 7)

あとはこれを実装します。毎回の分岐で + か – かを考えるので，２通りの分岐を行います。
+ の時は，f_i+1 = f_i + “+" + n[i+1]，s_i+1 = s_i + int(n[i+1]) とします。
ー の時は，f_i+1 = f_i + “-" + n[i+1]，s_i+1 = s_i – int(n[i+1]) とします。

最終的に i が 3 になった時，s （計算結果）が７であれば，その数式に =7 を加えたものを返します。そして７でなければ何も返さないように，return ' ' とします。もしこれを書かないと，i = 3 の時に s = 7 でなければ操作が終わらないということになって，i = 4 の場合に飛んでしまい，エラーを起こしてしまいます。
それでは，以下に解答例を載せておきます。

解答例

n = input()

def dfs(i, f, s):
    if i == 3:
        return f+"=7" if s == 7 else ''
    return dfs(i+1, f+"+"+n[i+1], s+int(n[i+1])) or dfs(i+1, f+"-"+n[i+1], s-int(n[i+1]))

print(dfs(0, n[0], int(n[0])))

いかがだったでしょうか。
もしよろしければ twitter のフォロー，リツイートなどよろしくお願いします。
それでは！

他の蟻本系統の問題も解説していますので，こちらも是非ご覧ください。

AtCoder Beginner Contest 163 C を Python で

ABC C問題 AtcoderをPythonで

AtCoder Beginner Contest 163 C を Python で解説していきたいと思います。
それでは，さっそくまずは問題文から。
https://atcoder.jp/contests/abc163/tasks/abc163_c

C – management

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

N 人の社員からなる会社があり、各社員には 1,…,N の社員番号が割り当てられています。

社員番号 1 の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど 1 人います。

X さんが Y さんの直属の上司であるとき、Y さんは X さんの直属の部下であるといいます。

社員番号 i の社員の直属の上司の社員番号が Ai であることが与えられます。各社員について直属の部下が何人いるか求めてください。

制約

  • 2≤N≤2×10^5
  • 1≤Ai<i

入力

入力は以下の形式で標準入力から与えられる。

N
A2 … AN

出力

社員番号 1,2,…,N のそれぞれの社員について、直属の部下が何人いるか、改行区切りで出力せよ。

入力例 1

5 1
1 2 2

出力例 1

2
2
0
0
0

社員番号 1 の社員の直属の部下は社員番号 2,3 の 2 人です。

社員番号 2 の社員の直属の部下は社員番号 4,5 の 2 人です。

社員番号 3,4,5 の社員には直属の部下はいません。

入力例 2

10
1 1 1 1 1 1 1 1 1

出力例 2

9
0
0
0
0
0
0
0
0
0

入力例 3

7
1 2 3 4 5 6

出力例 3

1
1
1
1
1
1
0

解説

少し問題文の意図が読み取りずらい問題ですが，結局は与えられる A2~AN の値の中に，１～Nの値はそれぞれいくつあるかを出力するという問題です。
まず一番簡単に思いつく方法は次のようなコードかと思います。

n = int(input())
a = list(map(int, input().split()))
 
for i in range(1,n+1):
    print(a.count(i))

つまり，そのまま１～Nまでの値 i について，A のリストの中にその数 i は何個あるかを count 関数を使って出力するというものです。
しかしこれだと O(n^2) となり TLE になってしまいます。
そこで，次のような実装を考えます。

まず，あるリスト b を作ります。これは０が n 個あるリストで，A の中の1~N までの値 i の数を表します。
これに for 文を用いて A の中の全ての数を調べ，その数 i に対応する b[i-1] に１を加えます。
あとは b の値をそれぞれ出力してやればよいです。
これだと O(n) でこの問題が解けました。
それでは，以下に解答例を載せておきます。

解答例

n = int(input())
a = list(map(int, input().split()))
 
b = [0]*n
 
for i in a:
    b[i-1] += 1
 
for i in b:
    print(i)

いかがだったでしょうか。
O(n^2) だと TLE になるので，計算量を減らすことを考えることが肝になりました。
何かありましたらコメントしてくださいね！
他の問題も解説しているので，見ていってください！
それでは！

AtCoder Beginner Contest 162 C を Python で

ABC C問題 AtcoderをPythonで

引き続き，AtCoder Beginner Contest 162 C を Python で解説していきたいと思います。
今回はなかなかジャッジが遅かったようで，この問題十分くらいジャッジが出ずになかなか焦りました。(-_-;)
gcd の処理もちょっと抜けていて手がすぐには動かなかったので，それも反省です。
それではもう早速解説に進みます。
まずは問題文から。
https://atcoder.jp/contests/abc162/tasks/abc162_c

C – Sum of gcd of Tuples (Easy)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

\sum_{a=1}^K\sum_{b=1}^K\sum_{c=1}^K gcd(a,b,c)

 を求めてください。

ただし、gcd(a,b,c) は a,b,cの最大公約数を表します。

制約

  • 1≤K≤200
  • K は整数

入力

入力は以下の形式で標準入力から与えられる。

K

出力

\sum_{a=1}^K\sum_{b=1}^K\sum_{c=1}^K gcd(a,b,c)の値を出力せよ。

入力例 1 

2

出力例 1

9

gcd(1,1,1) + gcd(1,1,2) + gcd(1,2,1) + gcd(1,2,2) + gcd(2,1,1) + gcd(2,1,2) + gcd(2,2,1) + gcd(2,2,2) =1+1+1+1+1+1+1+2=9=1+1+1+1+1+1+1+2=9

となるため、答えは 9 です。

入力例 2

200

出力例 2

10813692

解説

１から K までの３つの数 a,b,c のそれぞれの gcd（最大公約数）の和の値を出せと言った問題です。
Σが出てきてぱっと見少しいかついですが，入力例を見てもらえばどういうことか分かると思います。
a，ｂ，ｃ の選び方はそれぞれ１～K あるので，全体として K^3 個の組み合わせがあります。

まずは肝心の最大公約数についてです。
これについては別途記事を書きたいと思いますので，記事を書いたらまたそちらを参考にしてください。
なので，簡単に触れていきます。

最大公約数を求める際は高校数学で扱ったユークリッドの互除法を用いればよいです。
これについて復習すると，整数 a を b で割った商が c で余りが d であった時，すなわち
a = b × c + d
のとき，gcd(a,b) = gcd(b,d)
という関係が成り立つというものでした。
これを用いて，２つの数字の最大公約数を求める関数を次のように定義することができます。

# a >= b でのgcd(a,b)
def gcd2(a,b):
    if b == 0:
        return a
    return gcd2(b,a%b)

２つの数字の最大公約数ということで，関数名を gcd2 と定義しました。
これで２つの数字の間の最大公約数を求める関数が作れました。
これを３つの数字の間の最大公約数を求めようとすると，まず２つの数字の間の最大公約数を求めて，その最大公約数と３つ目の数字との最大公約数を求めればよいです。つまり
gcd(a,b,c) = gcd(gcd(a,b), c)
というわけです。これより，３つの数字の最大公約数を作る関数を次のように定義します。

def gcd3(a,b,c):
    return gcd2(gcd2(a,b), c)

これで最大公約数を求める関数を定義できました。
あとは貪欲に最大公約数を求めることになるのですが，計算時間を減らしてやるために少し工夫してやります。
３つの数 a,b,c の選び方は次の三通りあります。

  1. ３つの値がすべて等しい　ex.) (3, 3, 3)
  2. ２つの値が等しい ex.) (1, 1, 3)
  3. どの値も等しくない ex.) (1, 2, 3)

このパターン１のとき，このような a,b,c の選び方は１通りしかありません。
パターン２のときは，このような a,b,c の選び方は上記の例だと (a,b,c) = (1,1,3), (1,3,1), (3,1,1)の３通りあります。（３C１＝３）
パターン３のときは，３！＝６通りの選び方があります。
このそれぞれについて，３つの数が同じ組み合わせなら当然最大公約数も同じ値になるので，ループの中でこの３パターンを調べ，そのパターンの数を最大公約数にかけてやればよいです。

どういうことかというと，例えば上記のパターン３の時，これは gcd(1,2,3) = 1 なのですが，これが同様にgcd(2,3,1) だとか gcd(3,1,2) だとかの同じ数の組み合わせで６通りあるので，
1 × 6 = 6
を最大公約数の和に加えてやればいいです。

このようにやってあげることで，a,b,c に a ≦ b ≦ c という条件のもとでループをかませるようになり，若干ですが計算量が減ります。

では，以下に解答例を載せておきます。

解答例

k = int(input())
 
def gcd2(a,b):
    if b == 0:
        return a
    return gcd2(b,a%b)

def gcd3(a,b,c):
    return gcd2(gcd2(a,b), c)

ans = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b, k+1):
            if a == b == c:
                ans += gcd3(a,b,c)
            elif a == b or b == c:
                ans += gcd3(a,b,c)*3
            else:
                ans += gcd3(a,b,c)*6

print(ans)

いかがだったでしょうか。
少しみにくいコードではありますが，これで何とか制限時間以内に答えることができました。
もし何かありましたら，気軽にコメントしてくださいね！
それでは！

Atcoder Beginner Contest 160 C を Python で

ABC C問題 AtcoderをPythonで

Atcoder Beginner Contest 160 C を Python で解説していきたいと思います。まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_c

C – Traveling Salesman around Lake

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

1 周 K メートルの円形の湖があり、その周りに N 軒の家があります。

i 番目の家は、湖の北端から時計回りに Ai メートルの位置にあります。

家の間の移動は、湖の周りに沿ってのみ行えます。

いずれかの家から出発して N 軒すべての家を訪ねるための最短移動距離を求めてください。

制約

  • 2≤K≤106
  • 2≤N≤2×10^5
  • 0≤A1<…<AN<K
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

K N
A1 A2 … AN

出力

いずれかの家から出発して N 軒すべての家を訪ねるための最短移動距離を出力せよ。

解説

これはいわゆる巡回セールスマン問題ですね。円形に配置された家の全てを通る最小の距離を考えるという問題になります。
家が N 個あるので，円形の湖はこの家によって N 個の区間に分かれています。
いずれかの家から出発するので，すべての家を通るとき，N 個の区間のうち通らない区間は１つだけになります。よって，最も長い区間をこの通らない区間に設定することで最短距離を求めることができます。

従って，最も長い区間を出すことを試みます。i 番目の家と i+1 番目の家の区間の距離は
Ai+1 – Ai
で出すことができます。ただし，１番目の家と N 番目の家との区間の距離を出すときは注意が必要です。この円一周の長さが K であったので，１番目の家と N 番目の家との距離は
K – (AN – A1)
で出せることが分かります。
以上より，それぞれの区間の距離は以下のように出せます。

  • Ai+1 – Ai （1≦i≦N-1）
  • K – (AN – A1)

この中から最大値を出せばいいわけです。それは最大値を longest とし，まずは longest に K – (AN – A1) を代入して，そのあと for 文でループして出すことにします。
それでは，解答例に移ります。

解答例

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

longest = k - (a[-1] - a[0])

for i in range(n-1):
    if a[i+1] - a[i] > longest:
        longest = a[i+1] - a[i]

print(k-longest)

いかがだったでしょうか。
もし分からないところがあればコメントをお願いします。
それでは！

AtCoder Beginner Contest 161 C

ABC C問題 AtcoderをPythonで

AtCoder Beginner Contest 161 C 問題をPython で解説していきます。
まずは問題文から。
https://atcoder.jp/contests/abc161/tasks/abc161_c

C – Replacing Integer 

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

青木君は任意の整数 x に対し、以下の操作を行うことができます。

操作: x を x と K の差の絶対値で置き換える。

整数 N の初期値が与えられます。この整数に上記の操作を 0 回以上好きな回数行った時にとりうる N の最小値を求めてください。

制約

  • 0≤N≤10^18
  • 1≤K≤10^18
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

操作を 0 回以上好きな回数行った時にとりうる N の最小値を出力せよ。

解説

x と K の差の正負によって絶対値の値は変化するので，正味の操作は以下の２通りになります。

  • x – K > 0 の時：x -> x – K
  • x – K < 0 の時：x -> -(x – K)

なので，x – K > 0 であるときは常にx から K を引き続けていき，x – K < 0 になるまでその操作が続きます。
この操作を行う回数は， N を K で割った時の商になります。よって，その操作を行う回数を l とすると，
N – l * K > 0
となるような最大の n を求めてあげると，l + 1 回目の操作では，
(N – l * K) – K < 0
になるので，この値の絶対値を取ることになります。
よって，この２つの数の大小を比較すればいいことになります。
すなわち，出力すべきは

min(N - l * K, abs((N - l * K) - K)

になります。

解答

n, k = map(int, input().split())

l = n // k

print(min(n - l * k, abs((n - l * k) - k)))

AtCoder Beginner Contest 170 B を Python で

ABC B問題 AtcoderをPythonで

こんばんは。本日行われた AtCoder Beginner Contest 170 B を Python で解説していきたいと思います。
それでは，まずは問題文から。

B – Crane and Turtle

実行時間制限: 2 sec / メモリ制限: 1024 MB×

配点 : 200 点

問題文

庭に何匹かの動物がいます。これらはそれぞれ、2 本の足を持つ鶴か 4 本の足を持つ亀のいずれかです。

高橋くんは、「庭の動物の総数は X 匹で、それらの足の総数は Y 本である」と発言しています。この発言が正しいような鶴と亀の数の組合せが存在するか判定してください。

制約

  • 1≤X≤100
  • 1≤Y≤100
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

X Y

出力

発言が正しいような鶴と亀の数の組合せが存在すれば Yes、なければ No と出力せよ。

入力例 1

3 8

出力例 1

Yes

「庭にいる動物の総数は 3 匹で、それらの動物の足の総数は 8 本である」という発言は、鶴が 2 羽、亀が 1 匹いる場合に正しいため、発言が正しいような鶴と亀の数の組合せは存在します。

入力例 2

2 100

出力例 2

No

この発言が正しいような鶴と亀の数の組合せは存在しません。

入力例 3

1 2

出力例 3

Yes

鶴と亀のうち一方のみが存在する場合も考慮します。

解説

中学受験とかでおなじみのつるかめ算が頭によぎる問題ですね。ただ，今回は鶴と亀のそれぞれの数を出せと言うのではなく，それぞれの数が存在するか否かを出力せよという問題です。

とりあえず，鶴と亀のそれぞれの数を出してみましょう。連立方程式を立てて出しましょう。鶴の数を a，亀の数を b とすると，総数と足の数で次の二式が立てられます。

  • a + b = X
  • 2×a + 4×b = Y

これを解くと次のようになります。

  • a = 2×X – Y/2
  • b = Y/2 – X

ここで，考える条件は，
「a,bそれぞれが負でない整数になる」
です。匹数なのに負の数になるのはおかしいですし，整数でない数になるのもおかしいのでこうなります。ただ，0匹も含めるので，自然数ではなく，負でない整数です。

まず，整数になるという条件は，先ほど出した式から，Y が２で割り切れたらよく，負でないという条件は，aとbがどちらも０以上になるとすればよいです。
結局この条件分岐で判断すればよいです。それでは，解答例に移ります。

解答例

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

a = (4*x-y)/2
b = (y-2*x)/2
if y%2 == 0 and a >=0 and b>=0:
    print('Yes')
else:
    print('No')

いかがだったでしょうか。
問題設定はやはりA問題と比べると少し煩雑にはなりますが，条件分岐はそこまで複雑なものにはなりませんね。
もし分からないところがあれば twitter で気軽にどうぞ。

少しでも参考になれば，twitter のフォロー，ファボ，RTよろしくお願いします。
それでは！

AtCoder Beginner Contest 169 B を Python で

ABC B問題 AtcoderをPythonで

AtCoder Beginner Contest 169 B を Python で解説していきます。とりあえず C はまだ理解が完全と言うわけではないので B を解説します。すぬけさんの生放送でなかなか苦戦されてて，これまでで一番難しい B 問題だとか言ってはったので，なかなか引っかかる問題だと思います。本当に作問者さん素晴らしいですね。いやらしい。笑
それでは，まずは問題文から。

B – Multiplication 2

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

N 個の整数 A1,…,AN が与えられます。

A1×…×AN を求めてください。

ただし、結果が 10^18 を超える場合は、代わりに -1 を出力してください。

制約

  • 2≤N≤10^5
  • 0≤Ai≤10^18
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A1 … AN

出力

値 A1×…×AN を整数として出力せよ。ただし、この値が 10^18 を超える場合は、代わりに -1 を出力せよ。

入力例 1

2
1000000000 1000000000

出力例 1

1000000000000000000

1000000000×1000000000=1000000000000000000 です。

入力例 2

3
101 9901 999999000001

出力例 2

-1

101×9901×999999000001=1000000000000000001 ですが、これは 10^18 を超えるので、代わりに -1 を出力します。

入力例 3

31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0

出力例 3

0

解説

一番簡単にパッと思いつくのは， A をリストとして受け取って，ans という変数に for 文で全要素をかけて格納していって，最後の値が10^18より大きければ -1 を出力するというものではないでしょうか。しかしこれではN と Ai の制限から，ans の値がとてつもなく大きくなってオーバーフローして TLE になってしまいます。Python では整数型の上限はありませんが，あまりに大きい値は扱う際にかなり時間がかかってしまうためです。

これを回避するために，for 文での毎回の計算において，その値が 10^18より大きいかどうか判断します。もし大きければその段階で ans に -1 を代入してあげて，break します。これでオーバーフローを回避できます。

また，入力に０がある場合にも要注意です。この場合は有無を言わさず掛けた値が０になります。Python ではリストに０が含まれているかどうかの判定は次のように行えます。

0 in A:
// 含まれていたら True，含まれていなかったら False の bool値を返す

これをやっておかないと，例えばかけていって１０^１８を超えた後に０の値が出てきた場合，仕様上先に１０^１８を超えた段階で-1を出力して終わってしまうからです。なので実装の優先順位としては次のようになります。

  1. 入力に０が含まれているか　→　含まれていたら０を出力
  2. それぞれの掛け算で10^18を超えるか　→　超えたら -1 を出力
  3. １と２どちらにも該当しなければ普通にかけた値を出力

それでは，解答例に移ります。

解答例

import sys
n = int(input())
A = list(map(int, input().split()))

ans = 1
if 0 in A:
  print(0)
  sys.exit()
  
for i in range(n):
  ans *= A[i]
  if ans > 1e18:
    ans = -1
    break

print(ans)

いかがだったでしょうか。
確かになかなか難しい問題だったかと思います。
すぬけさんの生放送聞きながら書いていたのですが面白かったです。w
こんなこと言ったら怒られそう()

もしおかしいところなどがあった場合はtwitterで教えてください。
それでは！