PythonでAtCoder Beginner Contest 080 ABC080 - やるだけPython競プロ日誌

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の難易度逆なんじゃないでしょうか…？

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

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