ABC216 (A〜C) Pythonで解く
ABC216 A〜C Python
A - Signed Difficulty
A 問題としては少しとっつきにくかったかもしれません。
x.y を素直に x と y で受け取ると良いでしょう。整数値のみの操作で済みます。競技プログラミングではこういうの大事です。float は極力避けるようにしておくのが無難でしょう。
Python では、空白区切りの入力は input().split() で受け取ることができますが、split('.')とすることでドット区切りになります。カンマやコロンなども使えますね。
x, y = input().split('.') y = int(y) if 0 <= y <= 2: print(x + '-') elif 3 <= y <= 6: print(x) else: print(x + '+')
B - Same Name
タプル
をリストに入れていき、二重ループの全探索で同じ要素があるか調べればよいでしょう。
という制約をチェックしましょう。
で通ります。
決して
と
をくっつけて一つの名前として管理してペナを出してはいけません。私です。
n = int(input()) list_ = [] for i in range(n): s, t = input().split() list_.append((s, t)) for i in range(n): for j in range(i+1, n): if list_[i] == list_[j]: print('Yes') exit() print('No')
C - Many Balls
先ほどまでより考察がいります。
と
が大きいので魔法 A ばかり使っているわけにはいかないだろうということがわかります。
最後の操作から逆に辿っていくことにします。例えば 14 なら偶数なら魔法 B を使って 7 → 14 と遷移できます。7は奇数なので、Bは無理。魔法 A を使い、6 → 7 と遷移できます。このように、偶数ならB, 奇数なら A と後ろから辿っていくことで最短の手順が見つかります（証明はしません）。
n = int(input()) ans = [] for i in range(120): if n < 1: break elif n % 2 == 1: n -= 1 ans.append('A') else: n //= 2 ans.append('B') ans = ''.join(reversed(ans)) print(ans)
お疲れ様でした。
ABC166 ( A 〜 D ) Python で解く
ABC166 Pythton
A - A?C
'ABC' と 'ARC' のどちらかが与えられるので、もう一方を出力すればよいです。
s = input() if s == 'ABC': ans = 'ARC' elif s == 'ARC': ans = 'ABC' print(ans)
B - Trick or Treat
Python のset( 集合 ) は競プロでもなかなか使えます。 集合は同じ要素を追加しても要素数が増えないので、数学やっている人には自然でしょうが、押さえておきましょう。
それぞれのお菓子について、そのお菓子をもらっている人すべてを用意した集合に放り込めば、1度でもお菓子をもらっている人はその集合にはいります。なので、そこに入っていない人数を数えて終わりです。
n, k = map(int, input().split()) s = set() for i in range(k): d = int(input()) a = list(map(int, input().split())) for j in a: s.add(j) print(n - len(s))
C - Peaks
この問題でも set を使いました。ぜひ押さえておきましょう。
ある道が結ぶ展望台のうち、標高の低い方の展望台は絶対良い展望台ではありません。良い展望台ではない set を作って入れておきましょう。逆に、すべての道についてこれをチェックして低い方にならなかった展望台は良い展望台です。このように実装しやすいように問題を読み替えるのが大切です。
n, m = map(int, input().split()) h = list(map(int, input().split())) false_set = set() for i in range(m): a, b = map(int, input().split()) a -= 1 b -= 1 if h[a] == h[b]: false_set.add(a) false_set.add(b) elif h[a] < h[b]: false_set.add(a) else: false_set.add(b) print(n-len(false_set))
D - I hate Factorization
X が 109 と大きいですが、びびってはいけません。A と B はともに5乗されるので、それぞれ1000までで全探索すれば十分です。公式の解説に詳しく書いてあります。
気をつけるべきポイントは、どちらかは負の数かもしれないということです。しかし、A5 + B5 = X を満たすものを探し、Bは-1倍すると、負の数は考えなくて良いことになります。
x = int(input()) for a in range(10**3): for b in range(10**3): if a**5 - b**5 == x: print(a, b) exit() if a**5 + b**5 == x: print(a, -b) exit()
ABC165 C Python で解く
ABC165 C Python
C - Many Requirements
少し難しめかもしれませんが、Python であれば itertools の combinations_with_replacement という関数を使うと、重複を含む組み合わせのシーケンスが作れます。
実装は、条件を満たすDの総和をリストに追加していき、最後に最大値をとって出力しました。数列 A を変えるごとに総和を毎回比較しても良いでしょう。
実装は↓のようになりました。
from itertools import combinations_with_replacement as cbw n, m, q = map(int, input().split()) lst = [list(map(int, input().split())) for _ in range(q)] ans = [] for seq in cbw(range(1,m+1), n): d_sum = 0 for i in range(q): a, b, c, d = lst[i] a -= 1 b -= 1 if seq[b]-seq[a] == c: d_sum += d ans.append(d_sum) ans = max(ans) print(ans)
ABC165 D Python で解く
ABC165 D
D - Floor Function
- これは数学ですかね。Nが大きいので当然全探索は間に合いません。
- 手を動かして実験すると良いと思います。入力例1 で n を大きくしてみると考えやすいかもしれません。
x を 1 ずつ大きくしていくと、x が B の倍数のときはそれぞれの分数がともに整数になり、全体は0になるのがわかります。また、x = B + 1
のときは
floor(Ax/B) = A + floor(A/B)
A × floor(x/B) =A + A × floor(1/B)
となり、全体は x = B のときの値と等しくなります。 これでB周期で繰り返すことに気付けるのではないでしょうか。
実装はすることがありません。
a, b, n = map(int, input().split()) x = min(b-1, n) ans = (a*x)//b - a*(x//b) print(ans)
ABC164 Python 解説 (A 〜 C）
ABC164 (A〜C)
A - Sheep and Wolves
if 文を書いて、羊の数と狼の数の大小を比較するだけです。 三項演算子（条件演算子）を使って書いています。
s, w = map(int, input().split()) print('unsafe' if w >= s else 'safe')
B - Battle
高橋君、青木君と交互に攻撃するので、青木君の体力を高橋君の攻撃力だけ減少させ、もし体力が0以下なら'Yes'を出力して終わらせます。次に高橋君についても同じようにし、これを繰り返せば良いです。
a, b, c, d = map(int, input().split()) while True: c -= b if c <= 0: print('Yes') exit() a -= d if a <= 0: print('No') exit()
C - gacha
Python ならこれはかなり簡単です。S_i を set（集合） にすると、同じ要素は一度しか出てこないので、set の要素数をカウントするだけで済みます。
n = int(input()) s = [] for i in range(n): s.append(input()) s = set(s) print(len(s))
ABC163 Pythonで参加
ABC163 (A〜C + D)
A - Circle Pond
これがIE（内部エラー）になってしまったんですよね。 Python では標準モジュール math に円周率が入っています。
import math print(int(input()) * math.pi * 2)
B - Homework
sum とif文が書ければ大丈夫です。
n, m = map(int, input().split()) A = list(map(int, input().split())) ans = sum(A) if ans > n: ans = -1 else: ans = n - ans print(ans)
C - management
A_i はリストとして受け取りました。それぞれの要素をカウントして出力すれば良いのですが、count メソッドを使うとO(N2)で間に合いません。各A_iに対してその数のカウントをで増やしていけばO(N)で大丈夫です。
N = int(input()) A = list(map(int, input().split())) cnt = [0] * N for i in A: cnt[i-1] += 1 for j in cnt: print(j)
[追記]
D - Sum of Large Numbers
考察ポイント
10100 + a の形の数の和を考える訳ですが、a の方は10100より十分小さいので、違う個数の和が等しくなることはありません。
i 個の和を考えるときその数のうち最大でないものを1増やすことで、合計が1増えます。よって、最小値と最大値の間の全ての数をとることができます。
実装は難しくないでしょう。
n, k = map(int, input().split()) def sum_count(x): return (2*n-x+1)*x//2 - x*(x-1)//2 + 1 ans = 0 for i in range(k, n+2): ans += sum_count(i) ans %= 10 ** 9 + 7 print(ans)
ABC161 Pythonで参加した
ABC161（A〜C）
初記事。競プロ初心者です。東工大というところで学生してます。
灰色コーダーですので、あまり参考にならないと思いますが、考えたことや感想など載せていきます。output だいじ。
まあ、競プロでPython使う人は増えているようだし、Pythonの記事はまだそこまで多くない気がするので、少しは意義もあるかな。
と言っても、コンテスト内でACしたのはCまでです。 残りは後日解けたら追記します。
Dはcodeは書けたけどTLE確実だったので、出しませんでした。復習しておきます。
A - ABC Swap
箱 A, B, C の中身を入れ替えるわけですが、x、y、zの移動は簡単に追えるので、z, x, yの順番になることに気づくだけです。
x, y, z = map(int, input().split()) print(z, x, y)
B - Popular Vote
A_i をリストとして持ち、各要素が(A_i の総和) / (4M) 以上かどうかを for ループでチェックしていきました。 シンプルですね。
n, m = map(int, input().split()) a = list(map(int, input().split())) popular = 0 for i in range(n): if a[i] >= sum(a) / (4 * m): popular += 1 print("Yes" if popular >= m else 'No')
C - Replacing Integer
これは少し数学力よりの問題でしょうか。 実装はめちゃ簡単です。 こういうのがすぐできたのはよかった。 絶対値とってるので少しわかりにくいかもしれませんが、結局 K を足したり引いたりした絶対値を最小にしたいので、とりあえず割り算すればいいと思います。
7 を 4 で割ったあまりは 3 ですが、これよりも |3-4|の方が小さいです（3 ≡ -1 (mod 4))。 kで割った余りは必ず0以上k未満の値として得られるので、そこからKを引いて絶対値とったもの、つまりkから余りを引いたものと比較して小さい方をとれば良いでしょう。
n, k = map(int, input().split()) ans = min(n % k, k - (n % k)) print(ans)
