AtCoder Beginners Selectionの実施記録(Crystal)

## 概要

表題のプログラミング言語でAtCoder Beginners Selectionを実施記録した際の記録です
基本文法の学習が目的です

> https://atcoder.jp/contests/abs
> AtCoder Beginners Selectionとは？
> このコンテストは、「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集です。
> 問題は、dr.kenさんの、「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」から選出しています。

基本的には以下ができれば大体の問題を解けるようになっている。

- 標準入力
- 標準出力
- 四則演算
- 条件分岐
- 文字列操作
- ループ
- 配列の操作
- 全通りの探索
- 組み込み関数等の利用
- ソート
- 集合
- 二次元配列の操作

## PracticeA - Welcome to AtCoder 

[PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)

> 問題文
> 高橋君はデータの加工が行いたいです。
> 整数 a,b,cと、文字列 s が与えられます。 a+b+c の計算結果と、文字列 s を並べて表示しなさい。
>
> 制約
1≤a,b,c≤1,000
1≤∣s∣≤100
>
> 入力
> 入力は以下の形式で与えられる。
> a
> b c
> s
>
> 出力
> a+b+c と s を空白区切りで 1 行に出力せよ。

基本的な標準入力、標準出力、四則演算ができればOK

```main.cr
a = read_line.to_i
b, c = read_line.split.map(&.to_i)
s = read_line
puts "#{a+b+c} #{s}"
```

## ABC086A - Product 

