PythonでAtCoder Beginner Contest 080 ABC080

AtCoder Beginner Contest 080 ABC080

2017/12/03 21:00 ～ 22:40の問題でした。

簡単に説明すると

A：計算問題

B：型変換多用

C：bin換算

D：重複計算

となります。

A : Parking

問題文

駐車場があり、以下の二種類のプランのどちらかを選んで駐車できます。

• プラン 1 : T 時間駐車した場合、 A×T 円が駐車料金となる。
• プラン 2 : 駐車した時間に関わらず B 円が駐車料金となる。

N 時間駐車するとき、駐車料金は最小でいくらになるか求めてください。

制約

• 1≦N≦20
• 1≦A≦100
• 1≦B≦2000
• 入力は全て整数

入力

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

出力

駐車料金が最小で x 円のとき、x を出力せよ。

n, a, b = map(int, input().split())  # 入力
print(min(n*a, b))

N×AとBの小さいほうを返します。

B : Harshad Number

問題文

整数 X を十進法で表したときの各桁の数字の和を f(X) としたとき、X が f(X) で割り切れる場合、X はハーシャッド数です。
整数 N が与えられるので、ハーシャッド数かどうか判定してください。

制約

• 1≦N≦108
• 入力は全て整数

入力

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

出力

NN がハージャッド数ならば Yes を、そうでなければ No を出力せよ。

n = input()  # 入力
a = int(n)  # 数に変換
b = sum(map(int, list(n)))  # 各桁の合計
if a % b  == 0:
    print("Yes")
else:
    print("No")

b = sum(map(int, list(n)))　とすることで、map関数でnを数に変換し、sumを実行しています。map関数に関してはこちらで。
delta114514.hatenablog.jp

C : Shopping Street

問題文

joisinoお姉ちゃんは、ある商店街に店を開こうとしています。

その商店街の店は、月曜日から金曜日の 5 つの曜日を午前と午後の 2 つの時間帯に分けて、これら 10 個の時間帯それぞれについて店を営業するか否かを決めることとなっています。ただし、1 つ以上の時間帯で店を営業しなければなりません。
商店街には既に N 個の店があり、1 から N までの番号がついています。
これらの店の営業時間の情報として Fi,j,k が与えられ、月曜日＝曜日1、火曜日＝曜日 2、水曜日＝曜日 3、木曜日＝曜日 4、金曜日 ＝曜日5、 午前=時間帯1、午後=時間帯 2 と対応させたとき、Fi,j,k=1 なら曜日 j の時間帯 k に店 i が営業しており、Fi,j,k=0 なら営業していないことを意味します。

店 i とjoisinoお姉ちゃんの開く店の両方が営業している時間帯の個数を ci としたとき、joisinoお姉ちゃんの店の利益は P1,c1+P2,c2+...+PN,cN となります。ただし、利益は負にもなりうることに注意してください。
1 つ以上の時間帯で店を営業しなければならないことに注意しつつ、
10 個の時間帯それぞれについて店を営業するか否かを決めるとき、joisinoお姉ちゃんの店の利益のあり得る最大値を求めてください。

制約

• 1≦N≦100
• 0≦Fi,j,k≦1
• 1≦i≦N を満たす全ての整数 i に対して、Fi,j,k=1 を満たす (j,k) が必ず 1 つ以上存在する
• −107≦Pi,j≦107
• 入力は全て整数

入力

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

• N
• F1,1,1 F1,1,2 ... F1,5,1 F1,5,2
• FN,1,1 FN,1,2 ... FN,5,1 FN,5,2
• P1,0 ... P1,10
• PN,0 PN,10

出力

joisinoお姉ちゃんの店の利益のあり得る最大値が x のとき、x を出力せよ。

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
arm = [list(map(int, input().split())) for j in range(n)]  # 入力

