AtCoder Beginner Contest 096
A - Day of Takahashi
各月に対して、高橋の日になる月の数と日の数との組み合わせは 通りずつです
月 日において、
- の場合、合計 日
- の場合、合計 日
となります
# coding: utf-8 a, b = [int(i) for i in input().split()] print(a - 1 if a > b else a)
B - Maximum Sum
を最大化するためには、 の中で最大の整数を 倍する操作を 回繰り返せば良いです
つまり、 で求めることができます
# coding: utf-8 a, b, c = [int(i) for i in input().split()] k = int(input()) print(a + b + c + max(a, b, c) * (2 ** k - 1))
C - Grid Repainting 2
#
のマスの上下左右に#
があるか判定すれば良いです
# coding: utf-8 h, w = [int(i) for i in input().split()] s = [list(input()) for _ in range(h)] flg = True for i in range(1, h - 1): for j in range(1, w - 1): # '#'のマスの上下左右に'#'がない場合、目標を達成することができない if s[i][j] == "#" and s[i - 1][j] == s[i + 1][j] == s[i][j - 1] == s[i][j + 1] == ".": flg = False print('Yes' if flg else 'No')
D - Five, Five Everywhere
で割って 余る素数を列挙すれば良く、これらの素数から 個選んだ合計は全て の倍数となります(つまり、合成数です)
# coding: utf-8 n = int(input()) ps = [] # 素数チェック def isPrime(target): for i in range(2, target): if target % i == 0: return False return True # 5で割って1余る数を55,555まで検証する for i in range(11, 55555, 5): # 素数の場合、数列に加える if isPrime(i): ps.append(i) # 数列の長さがNの場合、処理を抜ける if len(ps) == n: break print(*ps)
AtCoder Beginners Selection
今更ですが、AtCoder Beginners Selectionの問題を解きました。
PracticeA - はじめてのあっとこーだー(Welcome to AtCoder)
入出力の確認です。
C++
#include <iostream> using namespace std; int main() { int a, b, c; string s; cin >> a; cin >> b >> c; cin >> s; cout << (a + b + c) << " " << s << endl; return 0; }
Python
# coding: utf-8 a = int(input()) b, c = [int(i) for i in input().split()] s = input() print("{} {}".format(a + b + c, s))
Ruby
# coding: utf-8 a = gets.to_i b, c = gets.strip.split.map(&:to_i) s = gets puts "#{a + b + c} #{s}"
ABC086A - Product
倍数判定には%
を使えば良いです。
「2の倍数」ということは、「2で割った余りが0」ということです。
C++
#include <iostream> using namespace std; int a, b; int main() { cin >> a >> b; cout << (a * b % 2 == 0 ? "Even" : "Odd") << endl; return 0; }
Python
# coding: utf-8 a, b = [int(i) for i in input().split()] print('Odd' if a % 2 == b % 2 == 1 else 'Even')
Ruby
# coding: utf-8 a, b = gets.strip.split.map(&:to_i) puts (a * b).odd? ? 'Odd' : 'Even'
ABC081A - Placing Marbles
3桁の番号を文字列と考え、1文字目から順に'1'
か'0'
かを判定すれば良いです。
C++
#include <iostream> using namespace std; string s; int main() { cin >> s; int cnt = 0; for (int i = 0; i < 3; ++i) if (s[i] == '1') ++cnt; cout << cnt << endl; return 0; }
Python
入力文字列に対してlist()
を使用し、1文字ずつからなるリストに変換しています。
# coding: utf-8 print(sum([int(i) for i in list(input())]))
Ruby
split('')
を使用し空文字で分割することで、1文字ずつからなる配列に変換しています。
# coding: utf-8 ss = gets.strip.split('') puts ss.map(&:to_i).inject(:+)
ABC081B - Shift only
全てのA
の要素が偶数である限り、要素を2で割り、カウントを1加算する処理を繰り返します。
C++
#include <iostream> using namespace std; int n; int a[200]; int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; bool flg = true; // a[i]が偶数であるかどうかを判定するフラグ int cnt = 0; // 偶数がある限り処理を繰り返す while (flg) { // aの各要素に対して走査 for (int i = 0; i < n; ++i) { // 2の倍数でない場合 if (a[i] % 2 != 0) { flg = false; break; // 処理を抜ける } // 偶数である場合、要素を2で割る a[i] = a[i] / 2; } // 全てのaの要素が偶数であった場合 if (flg) ++cnt; } cout << cnt << endl; return 0; }
Python
all()
を使用し、a
の全要素が偶数であるかを判定しています。
# coding: utf-8 def count_div_by_2(nums): if all([num % 2 == 0 for num in nums]): return count_div_by_2([num / 2 for num in nums]) + 1 else: return 0 n = int(input()) a = [int(i) for i in input().split()] print(count_div_by_2(a))
Ruby
all?()
を使用し、a
の全要素が偶数であるかを判定しています。
# coding: utf-8 n = gets.to_i as = gets.strip.split.map(&:to_i) cnt = 0 # aの全要素が偶数である限り処理を繰り返す while as.all?(&:even?) do cnt = cnt.succ as = as.map { |a| a / 2 } end puts cnt
ABC087B - Coins
for
文で全探索を行います。
C++
#include <iostream> using namespace std; int a, b, c, x; int main() { cin >> a >> b >> c >> x; int cnt = 0; // 500円玉が0~a枚 for (int i = 0; i <= a; ++i) { // 100円玉が0~b枚 for (int j = 0; j <= b; ++j) { // 50円玉が0~c枚 for (int k = 0; k <= c; ++k) { // 合計金額がx円に等しい場合 if (500 * i + 100 * j + 50 * k == x) ++cnt; } } } cout << cnt << endl; return 0; }
Python
# coding: utf-8 a = int(input()) b = int(input()) c = int(input()) x = int(input()) ans = 0 for i in range(a + 1): for j in range(b + 1): for k in range(c + 1): if 500 * i + 100 * j + 50 * k == x: ans += 1 print(ans)
Ruby
# coding: utf-8 a, b, c, x = 4.times.map { gets.to_i } cnt = 0 (0..a).each do |i| (0..b).each do |j| (0..c).each do |k| cnt = cnt.succ if x == 500 * i + 100 * j + 50 * k end end end puts cnt
ABC083B - Some Sums
整数の各桁を計算していくには、以下の方法があります。
- 整数を1度文字列に変換し、1文字ずつ整数に再変換して計算します。
- 整数の1の位を10で割った余りで求めた後、整数を10で割ることで、桁数を1つ減らす(元の1の位を削る)処理を、整数が0になるまで繰り返します。
C++
#include <iostream> using namespace std; int n, a, b; // 各桁の和を計算する関数 int sumOfDigits(const int n) { // nが0の場合、処理を終了する (0を足す) if (n == 0) return 0; // nが0でない場合、1の位の数字を抽出し、残りの桁を抽出した結果に足す return n % 10 + sumOfDigits(n / 10); } int main() { cin >> n >> a >> b; int total = 0; // 1からnまで繰り返す for (int i = 1; i <= n; ++i) { // 各桁の和 int target = sumOfDigits(i); // 各桁の和がa以上b以下である場合 if (a <= target && target <= b) total += i; } cout << total << endl; return 0; }
Python
# coding: utf-8 n, a, b = [int(i) for i in input().split()] total = 0 for i in range(n + 1): # 整数を1度1文字ずつからなるリストに変換し、各桁を数字に再変換して合計する # その合計がa以上b以下である場合、合計を累計していく if a <= sum([int(c) for c in list(str(i))]) <= b: total += i print(total)
Ruby
各桁を1度文字列に変換した後、整数に再変換し、inject
で各桁の和を計算しています。
select
を使用し、各桁の和がa
以上b
以下のものだけを選択し、これにinject
を使用し合計しています。
# coding: utf-8 n, a, b = gets.strip.split.map(&:to_i) puts 1.upto(n).select { |i| i.to_s.split('').map(&:to_i).inject(:+).between?(a, b) }.inject(:+)
ABC088B - Card Game for Two
自分の得点を最大化するためには、カードに書かれている数が大きいものから順にカードを取得すれば良いです。
降順にソートすることで、交互にカードを取得するということを、インデックスを2で割った余りで表現することができます。
つまり、
- カードの数を配列(リスト)に設定します。
- これを降順にソートします。
- 配列(リスト)のインデックスが偶数の全要素の合計と、奇数の全要素の合計との差で、二人の得点差を求めます。
と処理することで、解を求めることができます。
C++
#include <iostream> #include <algorithm> using namespace std; int n; int a[100]; int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; int score = 0; // 降順にソートする sort(a, a + n, greater<int>()); for (int i = 0; i < n; ++i) { // インデックスが偶数の場合、その要素を得点に加算し、奇数の場合は得点から減算する score += (i % 2 == 0) ? a[i] : -a[i]; } cout << score << endl; return 0; }
Python
a[::2]
で、a
の要素を0番目から2stepで(偶数番号のみ)取得します。
a[1::2]
で、a
の要素を1番目から2stepで(奇数番号のみ)取得します。
# coding: utf-8 n = int(input()) a = sorted([int(i) for i in input().split()])[::-1] # 降順にソート print(sum(a[::2]) - sum(a[1::2]))
Ruby
each_slice(2)
で配列から2個要素を要素を繰り返し取得しています。
取り出した要素の個数が1つの場合はそれ自身を、2個の場合はその差を取得し、それらを合計しています。
# coding: utf-8 n = gets.to_i as = gets.strip.split.map(&:to_i).sort.reverse # 降順にソート puts as.each_slice(2).map { |a| a.size == 1 ? a[0] : a[0] - a[1] }.inject(:+)
ABC085B - Kagami Mochi
重複を取り除いた集合を作成する関数を使用すれば良いです。
C++
餅をソートして、直前の餅と比較することで、重複を判定しています。
#include <iostream> #include <algorithm> using namespace std; int n; int d[100]; int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> d[i]; int count = 1; // 1段目は必ず存在する sort(d, d + n); // 2枚目から検証を開始する(1段目には直前が存在しないため) for (int i = 1; i < n; ++i) { // 直前の餅と違う大きさの場合、段数が増える if (d[i - 1] != d[i]) ++count; } cout << count << endl; return 0; }
Python
set()
を使用し、重複した要素のない集合を取得します。
# coding: utf-8 n = int(input()) d = [int(input()) for _ in range(n)] # 重複した要素のない集合の要素数を出力する print(len(set(d)))
Ruby
uniq
を使用し、配列の中で重複する要素を削除した新しい配列を取得します。
# coding: utf-8 n = gets.to_i d = n.times.map { gets.to_i } # 重複した要素のない配列の要素数を出力する puts d.uniq.size
ABC085C - Otoshidama
1,000円札の枚数は、10,000円札の枚数と5,000円札の枚数により確定します。
C++
#include <iostream> using namespace std; int n, yen; int main() { cin >> n >> yen; int x = -1, y = -1, z = -1; // 組み合わせが見つからなかった場合の出力を事前に設定 // 10,000円札の枚数 for (int i = 0; i <= n; ++i) { // 5,000円札の枚数 for (int j = 0; j <= n - i; ++j) { // お年玉の金額が一致した場合 if (yen == 10000 * i + 5000 * j + 1000 * (n - i - j)) { // 組み合わせを更新 x = i; y = j; z = n - i - j; } } } cout << x << " " << y << " " << z << endl; return 0; }
Python
# coding: utf-8 n, yen = [int(i) for i in input().split()] ans = [-1, -1, -1] for x in range(n + 1): if 10000 * x > yen: break for y in range(n - x + 1): z = n - x - y total = 10000 * x + 5000 * y + 1000 * z if total > yen: break if total == yen: ans = [x, y, z] break print(*ans)
Ruby
# coding: utf-8 n, yen = gets.strip.split.map(&:to_i) a, b, c = -1, -1, -1 0.upto(n) do |x| 0.upto(n - x) do |y| if yen == 10000 * x + 5000 * y + 1000 * (n - x - y) a, b, c = x, y, n - x - y break end end end puts "#{a} #{b} #{c}"
ABC049C - 白昼夢 / Daydream
er
が単語の先頭のer
であるのか、末尾のer
であるのかの判定が難しいです。
そこで、S
を後ろから順に判定します。
C++
#include <iostream> #include <string> #include <algorithm> using namespace std; const int D_SIZE = 4; string d[D_SIZE] = {"dream", "dreamer", "erase", "eraser"}; string s; string t; int main() { cin >> s; reverse(s.begin(), s.end()); // 文字列をすべて左右反転する for (int i = 0; i < D_SIZE; ++i) reverse(d[i].begin(), d[i].end()); // ループ継続のフラグ bool flg; do { // ループフラグをfalseで初期化 flg = false; // 'dream'等4つの文字列すべてを走査 for (int j = 0; j < D_SIZE; ++j) { // sから、tに設定された文字数以降から、走査中のdの文字数文切り出し、それがdに一致する場合 if (s.substr(t.size(), d[j].size()) == d[j]) { // tに追加する t += d[j]; // ループを継続 flg = true; } } // 文字列が追加できる可能性がある限り処理を繰り返す } while (flg); cout << (s == t ? "YES" : "NO") << endl; return 0; }
Python
endswith()
を使用し、末尾が一致しているか判定します。
# coding: utf-8 ws = ['dream', 'dreamer', 'erase', 'eraser'] s = input() t = '' flg = True while flg: flg = False for w in ws: if s.endswith(w + t): t = w + t flg = True break print('YES' if s == t else 'NO')
Ruby
end_with?()
を使用し、末尾が一致しているか判定します。
# coding: utf-8 s = gets.strip ds = %w(dream dreamer erase eraser) # 末尾が一致しているものがある限り処理を繰り返す while ds.any? { |d| s.end_with?(d) } do # 一致した末尾を削除する ds.each { |d| s = s[0..-d.size - 1] if s.end_with?(d) } end puts s.empty? ? 'YES' : 'NO'
ABC086C - Traveling
毎秒x、もしくはy方向に±1移動するということは、毎秒ごとに移動量の偶奇が入れ替わるということです。
また、経過時間以上の移動量は起こり得ないです。
これらの条件をすべて満たすことができるかで、旅行プランが実行可能かを判定します。
C++
#include <iostream> using namespace std; int n; int t[100001], x[100001], y[100001]; int main() { cin >> n; t[0] = x[0] = y[0] = 0; // 初期状態(スタート地点) for (int i = 1; i <= n; ++i) cin >> t[i] >> x[i] >> y[i]; bool flg = true; // 旅行プラン実行可能フラグ // 訪れる予定すべてを走査 for (int i = 1; i <= n; ++i) { int dt = t[i] - t[i - 1]; // 時刻の差 int dist = abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]); // 距離の差(絶対値) // 時刻に対して移動量が大きい、もしくは、時刻と移動量の偶奇が違う場合、プランは実行不可能 if (dt < dist || (dt + dist) % 2 != 0) flg = false; } cout << (flg ? "Yes" : "No") << endl; return 0; }
Python
# coding: utf-8 n = int(input()) pre = [0, 0, 0] // 現在訪れている時刻、点(x, y)から見た直前の時刻、点 t, x, y = [0, 1, 2] flg = True for _ in range(n): now = [int(i) for i in input().split()] # 現在と直前との差 dif = [abs(n - p) for n, p in zip(now, pre)] if dif[t] < dif[x] + dif[y] or sum(dif) % 2 != 0: flg = False break # 直前の値を現在の値で更新 pre = now print('Yes' if flg else 'No')
Ruby
# coding: utf-8 n = gets.to_i ds = n.times.map { gets.strip.split.map(&:to_i) } pre = [0, 0, 0] # 全ての予定に対して、旅行プランが実行可能か flg = ds.all? do |d| # 現在と直前との差 dt, dx, dy = d.zip(pre).map { |i| i.inject(:-).abs } # 直前の値を現在の値で更新 pre = d # 旅行プランが実行可能か判定 dx + dy <= dt && (dt + dx + dy) % 2 == 0 end puts flg ? 'Yes' : 'No'
Volume0: 0002
数値の桁数を求める問題
解答
整数の桁数を求めるので、文字列に変換し、文字列の長さを求めれば良い
while True: try: # 入力から2つの整数を受け取る a, b = [int(i) for i in input().split()] # 2つの整数を足し、文字列に変換した後、その文字列の長さを出力する print(len(str(a + b))) except EOFError: break
reduce
を使用し、入力値のリストを縮約しても良い
from functools import reduce while True: try: print(reduce(lambda a, b: len(str(a + b)), [int(i) for i in input().split()])) except EOFError: break
Volume0: 0001
ソートに関する問題
解答
リストを降順に並べ替えて、上から3つ切り出せば良い
# 山の高さ10個のデータ mountains = [int(input()) for _ in range(10)] # 山の高さが高い順に3件分、ループで取り出す for height in sorted(mountains, reverse=True)[:3]: # 山の高さを出力 print(height)
一行で書く
print(*sorted([input() for _ in range(10)])[::-1][:3], sep='\n')
Volume0: 0000
九九を出力する問題
解答
二重ループを利用する
# 掛けられる数 i for i in range(1, 10): # 掛ける数 j for j in range(1, 10): # 九九を出力 print(f'{i}x{j}={i * j}')
一行で書く
[print(f'{i}x{j}={i * j}') for i in range(1, 10) for j in range(1, 10)]
ITP1_10_D: Distance II
ミンコフスキー距離 | プログラミング入門 | Aizu Online Judge
数学に関する問題
解答
問題文で与えられた数式をコードにしていきます。
まず、xとyの距離をそれぞれ計算します。
次に、求めた距離をそれぞれp乗し、その合計を求めます。
そして、求めた合計をpの逆数乗します。
# coding: utf-8 n = input() xs = map(float, input().split()) ys = map(float, input().split()) abs_d = [abs(x - y) for (x, y) in zip(xs, ys)] d = [sum([i ** p for i in abs_d]) ** (1 / p) for p in range(1, 4)] d.append(max(abs_d)) print(*d, sep='\n')
ITP1_10_C: Standard Deviation
標準偏差 | プログラミング入門 | Aizu Online Judge
数学に関する問題
解答1
問題文で与えられた数式をコードにしていきます。
# coding: utf-8 while True: n = int(input()) if n == 0: break s = list(map(float, input().split())) m = sum(s) / n a_2 = sum([(x - m) ** 2 for x in s]) / n print(a_2 ** 0.5)
解答2
標準ライブラリにあるpstdev()
メソッドを使用します。
# coding: utf-8 from statistics import pstdev while True: n = int(input()) if n == 0: break s = list(map(float, input().split())) print(pstdev(s))