ABC170 - 解説 (A〜D)
A - Five Variables
URL
https://atcoder.jp/contests/abc170/tasks/abc170_a
解法
解法は2つある
①5つの入力をすべて受け取り、0だったものの番号を出力する。
②15から入力された数値の和を引く
ソースコード
https://atcoder.jp/contests/abc170/submissions/14285940 (②の方法)
コメント
①はないのかって？無いです。②の方法を先に思いついたしそっちのほうが楽だから。
B - Crane and Turtle
URL
https://atcoder.jp/contests/abc170/tasks/abc170_b
解法
つるの数をN、亀の数をMとすると、足の数は
2N+4M
となる。
このことから、足の総数は2X以上、4X未満となる(Xは入力の数値。鶴と亀の総数を表す)。これを条件①とする。
また、鶴と亀の足の本数はどちらも偶数本であることから、
入力される数値Y(＝足の総数)は偶数である必要がある。これを条件②とする。
以上のことより、入力が①と②の両方を満たしていればその入力に対する解は存在する。
ソースコード
https://atcoder.jp/contests/abc170/submissions/14298187
コメント
鶴亀算なんて言うものがあったなぁ。どんな式だったっけ。忘れた。
C - Forbidden List
URL
https://atcoder.jp/contests/abc170/tasks/abc170_c
解法
整数列pに含まれない数字のうち、Xとの絶対値が最小のもののうち、最小のものを答える。
つまり、Xがpに含まれているかを確認し、含まれていれば次は
X-1について、その次はX+1、X-2、X+2...
というふうに探索する。
この問題の制約は1<=N<=100だから、この方法でも十分間に合う。
ソースコード
https://atcoder.jp/contests/abc170/submissions/14312043
コメント
最近C問題全探索多くない？
D - Not Divisible
URL
https://atcoder.jp/contests/abc170/tasks/abc170_d
解法
問題の意図は、入力された数値のうち、どの数でも割りきることができない数(今後、このような数を「素数状態にある数」と呼ぶ)がいくつあるかを調べよ、
というもの。
そのため、入力を昇順にソートし、要素数が入力の最大値Mのint型の0で初期化した配列(dpとする)を用意する。
そして、入力を小さい方から見ていき(その時見ている数をxとおく)、次のようにdpを操作する。
①dp[x]を+1する。
②M以下のすべてのxy(1<y,yは整数)について、dp[xy]を+1する。
以上の操作を行うと、dp[x]には、入力の中に、1を除くxの約数が何個あるかが示されている。
そのため、素数状態にあるのは、dp[x]が1であるxとなる。よって、そのようなxの個数を調べれば良い。
ソースコード
https://atcoder.jp/contests/abc170/submissions/14390625
コメント
「任意の〜」を「ある〜」と思っていたせいで実装できなかった。(本当は「すべての〜」という意味らしい)
数学って大事だねぇ
ABC148解説(A~E)
A Round One
概要
A,Bが与えられたとき、1,2,3のうち入力されなかった数を出力せよ。
解法
出力の選択肢は全て異なる整数であるため、入力された数A,Bの和を、1,2,3の総和6から引けばよい。
B Strings with the Same Length
概要
長さNの文字列SとTを一文字ずつ交互に出力せよ。
解法
for文などを使い、一回のループでS,Tそれぞれ一文字ずつ、計二文字出力させる。
C Snack
概要
AとBの最小公倍数を求めよ。
解法
AとBの最小公倍数は、A*B/(AとBの最大公約数)によって求められる。また、この最大公約数はユークリットの互除法を使えば求めることができる。
D Brick Break
概要
与えられた整数列の中から、連続した整数の最大値を求め全体の要素数からその最大値を引け
解法
まず、考えうる最大値maxの初期値を1とし、入力された値がmaxと等しければmaxに位置を加える。この動作を入力が終了するまで繰り返す。しかし、これだと入力に１が存在していなくてもすぬけさんが満足してしまうため、入力とmaxが等しいことを示すbool型の変数を利用する
E Double Factorial
※ここから先、語彙力の欠乏特殊な表現に注意※
概要
与えられた整数Nに自然数N-2*aをかけ続けた時、その計算結果Qの末尾に0は何個連続してついているかを求めよ。
解法
まず、末尾に0がつくということは、Qを素因数分解したときに5と2が現れるということ。また、問題文より2を引きつづけるので末尾に0を付けるには、最低限Nは偶数である必要があるとともに、それを満たす最小の５の倍数10以上である必要がある。
そして、末尾に0がつくのは(5のx乗)*(2のy乗)であり、前提条件として、Nが偶数なので、問題文は、
”計算結果Qを素因数分解したときに現れる5の指数を求めよ”
と書き換えられる。これをfor文等を使って求めればよい