ans = -9999999999  # 最小
for item in range(1, 1024):  # 2 ** 10 == 1024
    fund = 0
    for i in range(n):  # 店の数
        cou = 0  # かぶる数
        for x in range(10):  # 月-金(5) * 2
            if (item >> x) % 2 == 1 and arr[i][x] == 1:  # その時間で被るかどうか
                cou += 1
        fund += arm[i][cou]
    ans = max(ans, fund)  # 最大値更新

print(ans)

エラーの鬼ですね。

10重ループでも良いのですが汚いですし、そういうのはやりたくありません。

ところで、10重ループで各々2回回すとすると何回回すことになるのでしょうか。

1024回ですよね。 2 ** 10です。

なので、今回は10重ループの代わりにfor文を1024回回しています。

恐らく、この問題がわからない人は

(item >> x) についてわからないのだと思います。 ">>"　は右ビットシフトです。
ビットですので、1ビットシフトごとに / 2されていきます。nビットシフトすると、/ (2**n)となります。

D : Recording

問題文

joisinoお姉ちゃんは、録画機を用いて N 個のテレビ番組を録画しようとしています。
テレビが受信できるチャンネルは C 個あり、1 から C までの番号がついています。
joisinoお姉ちゃんの録画したいテレビ番組のうち、i 個目のテレビ番組は、時刻 si から時刻 ti まで、チャンネル ci で放送されます。(ただし時刻 si を含み、時刻 ti を除く)
ただし、同じチャンネルで複数のテレビ番組が同時に放送されることはありません。
また、録画機は、あるチャンネルの時刻 S から時刻 T までを録画するとき、時刻 S−0.5 から時刻 T までの間、他のチャンネルの録画に使うことができません。(ただし時刻 S−0.5を含み、時刻 T を除く)
N 個のテレビ番組の全ての放送内容が含まれるように録画するとき、必要な録画機の最小個数を求めてください。

制約

• 1≦N≦105
• 1≦C≦30
• 1≦si
• 1≦ci≦C
• ci=cj かつ i≠j ならば ti≦sj か si≧tj が成り立つ
• 入力は全て整数

入力

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

N C
s1 t1 c1
:
sN tN cN

出力

必要な録画機の最小個数が x 個のとき、 x を出力せよ。

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

r = [[0 for i in range(c)] for j in range(100000)]  # テレビ局の番組表
for dummy in range(n):  # 入力
    s, t, c = map(int, input().split())
    for j in range(s - 1, t):
        r[j][c - 1] = 1  # 放送中なら1

ans = 0
for i in range(100000):
    if sum(r[i]) > ans:
        ans = sum(r[i])  # 同時に放送されている番組の最大数

print(ans)

簡単ですよね。

CとDの難易度逆なんじゃないでしょうか…？

同時に放送されている最大数を求めるだけです。

分からないことがあれば気軽にコメントしてくださいね。じゃあな！

プログラミング(競プロ)に便利な Python3 用法集 ~出力編~

---

単純出力: print(n)

一番簡素な出力です。

n = "114514"
print(n)  # 114514

ぱっと見ではprintされるものが文字列なのか数なのか分かりませんが、

n = "114514"
print(n * 2)  # 114514114514

となり、"229028"とは表示されません。

そうしたいのであれば、int(n)　としてみましょう

n = "114514"
print(int(n) * 2)  #229028

int()で囲ってやることで、nを数と認識して計算してくれます。

---

変数間の文字を指定: print("".join(list))

出力するものの間に表示するものを変えてくれます。

n = ["114514", "810", "893"]
print(n)  # ['114514', '810', '893']
print("ｱｯｰ".join(n))  # 114514ｱｯｰ810ｱｯｰ893

リストを出力したいときに、[] や "" は出力したくない…というときにも使えます。

n = ["114514", "810", "893"]
print("".join(n))  # 114514810893
print(" ".join(n))  # 114514 810 893

---

文字列に変数を挟み込む: print("{0}+{1}={2}".format("3", "4", "7"))

本来例えば、a + b = 7というのを表示しようとすると

a, b, c = 3, 4, 7
print(str(a) + " + " + str(b) + " = " + str(c))  # 3 + 4 = 7

というようにしなければなりません。ですが、format関数を使えば

