AtCoder 142 - shaknownのブログ

こんにちは！

今回はAtCoder 142 ABCに参加しました。

ブログ始める前から２回ほどコンテストには参加していて、現在問題をACできるように勉強しているところです。

過去２回では、だいたいC問題までACして、Dでわからないなーって感じでした。

と、いうことは今回は。。。

A - Odds of Oddness

整数 $N$ が与えられます。

高橋君は、 $N$ 以下の正整数の中から等確率で $1$ つを選んで $a$ とします。

このとき、 $a$ が奇数である確率を答えてください

A問題は特に難しくないですね。

奇数の数出して、全体から割ればいいだけでした

すぐにACいただきました

B - Roller Coaster。

高橋君の仲間たちは $N$ 人で遊園地に遊びにいきました。

遊園地の一番人気のジェットコースターに乗るためには、身長が $K$ cm以上必要です。

高橋君の $i$ 番目の仲間の身長は $h_{i}$ cm です。

高橋君の仲間たちのうち、一番人気のジェットコースターに乗ることができる人の数を求めてください。

B問題も難なくいけました。

N人の中で身長がK以上の人をカウントするだけですね。

ACです。

C - Go to School

高橋くんは $N$ 人の生徒たちのいるクラスの担当教師です。

生徒たちには $1$ から $N$ までの出席番号が重複なく割り当てられています。

今日は全ての生徒たちが相異なるタイミングで登校しました。

高橋くんは、出席番号 $i$ の生徒が登校した時点で、教室に $A_{i}$ 人の生徒たちがいたことを記録しています(出席番号 $i$ の生徒を含む)。

記録された情報を元に、生徒たちの登校した順番を復元してください。

ここから難しくなっていきます。

ちょっと時間かかってしまったんですが、よく考えたらこれでいいんじゃね？って感じでいけました。

ans[a[i]-1] = i+1

これに気づいたときは気持ちよかった。（笑）

無事ACです。

D - Disjoint Set of Common Divisors

正整数 $A, B$ が与えられます。

$A$ と $B$ の正の公約数の中からいくつかを選びます。

ただし、選んだ整数の中のどの異なる $2$ つの整数についても互いに素でなければなりません。

最大でいくつ選べるでしょうか。

A、Bの公約数から選んだ二つが互いに素になる。。。

なるほど

とりあえず、公約数なんで最大公約数の公約数だせばいいかなーと思い、最大公約数を考え実装。

その要素二つを選んで互いに素かどうか、なんですが二つ選ぶってところで、forを二回使いたいですけど、だめなやつですよね。

なので、別のアプローチですねー

で、考え付いたのが公約数を素数だけにすればいいのでは？？ということ。

そこで、素因数分解する関数を作成し、最大公約数を素因数分解。最後に重複をなくしてその数を数えたら終わりです！

いぇーい！！！

時間内にDまで解けたのは初めてでしたのでとてもうれしかったです。

ここで時間終了しました。

次回も参加予定なので、Dを解けるように練習していきたいですね。

そして、E、Fも。。。

これからも成長していきたいです。

ではでは(^▽^)/