エイシング プログラミング コンテスト 2020 備忘録
エイシングプログラミングコンテスト2020の備忘録です。
問題はこちら↓
今回はABC3完でした。
・A問題:Number of Multiples
L,R,d が入力として与えられ、L 以上 R 以下の d の倍数がいくつあるか数える。L から R+1 までループを回して d で割り切れるものの数を数えればよい。
解答例(Python)
https://atcoder.jp/contests/aising2020/submissions/15182475
・B問題:B An Odd Problem
1~N の番号がついた N 個のマスがあり、それぞれのマス i には整数 ai が書かれている。このマスのうち「マスの番号が奇数」・「マスに書かれた整数が奇数」の両方を満たすマスの数を数える。
0indexでループを回した時には偶数の時がマスの番号が奇数になるので、0から N まで2ずつ増やしてループを回し、ai が奇数であるか調べればよい。
解答例(Python)
https://atcoder.jp/contests/aising2020/submissions/15182659
・C問題:XYZ Triplets
f(n)を2つの条件両方を満たすような3つの整数の組(x,y,z)の個数とする。
ここで条件とは
・1≦x,y,z
・x^2+y^2+z^2+x*y+y*z+x*z=n
である。整数 N が与えられるのでf(1),f(2)...f(N)をそれぞれ求める。
2つ目の条件から探索範囲は最大でも √N まで調べればよいことが分かるので、制約が 1≦N≦10000 から全探索で求めることができる。
ただし、1~N まで順に求めようとすると 10000*100*100 = 10^8 となり間に合わない可能性が高い。そこで 1~N までのそれぞれのf(N)の個数を配列で持っておき、x,y,z を 1~√Nまで全て探索し2つ目の条件の式に代入して求めた n に応じた配列のindexに1を足していき、最後に 1~N までの個数を出力するようにすることで時間内に求めることができる。
解答例(Python)
https://atcoder.jp/contests/aising2020/submissions/15183069