a, b, c = 3, 4, 7 
print("{0} + {1} = {2}".format(a, b, c))  # 3 + 4 = 7

とできます。format()内のn番目の数が{}内の数に対応しています。リストや文字列等を代入することも可能です。

数ですので計算にも使えます。

---

最終文字決定: print(n, end="")

pythonでは、print()の後には必ず改行が入ります。それを別のものに変えます。

n, m = 114514, 810
print(n)
print(m)
print(n, end="")
print(m)
print(n, end="ｱｯｰ")
"""
出力
114514  改行が入っている
810
114514810
114514ｱｯｰ
"""

ある意味、通常のprint()はprint(n, end="\n")であるとも言えますね。

PythonでAtCoder Beginner Contest 079 ABC079

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数間)の魔力消費量のうち小さいもの」としています。
これをすべての数に対して行うことで最小を導き出すことができます。

Python3 ~split関数について~

競技プログラミング（あるいはそれ以外でも）で使わない問題はないのではないと思うほど使用頻度の高いsplit()ですが、それを高度な使用をしようとしてできる人はあまり多くないのではないでしょうか。今回は、そんな愛されながらも謎に包まれたsplit()について解説します。

よくある使い方

たとえば、
AtCoder Beginner Contest030_AA - 勝率計算

問題文

野球のAtCoderリーグのシーズンが終了しました。チーム高橋は A試合中 B 回勝ち、チーム青木は C 試合中 D回勝ちました。AtCoderリーグでは勝率の高い順に高い順位が与えられます。チーム高橋とチーム青木のどちらが勝率で勝っているか答えるプログラムを作成してください。

入力

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

A B C D
1行目には、4 つの整数 A,B,C,D(1≦A,B,C,D≦100)が与えられる。
B ≦ A かつ D ≦ C を満たすことが保証される。

出力

チーム高橋の勝率がより高いときは TAKAHASHI、チーム青木の勝率がより高いときは AOKI、両チームの勝率が等しいときは DRAW と 1 行に出力せよ。出力の末尾にも改行をいれること。

などでは、入力にsplit()をつかうべきですよね。A, B, C, Dそれぞれがn桁だと明示されていれば入力そのものを文字列だと受け取り、インデックスの指定で計算してやることもできますが、今回は１から３桁まで開きがあるので（できないとは言いませんが）やるべきではありません。

ここで役に立つのがsplit()です。

引数(split(*)の*の部分)を指定せずに使ってやると、スペース区切りでリストに入れてくれます。

n = input().split()  #114 514 810 931
print(n)  # ['114', '514', '810', '931']

区切り文字を指定して区切る

引数の中に文字（列）を入れてやると、それを区切りとしてリストを作ってくれます。

n = input().split("アッー")  # 114アッー514アッー810アッー931
print(n)  # ['114', '514', '810', '931']

arrgh = "アッー"
n = input().split(arrgh)  # 114アッー514アッー810アッー931
print(n)  # ['114', '514', '810', '931']

区切り回数を指定する

第二引数に数を指定してやると回数指定ができます。

はじめの一回だけ区切りたい...あるいは、最後の一回だけ区切りたい、と言った時に使えます。

n = input().split("アッー", 1)  # 114アッー514アッー810アッー931
print(n)  # ['114', '514アッー810アッー931']

あるいは、split()をrsplit()に変えてやることで、反対から区切ってくれます。

n = input().rsplit("アッー", 1)  # 114アッー514アッー810アッー931
print(n)  # ['114アッー514アッー810', '931']

すでにある文字列・リストを区切ってリストにする

すでに存在している文字列に後置で実行してやることによって、リストを作成することもできます。

n = "114 514 810 931"
n = n.split()
print(n)  # ['114', '514', '810', '931']

リストにsplit()は使えません。ので、一度文字列に直してやります。

