PythonでAtCoder Beginner Contest 079 ABC079 - やるだけPython競プロ日誌

AtCoder Beginner Contest 079 ABC079

2017/11/19 21:00 ～ 22:40の問題でした。

簡単に説明すると

A：orで3つをイコール

B：リュカ数を求める(キャッシュが好ましい)

C：3重ループ

D：ワーシャルフロイド

となります。

A : Good Integer

問題文

1118 のような、3 つ以上の同じ数字が連続して並んだ 4 桁の整数を良い整数とします。
4 桁の整数 N が与えられるので、N が良い整数かどうかを答えてください。

制約

1000≦N≦9999

入力は整数からなる

入力

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

出力

N が良い整数ならば Yes を、そうでなければ No を出力せよ。

素直に解いてみましょう

n = input()  # 入力を受け入れ
if n[0] == n[1] == n[2] or n[1] == n[2] == n[3]:  # 3つ並んでいる場合
  print("Yes")
else:
  print("No")

初心者の方にありがちなのが、"==" を "=" にしてしまうということです。

"="は代入に使うのに対し、"=="は比較演算子ですので、全くの別物です。
注意しましょう。

B : Lucas Number

問題文

今、日本は 11 月 18 日ですが、11 と 18 は隣り合うリュカ数です。
整数 N が与えられるので、N 番目のリュカ数を求めてください。
ただし、リュカ数は i 番目のリュカ数を Li とすると、
L0=2
L1=1
Li=Li−1+Li−2(i≧2)
と定義される数とします。

制約

1≦N≦86

答えは 1018 より小さいことが保証される

入力は整数からなる

入力

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

出力

N 番目のリュカ数を出力せよ。

何も考えずにやると、

def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n - 1) + lucas(n - 2)
print(lucas(int(input())))

というような再帰になるかもしれませんが、これだと明らかにTLE(時間超過)してしまいます。

なので、ここで超絶便利な方法をお教えします。

"@functools.lru_cache()"!!!\ﾃｯﾃﾚﾃｯﾃﾃｰ/

使い方は簡単！

import functools

@functools.lru_cache()
def 以下略

def　の一行前に書いてやることで、関数の戻り値を保存してくれるキャッシュを使えるようになります。

ええ、その速さは劇的です。劇的。

lucas(86)なんてしようものならどんな時間がかかるか想像できたものではありません

計算量でいうと O(580696784543858400) 位です。

しかし、キャッシュを使えば O(85) です。

比べ物にならないですよね。

ということで

import functools

@functools.lru_cache()
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n - 1) + lucas(n - 2)
print(lucas(int(input())))

これでよいです。
あるいは、

n = int(input())
 
lis = [2,1]
for i in range(2, n+1):
  lis.append(lis[i-1] + lis[i-2])
 
print(lis[n])

の様に、入力された番目まで作っていくというのもありかと思います。(というよりこっちのが簡単)

C : Train Ticket

問題文

駅の待合室に座っている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 の部分を含めて出力せよ。
ただし、記号は半角で出力せよ。
また、数字と記号の間に空白を入れてはならない。

CとBの難易度逆じゃないですかね？っていう問題。

3重ループでOK

a, b, c, d = list(input())
sign = "+-"
for i in range(2):  # 1つ目の記号
    for j in range(2):  # 2つ目の記号
        for k in range(2):  # 3つ目の記号
            if eval(a+sign[i]+b+sign[j]+c+sign[k]+d) == 7:
                print(str(a+sign[i]+b+sign[j]+c+sign[k]+d)+"=7")

forでそれぞれの記号が+の時と-の時を示しています。

eval()　では、その引数がpythonの構文的に問題ないとき、それを実行します。eval()をしなければおかしなことになってしまいます。

あるいは、

a, b, c, d = list(map(int, list(input())))
if a + b + c + d == 7:
    print("{0}+{1}+{2}+{3}=7".format(a, b, c, d))
elif a + b + c - d == 7:
    print("{0}+{1}+{2}-{3}=7".format(a, b, c, d))
elif a + b - c + d == 7:
    print("{0}+{1}-{2}+{3}=7".format(a, b, c, d))
elif a - b + c + d == 7:
    print("{0}-{1}+{2}+{3}=7".format(a, b, c, d))
elif a - b - c + d == 7:
    print("{0}-{1}-{2}+{3}=7".format(a, b, c, d))
elif a - b + c - d == 7:
    print("{0}-{1}+{2}-{3}=7".format(a, b, c, d))
elif a + b - c - d == 7:
    print("{0}+{1}-{2}-{3}=7".format(a, b, c, d))
elif a - b - c - d == 7:
    print("{0}-{1}-{2}-{3}=7".format(a, b, c, d))

というようなごり押しも可能です。私は案外こういうのも好きです。

D : Wall

問題文

魔法少女のjoisinoお姉ちゃんは、この世にあるすべての数字を 1 に変えてやろうと思い立ちました。
1 つの数字を i から j(0≦i,j≦9) に書き変えるには魔力 ci,j が必要です。
今、目の前にある壁は縦方向に H、横方向に W のマス目になっていて、1 つ以上のマス目に 0 以上 9 以下の整数が 1 つずつ書かれています。
上から i(1≦i≦H) 番目、左から j(1≦j≦W) 番目のマスの情報として Ai,j が与えられ、
Ai,j≠−1 の場合はマスに Ai,j が書かれている
Ai,j=−1 の場合はマスに数字が書かれていない
ことを意味します。
この壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小量を求めてください。

制約

1≦H,W≦200

1≦ci,j≦103(i≠j)

ci,j=0(i=j)

−1≦Ai,j≦9

入力は整数からなる

壁には一つ以上の整数が書かれている

入力

入力は以下の形式で標準入力から与えられる。
H W
c0,0 … c0,9
:
c9,0 … c9,9
A1,1 … A1,W
:
AH,1 … AH,W

出力

壁に書かれている数字を最終的に全て 1 に変えるのに必要な魔力の最小量を出力せよ。

ワーシャルフロイドと呼ばれる、二点間の最短距離(今回でいえば0~9の数から1までの最小消費魔力)を求めるような問題です。

h, w = list(map(int, input().split()))  #サイズ読み取り
power = [list(map(int, input().split())) for i in range(10)]  #魔力読み取り

for i in range(10):
    for j in range(10):
        for k in range(10):
            power[j][k] = min(power[j][i] + power[i][k], power[j][k])  # 三重ループで各数間の最小魔力を求める。

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  # 壁読み取り
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  # それぞれの壁に使う魔力を求める
print(ans)

聞いてしまうと、何だ、そんなことか。という感じですよね。

話をするとすれば、三重ループについてでしょうか。

三重ループでは、二数間の最小魔力消費量を「その純粋な数と、別の数を挟む(3数間)の魔力消費量のうち小さいもの」としています。
これをすべての数に対して行うことで最小を導き出すことができます。