AtCoder Beginner Contest 152お疲れ様でした!
公式ページ
今回の自分の書いたコードはこちら
結果はA-DまでAC、EがWAでした。
以下簡単に解説します。
問題A
引数のNとMを比較する問題。
同じ場合はYes
、違う場合はNo
を出力すればOK
問題B
aをb回繰り返した文字列とbをa回繰り返した文字列のどちらが辞書順ではやいかを出力する問題。
辞書順なので、aとbのうち小さいほうが先です。
aとbの小さい方をaとbの大きい方ぶん繰り返した文字列を出力できたらACです。
問題C
説明文はちょっと難しく書いてありますが、結局数列で最小値が何回更新されたかを答えればOKです。
4, 5, 2, 3, 1
上記だと太字になっている数字の数3が正解になります。
問題D
N以下の数字の中で、
- Aの先頭の数字 = Bの末尾の数字
- Bの先頭の数字 = Aの末尾の数字
のどちらも満たす数字の組み合わせが何通りあるかを答える問題です。
Nの数字の数的に二重ループしていると間に合わないと思ったので、
- 最初にループして先頭の数字と末尾の数字のMapをつくる
- 二回目のループで条件にマッチする数をとってきて足し合わせる
としました。計算量的に間に合わないから方針変えなきゃって気づけたのは個人的にうれしいポイントでした。
問題E
どのような i,j についても AiBi=AjBjが成り立つ。
つまり、最小公倍数を求めてAiで割ってBiを求める問題。
答えはさらにそれを足し合わせて出力しなさいとのこと。
方針を決める部分までは分かり、最近勉強した逆元使えばAiで割れるやん!というところまではよかったが、
大きい数の場合にうまく動かず。原因まで特定もできました。
最小公倍数を計算する際、大きい数になり1000000007で一度割ってしまうと最小公倍数を正しく求められなくなるというものでした。
色々考えた結果解消できず。。
解説にもある最小公倍数を素因数分解した形で保持するというのも考えたのですが、実力不足でコードにできませんでした。
(ちょっとまだどうすればいいかイメージも出来ていないので、平日仕事終わりにまた考えてみます。。)
問題F
問題Eがもうちょっとでできる気がしたので手を付けれていないです。。
レーティングは897→956。最高更新です!
D問題までは25分とサクサクできて、成長も感じれたのですが
E問題の逆元使うところまでは思いつけたのに、あと一歩及ばずでとても悔しいです。。
次こそは学びをきちんと形にしたいです・・・