n = ['114 514 810 931', '893 889464']
n = ' '.join(n).split()
print(n)  # ['114', '514', '810', '931', '893', '889464']
"""※str(n)では
['114 514 810 931', '893 889464']
というように中括弧やアポストフィーも出力されるので
' '.join(n)とし、nの要素間に' '(スペース)を挟んで出力する
114 514 810 931 893 889464
とする。
"""

とできます。

簡単な部分のみを解説しましたが、非常に便利な関数なので、ぜひ使ってみてください。

よいPythonLifeを！

Python3 ~map関数について~

今回は map()関数 についてお話します。

簡単に言うと、リストやタプルなどのシーケンスに対してmap(a, b) はbに対してaしたものを返す。ということです。

たとえば

def double(n):
    return (int(n) * 2)
lis = ["114514", "810", "893"]
print(list(map(double, lis)))  # [229028, 1620, 1786]

というように、全ての要素を引数として読み込みそれぞれ"114514", "810", "893"に対して ×２をして返します。

分岐・ループ

lis = ["1024", "23", "16", "256", "1", "32"]
def beautify(n):
    m = format(int(n), "b")
    if m == "1" + "0" * (len(m) - 1) and n != "1":
        return n
    else:
        return '1024'  # 2の累乗数ならそのままreturnし、そうでないなら最も美しい数をreturnする。
print(list(map(beautify, lis)))  # ['1024', '1024', '16', '256', '1024', '32']

というように、分岐やループが入っているようなものも可能です。

lambda式

あるいはlambda式も使えますので

lis = ["114514", "810", "893"]
print(list(map(lambda n:int(n)*2, lis)))  # [229028, 1620, 1786]

というようにも扱えます。

ですが、map関数を使おうとしてできることは、大方リスト内包表記も使えます。そちらのほうがほとんどの場合高速なので、リスト内包表記を使うほうが良いと個人的に思います。

lis = ["114514", "810", "893"]
print([int(n) * 2 for n in lis])  # [229028, 1620, 1786]

ちなみに、このmap関数が返すのはmap型です。これ自体を直接見ることはできないので、毎回list()としてリストに変換しています。

プログラミング(競プロ)に便利な Python3 用法集 ~入力編~

---

単純入力: n = input()

一番簡素な入力だと思います

n = input()  # 114514
print(n)  # 114514

大切なことですがこのとき、nの中に入っているのは数としての“114514”ではなく、文字列(str)としての“114514”です。ですので、

n = input()  # 114514
print(n * 2)  # 114514114514

となり、"229028"と表示されるわけではありません。

---

単純入力~数~: n = int(input())

恐らく最も使用頻度の高いものではないでしょうか。

n = int(input())  # 114514
print(n * 2)  #229028

しっかりと数だと認識してくれます。

input()を後でintに直すよりもよほどスマートですね。必須技能です。

---

リスト入力: n= input().split()

入力をスペース区切りでリストにしてくれます。

n = input()  # 114514 810 893
print(n)  # 114514 810 893

こちらも先ほどの例にもれずすべて文字(str)カウントです。

n = input().split()  # 114514 810 893
print(sum(n))   # 114514810893

---

リスト入力~数~: n = list(map(int, input().split()))

こちらは入力をスペース区切りで数としてリストにしてくれます。

n = list(map(int, input().split()))  # 114514 810 893
print(n)  # [114514, 810, 893]

数ですので計算にも使えます。

map関数については
Python3 ~map関数について~ - やるだけPython競プロ日誌
を参照ください。

n = list(map(int, input().split()))  # 114514 810 893
print(sum(n))  # 116217

---

分割入力: n, m = input().split()

重要なのは、input().split()　というのは特別な関数でもなんでもなく、ただリストを返すだけだという点です。

ですのでこれは、input()split()という名前のリストがあり、その一つ一つのインデックスにn, mが対応しているという見方もできます。

n, m = input().split()  # 114514 810
print(n + m)  # 114514810

当然

n, m = list(map(int, input().split()))  # map(int, input().split())でも同じ

とすれば

n, m = list(map(int, input().split()))  # 114514 810
print(n + m)  # 115324

となります。

---

一部を一つに、残りをそれ以外に: n, *m = input().split()

