AtCoder Beginner Contest 148に参加した記録
AtCoder Beginner Contest 148 – AtCoder
AtCoder Beginner Contest 148に参加しました。
結果、ABCD4完でした。レートは微減で900位か割らず緑レートです。前回が1400位のパフォーマンスでしたが今回は800台と大きく下がりました。
原因はもちろん数学問題?のEが解けなかったからです。この手の問題は特に苦手ですね。ということでとりあえず振り返っていきます。
全体的な難易度として、過去一番の易しさだったと思います。AtCoder Problems で確認しても D の Difficulty が 108 でABC139のD問題よりも易しいし、Eが茶、Fが水なのでやはり全体的に簡単な問題だったみたいです。
A – Round One
1, 2, 3 のうち2つが入力で与えられるので、残りの1個を出力する問題です。
if文を書くだけです。
B – Strings with the Same Length
B – Strings with the Same Length
2つの文字列 S, T が与えられるので、S の 1 文字目、T の 1 文字目、S の 2 文字目、T の2 文字目、S の 3 文字目、…、S のN 文字目、T のN 文字目というように、S の各文字と T の各文字を先頭から順に交互に文字を並べた文字列を出力するという問題です。
var ans = "";
for (int i = 0; i < N; i++)
{
ans += S[i];
ans += T[i];
}こんな感じで解きました。
C – Snack
高橋君はパーティを企画しています。
パーティーでは参加者に 1 人 1 個以上のお菓子を配る予定です。
高橋君は参加者の人数が A 人か B 人のどちらかになるだろうという予想を立てました。
どちらの場合でも均等に配りきることができるようなお菓子の個数の最小値を求めてくだい。
ただし、 1 個のお菓子を分割して複数人で分けることはできないものとします。
AでもBでも割り切れる最小の数を求める問題です。つまりABの最小公倍数(LCM)を求めればこれが答えです。
[C#] 最小公倍数(LCM)を求めるアルゴリズムと実装 │ Web備忘録
私はLCMを求めるコードをスニペットに入れているのですぐに実装できました。実装方法は上の記事にあります。
コードは以下のような感じです。
static void Main(string[] args)
{
// ..
var ans = Lcm(A, B);
Console.WriteLine(ans);
}
// ...
static long Lcm(long a, long b)
{
return a / Gcd(a, b) * b;
}
static long Gcd(long m, long n)
{
if (n == 0) return m;
return Gcd(n, m % n);
}D – Brick Break
N 個のレンガが横一列に並んでいます。
左から i (1≤i≤N) 番目のレンガには、整数 ai が書かれています。
あなたはこのうち N−1 個以下の任意のレンガを選んで砕くことができます。その結果、K 個のレンガが残っているとします。このとき、任意の整数 i (1≤i≤K) について、残っているレンガの中で左から i 番目のものに書かれた整数が i であるとき、すぬけさんは満足します。
すぬけさんが満足するために砕く必要のあるレンガの最小個数を出力してください。もし、どのように砕いてもそれが不可能な場合、代わりに -1 を出力してください。
制約
- 入力は全て整数である。
- 1≤N≤200000
- 1≤ai≤N
これは数列からいくつかの数を取り除いた(レンガを砕いた)後の状態が 1 2 3 ... みたいな連番になっているとよいということです。この連番を最も長くできるとき、取り除く数(レンガを砕く数)が最小になります。
左端からループしてみていき、1が見つかったら2を探す、2が見つかったら3を探す … として何個残すことができるか求めます。最終的に N-残す数 が答えになります。
var now = 1;
for (int i = 0; i < N; i++)
{
if (A[i] == now) now++;
}
if (now == 1)
{
Console.WriteLine(-1);
}
else
{
var ans = N - now + 1;
Console.WriteLine(ans);
}E – Double Factorial
解けなかったわけですが、以下のような問題でした。
0 以上の整数 n に対し、 f(n) を次のように定義します。
- f(n)=1 (n<2 のとき)
- f(n)=nf(n−2) (n≥2 のとき)
整数 N が与えられます。f(N) を 10 進法で表記した時に末尾に何個の 0 が続くかを求めてください。
制約
0≤N≤10^18
N*(N-2)*(N-2-2)*... みたいな計算をしたときに末尾に0が何個続くかという問題です。
例えば N=7 のとき 7*5*3*1 みたいに奇数の積で結果も奇数となるので、Nが奇数のときは答えが0になるのはわかりました。
制約的にも点数的にも愚直に計算ができないことは明らかなので何とかして数学的?に答えを求める必要がありそうなのですがその方法がわかりませんでした。
2の倍数と5の倍数に着目して2の倍数が明らかに多いので5の倍数に着目すればよいというところもわかったのですが、どうにもできませんでした。
AtCoder ABC 148 E – Double Factorial (500 点) – けんちょんの競プロ精進記録
上の解説がすごくわかりやすくて理解できました。
10*8*6*4*2 = (2^5)*(5*4*3*2*1) という式変形は絶対思いつかないですね。末尾に0が何個付くかという問題は受験数学でよく見るらしいし、2重階乗という名前も知らなかったので圧倒的経験不足・勉強不足が感じられる問題でした。
今回のE問題も上の2問みたいな数学的教養を問われる問題はやっぱり苦手だと思いました。Difficulty的にもっと難しい前回のD問題とかのほうが自分的にはやりやすかったです。
というより対策しやすいし自分の実力アップが確認できるから好きです。
数学問題が苦手なのは傾向と対策が立てにくいからというのもあります。とはいえもっと解けるようになりたいので、年末年始で高校数学をちょっと復習しようと思いました。それでこんな感じの問題が解けるようになるのか不明ですが…。
以上。
