AtCoder Beginner Contest 112
AtCoder Beginner Contest 112に参加しました。自分なりの考察と解答をまとめます。
A Programming Education
問題
1か2の入力を受け取り、1ならば 'Hello World'を、2ならば 2つの入力を受け取りその和を出力せよ。
最初に整数の入力を受け取り、それによって処理を分岐させれば良いです。
sample code:
Submission #3341589 - AtCoder Beginner Contest 112
B Time Limit Exceeded
問題
より小さいコスト
の中で一番小さいものを出力せよ。
最初にpair<int, int>型のvectorを用意して入力を受け取ります。
その後受け取った入力に対して、 を超えない最小の
を出力すれば良いです。
sample code:
Submission #3343694 - AtCoder Beginner Contest 112
C Pyramid
問題
中心座標が ( ) で高さが
のピラミッドがある。座標 (
) の高度が
で与えられるとき、N個の座標の情報と以下の条件から中心座標と高さを求めよ。
条件
は0以上100以下で,
は1以上の整数。
N個の情報の
番目は, 「座標 (
) の高度は
である」
考察
今回の鬼門のC問題です (4WA)
いろいろ条件がありますが、一旦それらを無視して中心座標と高さの求め方を考えてみましょう。
条件より、 は0以上100以下、なので
の組み合わせはたかだか104通りです。
さらに、座標 ( ) の高度は
で与えられるので、
より、
となります( でないとします)。
よって、2重ループで中心座標候補を決め、その候補に対して を求めて、それがN個の情報と一致するか調べればよいです。
ただ、このまま提出するとWAです。
気を付けなければならないのは、 と
の条件です。つまり、
中心座標候補から求めた
のときは,
。
という操作を行う必要があります。
これらすべてをかいくぐることでやっとACがもらえます。
sample code:
Submission #3353690 - AtCoder Beginner Contest 112
D Partition
問題
整数 が与えられる。
となる正整数からなる長さ
の数列
のおいて,
の最大公約数の最大値を求めよ。
考察
がちがち(?)の数学問です。
最初に取り得るGCD(最大公約数)の最大値を考えてみます。
整数のGCDは明らかに
以下なので、数列で最小の整数の約数になります。
よって、すべての数列の要素がであれば最大であるとわかります。
さらに、数列の公約数がのとき、
となるはずなので、
も
を約数に持ちます。
後は、数列のGCDの最大値が だと分かっているのでそこまでで一番大きい
の約数を出力すれば良いです。
sample code :
Submission #3353047 - AtCoder Beginner Contest 112
このコードでは、109 / 2なら全探索で回るだろーと思って約数を求める手順を省いちゃってます。
Cが普通に難しかった...