変数名に "*"を先付けすることによって、あふれ出る要素をそこに入れることができます。

n, *m = input().split()  # 114514 810 893 364
print(n, m)   # 114514 ['810', '893', '364']

*n, m = input().split()  # 114514 810 893 364
print(n, m)  # ['114514', '810', '893'] 364

n, *m, l = input().split()
print(n, m, l)  # 114514 ['810', '893'] 364

---

リスト入力~改行~: for i in range(times): n.append(input())

複数行の入力をすべて一つのリストに入れ込みます。

times = int(input())  # 3
n = []
for i in range(times):
    n.append(input())
    """
    114514
    810
    893
    """
print(n)  # ['114514', '810', '893']

n.append(int(input()))

とすれば数扱いになりますので

times = int(input())  # 3
n = []
for i in range(times):
    n.append(int(input()))
    """
    114514
    810
    893
    """
print(sum(n))  # 116217

となります。

---

リスト入力~リスト内包表記~: n = [input() for i in range(times)]

こちらのほうが上のappendを使った方法よりも2倍ほど高速です。さらにコードも短くなりますし、可読性も高まります。

times = int(input())  #3
n = [input() for i in range(times)]
"""
114514
810
893
"""
print(n)  # ['114514', '810', '893']

しつこいですが、

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

として

times = int(input())  #3
n = [int(input()) for i in range(times)]
"""
114514
810
893
"""
print(sum(n))  # 116217

とできます。

---

複数行に複数のデータ: for i in range(times): n.append(input().split())

times 回分だけ、nに input().split() を append します。なので、n は二次元配列になります。

times = int(input())  # 3
n = []
for i in range(times):
    n.append(input().split())
    """
    114514 810
    931 893
    364 364
    """
print(n)  #[['114514', '810'], ['931', '893'], ['364', '364']]

あるいは例のごとく

n.append(list(map(int, input().split()))) 

とすることで

times = int(input())  # 3
n = []
for i in range(times):
    n.append(list(map(int, input().split())))
    """
    114514 810
    931 893
    364 364
    """
print(n, sum(n[0]))  # [[114514, 810], [931, 893], [364, 364]] 115324

ともできます。

---

複数行に複数のデータ~リスト内包表記~: n = [input().split() for i in range(times)]

できることは上のものと同じですが、こちらのほうが高速です。

times = int(input())  # 3
n = [input().split() for i in range(times)]
"""
114514 810
931 893
364 364
"""
print(n)  # [['114514', '810'], ['931', '893'], ['364', '364']]

intで読み込みます。

times = int(input())  # 3
n = [list(map(int, input().split())) for i in range(times)]
"""
114514 810
931 893
364 364
"""
print(n, sum(n[0]))  # [[114514, 810], [931, 893], [364, 364]] 115324

---

いつデータ入力が終わるかわからない複数行にわたる入力 : except EOFError: break

EOFError は『End Of File Error』のことで、ファイルの読み込める物はもうない(入力がない)のに読み込みを続けようとしたときに出るエラーです。なので、読み込みが終わったときに辞める、ということになります。

n = []
while True:
    try:
        n.append(input().split())
    except EOFError:
        break
    """
    114514
    810
    893
    """
print(n)  # [['114514'], ['810'], ['893']]

PythonでAtCoder Beginner Contest 078 ABC078

AtCoder Beginner Contest 078 ABC078

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

簡単に説明すると

A：文字同士の順序を求める

B：植木算（小学校でやるやつ）

C：回数としての期待値の算出

D：max計算でOK

となります。

---

A：HEX

問題文

プログラミングでは 16進数がよく使われます。
16進数では 0,1,...,9 の数字の他に A, B, C, D, E, F の 6 つのアルファベットを使い，それぞれ 10,11,12,13,14,15を表します。
この問題では 2つのアルファベット X,Y が与えられます。 X と Yはどちらも A, B, C, D, E, F のうちどれかです。
Xと Y を 16進数として見たとき，どちらのほうが大きいかを判定してください。

