AtCoder 142
こんにちは!
今回はAtCoder 142 ABCに参加しました。
ブログ始める前から2回ほどコンテストには参加していて、現在問題をACできるように勉強しているところです。
過去2回では、だいたいC問題までACして、Dでわからないなーって感じでした。
と、いうことは今回は。。。
A - Odds of Oddness
整数 が与えられます。
高橋君は、 以下の正整数の中から等確率で つを選んで とします。
このとき、 が奇数である確率を答えてください
A問題は特に難しくないですね。
奇数の数出して、全体から割ればいいだけでした
すぐにACいただきました
B - Roller Coaster。
高橋君の仲間たちは 人で遊園地に遊びにいきました。
遊園地の一番人気のジェットコースターに乗るためには、身長が cm以上必要です。
高橋君の 番目の仲間の身長は cm です。
高橋君の仲間たちのうち、一番人気のジェットコースターに乗ることができる人の数を求めてください。
B問題も難なくいけました。
N人の中で身長がK以上の人をカウントするだけですね。
ACです。
C - Go to School
高橋くんは 人の生徒たちのいるクラスの担当教師です。
生徒たちには から までの出席番号が重複なく割り当てられています。
今日は全ての生徒たちが相異なるタイミングで登校しました。
高橋くんは、出席番号 の生徒が登校した時点で、教室に 人の生徒たちがいたことを記録しています(出席番号 の生徒を含む)。
記録された情報を元に、生徒たちの登校した順番を復元してください。
ここから難しくなっていきます。
ちょっと時間かかってしまったんですが、よく考えたらこれでいいんじゃね?って感じでいけました。
ans[a[i]-1] = i+1
これに気づいたときは気持ちよかった。(笑)
無事ACです。
D - Disjoint Set of Common Divisors
正整数 が与えられます。
と の正の公約数の中からいくつかを選びます。
ただし、選んだ整数の中のどの異なる つの整数についても互いに素でなければなりません。
最大でいくつ選べるでしょうか。
A、Bの公約数から選んだ二つが互いに素になる。。。
なるほど
とりあえず、公約数なんで最大公約数の公約数だせばいいかなーと思い、最大公約数を考え実装。
その要素二つを選んで互いに素かどうか、なんですが二つ選ぶってところで、forを二回使いたいですけど、だめなやつですよね。
なので、別のアプローチですねー
で、考え付いたのが公約数を素数だけにすればいいのでは??ということ。
そこで、素因数分解する関数を作成し、最大公約数を素因数分解。最後に重複をなくしてその数を数えたら終わりです!
AC
いぇーい!!!
時間内にDまで解けたのは初めてでしたのでとてもうれしかったです。
ここで時間終了しました。
次回も参加予定なので、Dを解けるように練習していきたいですね。
そして、E、Fも。。。
これからも成長していきたいです。
ではでは(^▽^)/
集合知プログラミング① 読んでみたまとめ
1章 集合知への招待
1.1 集合知とは何か
それらを利用し、個々人が知らなかかった統計的な結論を引き出す。
つまり、独立した貢献者たちから新たな結論を作りあげることである。
1.2 機械学習とは何か
データを分析し、将来現れるデータを予測する。
でたらめなデータでない限り、パターンを含んでいるので、このパターンを機械によって一般化する。
1.3 機械学習の限界
1.4 実生活における例
ページのランキングを出すためにWebリンクを使用するだけでなく、どのような人が広告をクリックしたかという情報も集めている。
・Amazon,Netfrix
人びとが購入したりレンタルした情報を利用して似ている人々や類似した商品を決定する。
1.5 学習アルゴリズムのその他の使用
シークエンシングとスクリーニング技術の発展により、DNA配列、たんぱく質の構造、化合物スクリーニング、RNA発現など。
生物学的な過程に対する理解を増すパターンを見つける
・クレジット詐欺の発見
ニューラルネットワークで、取引や現金の動きが不適切か確かめる
・マシンビジョン
侵入者を自動的に発見したり、自動車を特定したり、顔を認識する
教師なし学習を使用されている
・製品のマーケティング
顧客からデータを入手するのが簡単になったので、将来の流行について予測したり
・サプライチェーン
製品の需要を正確に予測することでお金を節約する
最適化と学習の技術がよく用いられる
・株式市場の分析
パターンを発見する
・国防
世界中の政府による膨大な量のデータからパターンを発見する
そして、それらを危険と関連させる
第一章をまとめるとこんな感じ
機械学習が重点的に使われている例は様々であり、ビッグデータであるからこそ機械学習にまかせるのがいい。
そして、インターネットの世界では情報が常に追加されていること
なかなか面白く興味深い内容でした!
随時更新していきます!
ではでは(^▽^)/