pontz_rwのブログ

プログラミング等の備忘録

Volume0: 0004

連立方程式 | Aizu Online Judge

連立方程式の解を求める問題です

クラーメルの公式を利用します

Python

# coding: utf-8

while True:
    try:
        a, b, c, d, e, f = [int(i) for i in input().split()]

        detA = a * e - b * d
        detA1 = c * e - b * f
        detA2 = a * f - c * d

        # -0.000 を 0.000 にするために 0 を足す
        print('{:.3f} {:.3f}'.format(detA1 / detA + 0, detA2 / detA + 0))
    except EOFError:
        break

Ruby

# coding: utf-8

while line = gets
    a, b, c, d, e, f = line.strip.split.map(&:to_f)
    detA = a * e - b * d
    detA1 = c * e - b * f
    detA2 = a * f - c * d
    # -0.000 を 0.000 にするために 0 を足す
    puts "%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0]
end

文字列の%演算は、第1引数にフォーマット、第2引数にフォーマットしたい値を指定します

書式に埋め込む値が複数ある場合は、右辺を配列にします

"%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0]

Volume0: 0003

正三角形 | Aizu Online Judge

三平方の定理を利用します

直角三角形の斜辺 c と他の 2a, b との関係は、 a^{2} + b^{2} = c^{2} です

C++

#include <iostream>
using namespace std;

int a, b, c, n;

int main()
{
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a >> b >> c;

        // cを斜辺にする
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);

        cout << (a * a + b * b == c * c ? "YES" : "NO") << endl;
    }

    return 0;
}

Python

# coding: utf-8

for i in range(int(input())):
    a, b, c = sorted([int(i) for i in input().split()])
    print('YES' if a ** 2 + b ** 2 == c ** 2 else 'NO')

Ruby

# coding: utf-8

gets.to_i.times do
    a, b, c = gets.chomp.split().map(&:to_i).sort()
    puts a ** 2 + b ** 2 == c ** 2 ? 'YES' : 'NO'
end

AtCoder Beginner Contest 096

AtCoder Beginner Contest 096

A - Day of Takahashi

各月に対して、高橋の日になる月の数と日の数との組み合わせは 1 通りずつです

ab 日において、

  1. a \leqq b の場合、合計 a
  2. a \gt b の場合、合計 a - 1

となります

# coding: utf-8

a, b = [int(i) for i in input().split()]

print(a - 1 if a > b else a)

B - Maximum Sum

A+B+C を最大化するためには、A, B, C の中で最大の整数を 2 倍する操作を k 回繰り返せば良いです

つまり、 A + B + C + \max (A, B, C) \times (2^{k} - 1) で求めることができます

# 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

5 で割って 1 余る素数を列挙すれば良く、これらの素数から 5 個選んだ合計は全て 5 の倍数となります(つまり、合成数です)

# 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文字ずつ整数に再変換して計算します。
  2. 整数の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で割った余りで表現することができます。

つまり、

  1. カードの数を配列(リスト)に設定します。
  2. これを降順にソートします。
  3. 配列(リスト)のインデックスが偶数の全要素の合計と、奇数の全要素の合計との差で、二人の得点差を求めます。

と処理することで、解を求めることができます。

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

桁数 | Aizu Online Judge

数値の桁数を求める問題

解答

整数の桁数を求めるので、文字列に変換し、文字列の長さを求めれば良い

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

山の高さ | Aizu Online Judge

ソートに関する問題

解答

リストを降順に並べ替えて、上から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

九九 | Aizu Online Judge

九九を出力する問題

解答

二重ループを利用する

# 掛けられる数 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)]