制約

• X,Yは A, B, C, D, E, F のうちどれかである。

入力

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

出力

Xのほうが小さいならば <，Y のほうが小さいならば >，等しいならば = と出力してください。

一般的な（というより素直な）解でいうと

---

alpha = ("A", "B", "C", "D" ,"E", "F")  # 文字の順番を決める
a = input().split()  # 入力をリストにして受け取る
if a[0] == a[1]:  # 入力が二文字とも同じなら
　　　　print("=")  # "=" を出力
elif alpha.index(a[0]) < alpha.index(a[1]):  # 二文字目のほうが順番が後なら
　　　　print("<")  # "<" を出力
else:  #>>3 >>5　# どちらでもない（一文字目のほうが順番が後）なら
　　　　print(">")  # ">" を出力

---

となりますかね。

(リスト名).index(要素)　は要素の位置を返してくれます。

あるいは、文字にも順番がある（あります）ので、

---

a, b = input().split()  # 入力を受け取る
if a == b:  # 入力が二文字とも同じなら
　　　　print("=")  # "=" を出力
elif a < b:  # 二文字目のほうが順番が後なら
　　　　print("<")  #"<" を出力
else:  # >>2 >>4どちらでもない（一文字目のほうが順番が後）なら
　　　　print(">")  # ">" を出力

---

というように、文字そのもののサイズを比べることで順番を比べることになります。

---

B：ISU

問題文

幅 Xセンチメートルの椅子があります。 この椅子に座りたい人がたくさんおり，人は椅子に座ると必ず Yセンチメートルの幅を使って座ります。
出来る限りたくさんの人を椅子に座らせたいですが， 人はみなシャイなので，人と人の間，また椅子の端と人の間には， 少なくとも Zセンチメートル間を開ける必要があります。
最大で何人座ることができますか？

制約

• 入力は全て整数
• 1≤X,Y,Z≤105
• Y+2Z≤X

入力

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

出力

求めた答えを出力してください。

植木算ですね。植木算。それです。小学校でやった。あれ。

---

