0. はじめに
就活が終わった24歳、学生です。
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
を一通りやったので備忘録がてら記事にしました。後ほど適宜修正したりするかも。
1. Atcoder Beginners Selection
AtCoderの過去問をやっていくにあたって、以下のような素晴らしいサービスがありました:
とりあえずここに載っている問題をやっていきます。
解法などは、こちらの記事を参考にしました。マークダウンなども参考にさせていただいているので、一部表現が似ている部分があるかもしれません。問題があったら教えていただけると助かります。
AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた
第 1 問: ABC 086 A - Product (100 点)
【問題概要】
二つの正整数 $a$, $b$ が与えられます。 $a$ と $b$ の積が偶数か奇数か判定してください。
【制約】
- $1 \le a, b \le 10000$
- $a$, $b$ は整数
【数値例】
1)
$a = 3$
$b = 4$
答え: Even
3 × 4 = 12 でこれは偶数なので、"Even" を出力します。
$a = 1$
$b = 21$
答え: Odd
1 × 21 = 21 でこれは奇数なので、"Odd" を出力します。
【コメント】
標準入力を取得するための
a, b = map(int, input().split())
の操作がわかれば良さそう。復習になりました。
【ポイント】
- map()
第 2 問: ABC 081 A - Placing Marbles (100 点)
【問題概要】
0 と 1 のみから成る 3 桁の番号 s が与えられます。1 が何個含まれるかを求めてください。
【数値例】
1)
s = "101"
答え: $2$
'1' が 2 個含まれています。
【コメント】
Sが文字列だったので、SがリストっぽくなってSの中の"1"をcountすると答えが出た。
【ポイント】
- string 型
- input()
- count()
第 3 問: ABC 081 B - Shift Only (200 点)
【問題概要】
黒板に $N$ 個の正の整数 $A_1, \dots, A_N$ が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。
- 黒板に書かれている整数すべてを，$2$ で割ったものに置き換える。
すぬけ君は最大で何回操作を行うことができるかを求めてください。
【制約】
- $1 \le N \le 200$
- $1 \le A_i \le 10^9$
【数値例】
1)
$N = 3$
$A = (16, 12, 24)$
答え: $2$
1 回操作を行うと (8, 6, 12) になります。2 回操作を行うと (4, 3, 6) になります。2 個目の 3 が奇数なため 3 回目の操作は行えません。
【コメント】
あ
【ポイント】
- for文を使った全探索
- list(map(int,input().split()))
第 4 問: ABC 087 B - Coins (200 点)
【問題概要】
500 円玉を $A$ 枚、100 円玉を $B$ 枚、50 円玉を $C$ 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りあるでしょうか？
【制約】
- $0 \le A, B, C \le 50$
- $A + B + C \ge 1$
- $50 \le X \le 20000$
- $A, B, C$ は整数である
- $X$ は $50$ の倍数である
【数値例】
1)
$A = 2$
$B = 2$
$C = 2$
$X = 100$
答え: $2$
条件を満たす選び方は以下の 2 通りです。
- 500 円玉を 0 枚、100 円玉を 1 枚、50 円玉を 0 枚選ぶ
- 500 円玉を 0 枚、100 円玉を 0 枚、50 円玉を 2 枚選ぶ
【コメント】
- for 文を用いた全探索
- 二重三重の for 文
第 5 問: ABC 083 B - Some Sums (200 点)
【問題概要】
$1$ 以上 $N$ 以下の整数のうち、$10$ 進法で各桁の和が $A$ 以上 $B$ 以下であるものについて、総和を求めてください。
【制約】
- $1 \le N \le 10^4$
- $ 1 \le A \le B \le 36$
- 入力はすべて整数
【数値例】
1)
$N = 20$
$A = 2$
$B = 5$
答え: $84$
20 以下の整数のうち、各桁の和が 2 以上 5 以下なのは、2, 3, 4, 5, 11, 12, 13, 14, 20 です。これらの合計である 84 を出力します。
【コメント】
- 整数の 10 進法表記の扱い方
- for 文
第 6 問: ABC 088 B - Card Game for Two (200 点)
【問題概要】
$N$ 枚のカードがあり、$i$ 枚目のカードには $a_i$ という数が書かれています。
Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。
2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。
【制約】
- $N$ は $1$ 以上 $100$ 以下の整数
- $a_i$ は $1$ 以上 $100$ 以下の整数
【数値例】
1)
$N = 3$
$a = (2, 7, 4)$
答え: $5$
以下が最適です:
- 1 ターン目: Alice が 7 を取る
- 2 ターン目: Bob が 4 を取る
- 3 ターン目: Alice が 2 を取る
Alice は 7 + 2 = 9 点、Bob は 4 点を獲得するので、その差は 9 - 4 = 5 点です。
【コメント】
- ソート
- Greedy
- sorted
- slice [::2],[1::2]とか
第 7 問: ABC 085 B - Kagami Mochi (200 点)
【問題概要】
$N$ 個の整数 $d[0], d[1], \dots, d[N-1]$ が与えられます。
この中に何種類の異なる値があるでしょうか？
(原問題文をかなり意訳していますが、題意はこういうことです)
【制約】
- $1 \le N \le 100$
- $1 \le d[i] \le 100$
- 入力値はすべて整数
【数値例】
1)
$N = 4$
$Q = 3$
$d = (8, 10, 8, 6)$
答え: $3$
6, 8, 10 の 3 種類です。
【コメント】
- 集計処理
- バケット法
- 連想配列
第 8 問: ABC 085 C - Otoshidama (300 点)
【問題概要】
10000 円札と、5000 円札と、1000 円札が合計で $N$ 枚あって、合計金額が $Y$ 円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。
【制約】
- $1 \le N \le 2000$
- $1000 \le Y \le 2*10^7$
- $N$ は整数
- $Y$ は $1000$ の倍数
【数値例】
1)
$N = 9$
$Y = 45000$
答え: $(4, 0, 5)$ など
10000 円札 4 枚と 1000 円札 5 枚で、合計枚数が 9 枚、合計金額が 45000 円になります。他の答えもあります。
【コメント】
- for 文を用いた全探索
- 二重三重の for 文
- 少し工夫が必要
- exit()
第 9 問: ABC 049 C - Daydream (300 点)
【問題概要】
英小文字からなる文字列 $S$ が与えられます。
$T$ が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで $S = T$ とすることができるか判定してください。
- $T$ の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。
【制約】
- $1 \le |S| \le 10^5$
- $S$ は英小文字からなる
【数値例】
1)
$S$ = "dreameraser"
答え: "YES"
"dream", "eraser" の順で $T$ の末尾に追加することで $S = T$ とすることができます。
【コメント】
- Greedy アルゴリズム
- 端から決まって行く Greedy アルゴリズム
- 後ろから解く
第 10 問: ABC 086 C - Traveling (300 点)
【問題概要】
シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻 $0$ に 点 $(0, 0)$ を出発し、$1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に 点 $(x_i, y_i)$ を訪れる予定です。
AtCoDeer くんが時刻 $t$ に 点 $(x, y)$ にいる時、 時刻 $t+1$ には 点 $(x+1,y), (x−1,y), (x,y+1), (x,y−1)$ のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。
【制約】
- $1 \le N \le 10^5$
- $0 \le x_i, y_i \le 10^5$
- $1 \le t_i \le t_{i+1} \le 10^5$
- 入力はすべて整数
【数値例】
1)
$N = 2$
$(t, x, y) = (3, 1, 2), (6, 1, 1)$
答え: "Yes"
例えば $(0,0), (0,1), (1,1), (1,2), (1,1), (1,0), (1,1)$ と移動すれば目的を果たせます。
【コメント】
- パリティ
気づいたこと
上手い人の解法を見ると、「こんなに少ない行で書けるのか」「自分で書いたコードセンス無さ過ぎて草」といった気持ちになり、発見があって面白いですね。めげずに頑張ろう。
このあとは
Atcoderに慣れるということと、ざっくりとした雰囲気を知るということはできたと思うので、ABCコンテストに参加したりAtcoder Problemsに参加したりしていきます。