[ABC086A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

>問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。
>
>制約
>1 ≤ a,b ≤ 10000
>a,b は整数
>
>入力
>入力は以下の形式で標準入力から与えられる。
>a b
>
>出力
積が奇数なら Odd と、 偶数なら Even と出力せよ。

基本的な標準入力、標準出力、四則演算、条件分岐ができればOK

```main.cr
a, b = read_line.split.map(&.to_i)

# a と b の積が偶数か奇数か判定する
if a * b % 2 == 0
  # 偶数の場合
  puts "Even"
else
  # 奇数の場合
  puts "Odd"
end
```

## ABC081A - Placing Marbles 

[ABC081A - Placing Marbles ](https://atcoder.jp/contests/abs/tasks/abc081_a)

> 問題文
>すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。各マスには 0 か 1 が書かれており、マス i には si が書かれています。
>すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。
>
>制約
>s1 ,s2 ,s3 は 1 あるいは 0
>
>入力
>入力は以下の形式で標準入力から与えられる。
>s1s2s3 
>
>出力
>答えを出力せよ。
>
>入力例 1
>101
>
>出力例 1
>2


基本的な標準入力、標準出力、文字列操作ができればOK

```main.cr
# 標準入力から文字列を取得
s = read_line
# 文字列中の '1' の数を数える
puts s.count("1")
```

## ABC081B - Shift only 
[ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)

> 問題文
>黒板に N 個の正の整数 A1,...,AN が書かれています．
>すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
>黒板に書かれている整数すべてを，2 で割ったものに置き換える．
>すぬけ君は最大で何回操作を行うことができるかを求めてください．
>
>制約
>1≤N≤200
>1≤Ai≤10^9
>
>入力
>入力は以下の形式で標準入力から与えられる。
>N
>A1 A2 ... AN
>
>出力
>すぬけ君は最大で何回操作を行うことができるかを出力せよ．
>
>入力例 1 
>3
>8 12 40
>
>出力例 1 
>2

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作ができればOK

```main.cr
# N個の整数を読み込む
n = gets.to_i
# N個の整数を配列として読み込む
numbers = gets.split.map(&:to_i)

# 最小操作回数を保存する変数
min_operation = 1e9

# 整数の配列を順に処理する
numbers.each do |number|
  # 現在の整数が2で割り切れる回数
  operation = 0

  # 現在の整数が2で割り切れるかどうかを確認する
  while number % 2 == 0
    # 現在の整数を2で割る
    number /= 2
    # 割り切れた回数をカウントする
    operation += 1
  end

  # 最小操作回数を更新する
  min_operation = [min_operation, operation].min
end

# 最小操作回数を出力する
puts min_operation
```

## ABC087B - Coins
[ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)

> 問題文
>あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
>同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
>
>制約
>0≤A,B,C≤50
>A+B+C≥1
>50≤X≤20,000
>A,B,C は整数である
>X は 50 の倍数である
>
>入力
>入力は以下の形式で標準入力から与えられる。
>A
>B
>C
>X
>
>出力
>硬貨を選ぶ方法の個数を出力せよ。

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作、全通りの探索ができればOK

```main.cr
# 入力を受け取る
a = gets.to_s.to_i
b = gets.to_s.to_i
c = gets.to_s.to_i
x = gets.to_s.to_i

# 硬貨を選ぶ方法の個数をカウントする変数
count = 0

# 硬貨を選ぶ方法を全て試す
(0..a).each do |i|
  (0..b).each do |j|
    (0..c).each do |k|
      # 選んだ硬貨の総額がX円になっている場合はカウントを増やす
      if (i * 500 + j * 100 + k * 50) == x
        count += 1
      end
    end
  end
end

# 結果を出力する
puts count
```

## ABC083B - Some Sums
[ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)

>問題文
>1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。
>
>制約
>1≤N≤10^4 
>1≤A≤B≤36
>入力はすべて整数である
>
>入力
>入力は以下の形式で標準入力から与えられる。
>N A B
>
>出力
>1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

基本的な標準入力、標準出力、四則演算、ループ、条件分岐、配列の操作、組み込み関数の利用、ができればOK

```main.cr
# N, A, Bを受け取る
n, a, b = read_line.split.map(&.to_i)

# 答えを格納する変数
ans = 0

# 1からNまでの整数を順番に処理する
1.upto(n) do |i|
  # iを10進数で表したときの各桁の和を求める
  sum = i.to_s.chars.map(&.to_i).sum

  # sumがA以上B以下であれば、ansにiを加える
  ans += i if a <= sum && sum <= b
end

# 最終的な答えを出力する
puts ans
```

## ABC088B - Card Game for Two
[ABC088B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)

> 問題文
>N 枚のカードがあります. i 枚目のカードには, ai という数が書かれています.
>Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
>2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
>
>制約
>N は 1 以上 100 以下の整数
>ai(1≤i≤N) は 1 以上 100 以下の整数
>
>入力
>入力は以下の形式で標準入力から与えられる.
>N
>a1 a2 a3 ... aN
>
>出力
>両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

基本的な標準入力、標準出力、四則演算、条件分岐、配列の操作、ループ、ソート、ができればOK

```main.cr
# 問題に従って、カードの枚数を表す変数 `n` と、各カードの数を表す配列 `cards` を定義する
n = read_line.to_i
cards = read_line.split.map(&.to_i).sort.reverse

# cards の降順に並べ替える
cards.sort.reverse

# 得点の差分を取得
diff = 0
n.times do |i|
  if i % 2 == 0
    diff += cards[i]
  else
    diff -= cards[i]
  end
end

# 出力
puts diff
```

## ABC085B - Kagami Mochi 
[ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)

> 問題文
>X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
>ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は diセンチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。
>
>制約
>1≤N≤100
>1≤di≤100
>入力値はすべて整数である。
>
>入力
>入力は以下の形式で標準入力から与えられる。
>N
>d1
>​:
>dN
>
>​出力
>作ることのできる鏡餅の最大の段数を出力せよ。
>
>入力例 1 
>4
>10
>8
>8
>6
>
>出力例 1 
>3


基本的な標準入力、標準出力、四則演算、ループ、配列、集合、ができればOK

```main.cr
# 入力を受け取る
n = gets.to_s.to_i
d = Array.new(n){ read_line.to_i }

# 鏡餅を作るための餅の直径を昇順に並び替える
d = d.sort

# 最大の段数
max_height = 1
max_d = d[0]

# 鏡餅を作ることができるかどうかを確認する
n.times do |i|
  if d[i] > max_d
    # 鏡餅を1段増やす
    max_height += 1
    max_d = d[i]
  end
end

# 結果を出力する
puts max_height
```

## ABC085C - Otoshidama
[ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)

>問題文
>日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
>青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
>
>制約
>1≤N≤2000
>1000≤Y≤2×10^7
>N は整数である。
>Y は 1000 の倍数である。
>
>入力
>入力は以下の形式で標準入力から与えられる。
>N Y
>
>出力
>N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
>N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。
>
>入力例 1 
>9 45000
>
>出力例 1 
>4 0 5

基本的な標準入力、標準出力、四則演算、ループができればOK

```main.cr
n, yy = read_line.split.map(&.to_i)

# x、y、zの値を初期化します。
x = 0
y = 0
z = 0

# xの値を1からNまで変化させながら、
# N枚のお札の合計金額がyy円となるかを判定します。
(0..n).each do |x|
  # yの値を0からN-xまで変化させながら、
  # N枚のお札の合計金額がY円となるかを判定します。
  (0..(n-x)).each do |y|
    # zの値をn-x-y枚とします。
    z = n-x-y

    # N枚のお札の合計金額がY円となるかを判定します。
    if yy == x * 10000 + y * 5000 + z * 1000
      # N枚のお札の合計金額がyy円となる場合は、x、y、zの値を出力します。
      puts "#{x} #{y} #{z}"
      exit
    end
  end
end

# N枚のお札の合計金額がY円となることがありえない場合は、-1 -1 -1と出力します。
puts "-1 -1 -1"
```

## ABC049C - 白昼夢
[ABC049C - 白昼夢](https://atcoder.jp/contests/abs/tasks/arc065_a)

>問題文
>英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
>
>制約
>1≦∣S∣≦10^5
>S は英小文字からなる。
>
>入力
>入力は以下の形式で標準入力から与えられる。
>S
>
>出力
>S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。
>
>入力例 1 
>erasedream
>
>出力例 1 
>YES

基本的な標準入力、標準出力、文字列操作ができればOK

```main.cr
# 入力から文字列Sを取得する
s = read_line

# 文字列Sを逆順にしたものを用意する
t = s.reverse

# 文字列Tから順に文字を取り出しながら、dream、dreamer、erase、eraserのいずれかであるか判定する
while t.size > 0
  if t.starts_with?("maerd")
    t = t[5..-1]
  elsif t.starts_with?("remaerd")
    t = t[7..-1]
  elsif t.starts_with?("esare")
    t = t[5..-1]
  elsif t.starts_with?("resare")
    t = t[6..-1]
  else
    puts "NO"
    exit
  end
end

# 全ての文字がdream、dreamer、erase、eraserのいずれかであった場合、YESを出力する
puts "YES"
```

## ABC086C - Traveling
[ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)

> 問題文
>シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻tiに 点 (xi,yi) を訪れる予定です。
>AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
>
>制約
>1 ≤ N ≤ 10^5 
>0 ≤ xi ≤ 10^5
>0 ≤ yi ≤ 10^5
>1 ≤ ti ≤ 10^5
>ti < ti+1 (1 ≤ i ≤ N−1)
>入力は全て整数
>
>入力
>入力は以下の形式で標準入力から与えられる。
>N
>t1 x1 y1
>​t2 x2 y2 
>:
>tN xN yN
>
>出力
>旅行プランが実行可能ならYesを、不可能ならNoを出力してください。
>
>入力例 1 
>2
>3 1 2
>6 1 1
>
>出力例 1 
>Yes
>
>入力例 2 
>1
>2 100 100
>
>出力例 2 
>No
>(0,0) にいる状態から 2 秒後に (100,100) にいるのは不可能です。
>
>入力例 3 
>2
>5 1 1
>100 1 1
>
>出力例 3 
>No



基本的な標準入力、標準出力、四則演算、ループ、二次元配列の操作、ができればOK

```main.cr
n = gets.to_s.to_i

# 配列を定義し、最初は全て0で初期化する
a = Array.new(n+1){Array.new(3,0)}
a[0][0] = 0
a[0][1] = 0
a[0][2] = 0

# 入力を配列に格納する
(1..n).each do |i|
  a[i] = read_line.split.map(&.to_i)
end

# 前の位置から移動した距離を計算し、
# 移動距離が1以内ならYesを出力し、
# そうでないならNoを出力する
(1..n).each do |i|
  x = (a[i][1] - a[i-1][1]).abs
  y = (a[i][2] - a[i-1][2]).abs
  t = a[i][0] - a[i-1][0]

  if x + y > t || (t - x - y) % 2 == 1
    puts "No"
    exit
  end
end
puts "Yes"
```

# 参考

https://atcoder.jp/contests/abs