a, b, c = list(map(int, input().split()))  # 入力の受け取り
print( (a - c) // (b + c) )  # 計算

---

あまり植木算の説明というのはやりたくないんですが・・・・一応やります。

入力例１でいえば、椅子の幅が13、一人3マス、脇に1マス必要ということですので

◆◆◆◆◆◆◆◆◆◆◆◆◆　　横13マス

＃人人人＃人人人＃人人人＃

ということですよね。分けて考えてみると

『＃人人人』　×　３　＋　『＃』

っていう見方もできます。

なので、

(a - c) // (b + c)   ==  (　椅子の長さ　－　右端の『＃』)　÷　（『＃人人人』の長さ）

となります。

 

 

---

C:HSI

問題文

高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。
提出の詳細を見ると，テストケースは全てで Nケースあり，そのうち MケースでTLEしていました。
そこで高橋くんは, Mケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し， 残りの N−M ケースではそれぞれ実行に 100ms かかって必ず正解するプログラムへ書き換えました。
そして，以下の操作を行います。

• このプログラムを提出する。
• 全てのケースの実行が終わるまで待機する。
• もし Mケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。

これを，一度で全てのケースに正解するまで繰り返す。
この操作が終了するまでの，プログラムの実行時間の総和の期待値を Xmsとした時，Xを出力してください。
なお，Xは整数で出力してください。

制約

• 入力は全て整数
• 1≤N≤100
• 1≤M≤min(N,5)

入力

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

出力

実行時間の総和の期待値 Xを整数で出力してください。 なお，X はこの問題の制約下で，109 以下の整数となることが証明できます。

 

これには少し悩みました。

 

Σ計算とか使うのかな・・・なんて悩んでいましたが、大切なことを思い出しました。

 

期待値は、確率の逆数です。なので

 

---

a, b = list(map(int, input().split()))  # 入力の受け取り
print( (b * 1900 + (a - b) * 100) * 2 ** a)  # 計算

---

となります。

 

ええ、この二行だけです。

 

解説をしますね。

 

 

これは、二つの部分に分けて考えるとわかりやすいと思います。

 

(b * 1900 + (a - b) * 100) 

と

(上式)* 2 ** a

 

です。

 

まずは上段。

 

これは、一回あたりの計算時間です。そのままですね。

 

次の下段ですが、そのまえに考えてほしい問題があります。

 

裏と表、それぞれ出る確率が同様に確からしいコインがn枚あったとし、

このコインのすべてが表が出るまで同時に投げ続けたとする。

投げる回数の期待値はいくらか？

 

答えは、2^n となります。

 

コインが1つなら2回、2つなら4回、3つなら8回といった具合です。

 

これを変形し、

 

裏と表、それぞれ出る確率が同様に確からしく、なおかつ1枚投げるのに1900ms掛かるコインがn枚あったとし、必ず表が出て、かつ1枚投げるのに100ms掛かるコインがm枚あったとする。

このコインのすべてが表が出るまで1枚ずつ投げ続けたとする。

かかる時間のの期待値はいくらか？

※ただしコインを投げている途中に裏が出ても最後まで投げつづけるものとする。

 

これの答えを言うと

 

(1900 × n + 100 × m) × 2 ^ n

 

です。

 

一回の試行時間　×　回数の期待値です。

 

これを今回のC問題に合わせてみると

 

(b * 1900 + (a - b) * 100) * 2 ** a

 

となりますよね。これが答えです。

---

D:ABS

問題文

N枚のカードからなる山札があります。カードにはそれぞれ数が書かれており， 上から i 枚目には aiが書かれています。
この山札を使い，X さんと Y さんが 2人でゲームをします。 X, Y さんは最初，Z,Wが書かれたカードを持っています。 そして X さんから交互に以下を行います。

• 山札から何枚かカードを引く。そして今持っているカードを捨て，最後に引いたカードを代わりに持つ。ただし，必ず 1
• 枚は引かなくてはならない。

山札がなくなるとゲームは終了で，2人の持っているカードに書かれた数の差の絶対値がこのゲームのスコアになります。
X さんはスコアを最大化するように，Y さんはスコアを最小化するようにゲームをプレイした時， スコアはいくつになるでしょうか？

制約

• 入力は全て整数
• 1≤N≤2000
• 1≤Z,W,ai≤109

入力

入力は以下の形式で標準入力から与えられる。
N Z W
a1 a2 ... aN

出力

求めたスコアを出力してください。

D問題にしては簡単でした。

コードはこちらになります

---

a = list(map(int, input().split()))  # 入力をリストにして受け付け
b = list(map(int, input().split()))
try:
    print(max(abs(a[2] - b[-1]), abs(b[-1] - b[-2]))) # xさんが最後から二番目の数か最後の数どちらを取ればよいかを判断
except:  # 与えられる数が一つの場合
    print(abs(a[2] - b[0]))

---

です。

なぜこれだけでよいのか？というのは、思考力の問題になります。地頭の範疇です。

xさんがどれだけ頑張っても、最後から3番目以前の数を取ってしまえば、yさんができるだけ小さい数を取らせようとしてきます。

つまり、yさんに選択の余地を与えてはいけないのです。となると

1. yさんの取れるカードを1つだけにする(xさんが最後から2枚目までを取る)
2. そもそもyさんに取らせない

のどちらかですね。

4行目のコードで、1と2を試し、どちらのほうが絶対値が大きいかを試しています。

5‐6行目のコードですが、4行目のコードでは、もしカードが一枚しか与えられなかった場合(b[-2])がリストの範囲を超えますのでエラーが出ます。

そのエラーが出た場合、無条件でその唯一のカードとyのカードの差の絶対値をprintする。となっています。

今回のABCは比較的簡単だったと感じています。

皆様の中にも、いつもよりいけた。だとか、いけそうだった！という方が大勢いらっしゃると思います。

このまま努力を続け、Pythonistaの皆様、良いPythonLifeをお送りください！