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'
