こんにちは,ツイッターで絡んでる人が書いているブログを見て僕もブログ書きたいなと思ったので書きます。
できれば継続したい。
競プロの話から。
二週間前の日曜日、
第一回日本最強プログラマー学生選手権決勝(オープンコンテスト) - AtCoder
こちらにイベント参加者枠として参加しました。
とはいっても上位500に入れたわけではなく、参加者が集まらないから500より下の人も招待される。といった感じですね。
前日に参加者をTwitterでフォローしまくったのですがあまりお話しすることはできませんでした。
そりゃまあ仕方ないよね。
まあ、0ってわけではないです。楽しかったです。生ハムおいしかったです。
そして先週、
AtCoder Grand Contest 039 - AtCoder
こちらのコンテストでA完しまして、ついに茶色コーダーになりました!うれしいね。
最近はAtCoder Problemsを見て、difficulty400くらいの問題を解くようにしています。
今日はAGC018 - A を解いていたんですが、無理of無理からの30分前くらいにACした。(解説聞いたんですけど実装は自分で…)
ACした後も、「どうして最大公約数の倍数ならいけるんだ??」と悩み続けていたのですが、
A1からAnのすべての数は最大公約数×(なにか)であらわされていて、KがA1からAnのいずれかなら、最大公約数の倍数だから作れる(っていうかもとからある)。そして、kがA1~An出ないのなら、最大公約数の倍数であるAi(iは1からn)のどれかから最大公約数の数を引いていけば作れる。ってことだったんですね。(僕が分かっているので読んでいる人は分からなくてもいい)
まあ前提として、Kは配列A(A1,A2...Anのこと)最大の数より小さくなくちゃいけないんですけど。
で、僕が自慢したいのは、最大公約数を求めるコードを実装できたよってことです。
どうやってブログにコード貼るんだろ
~ int gcd_2(int a , int b){ int A = max(a,b); //大きいほう int B = min(a,b);//小さいほう int c =-1; int ans = 1 ; while(c!=0){ c = A % B; if(c==0){//Bが最大公約数 ans = B; break; } else{//B大公約数ではないので,AをBに,BをCにしてもう一度 A = B; B = c; } } return ans;//cが最大公約数 } int main(){ int n,k ; cin >> n>>k ; vector<int> A(n); rep(i,n) cin>>A[i] int tmpGcd = A[0]; int M =A[0]; for(int i = 0 ;i < n ; i++){//GCDのGETとついでに最大の数も入手しとくか tmpGcd = gcd_2(tmpGcd,A[i]); M = max(M,A[i]); } } ~
配列を引数にしてint main()の外で求めさせてもよかったんですけど、配列を引数にするのなれてなかったので許して。
これはあれね、ただ貼ってるだだからね。これ参考にするとかやめたほうがいいよ。
現段階でも改善の余地見えてるもん。
ただ自慢したかっただけ。
ここまではブログ。以下は書きなぐり(ほんとか?)
タイトル、北風と太陽とPCとけーぷろと編入と
とありますが、今北風と太陽と競プロの部分が終わりました。
北風と太陽はただ入れたかっただけだから気にしないで。
はい、PC。ココちゃんのことですね。
ぶっこわれました。
…
編入
考えてます
以上
あ、最近していることは、線形代数、金のセンテンス(TOEIC英単語)、螺旋本(アルゴリズムとデータ構造)、C++のおべんきょ、AtCoderです。
線形代数、分かる!楽しい!→ワカラン
金のセンテンス →結構時間かかるなあ 二週間で一周したい
螺旋本 → ポインタと構造体を前提知識に含む →無理やん、どうしよ。せや、C++のおべんきょしよ。
c++ → 基礎から分かるC++ みたいな本買った →7章の文字列のとこまでやった。
AtCoder →まあ ぼちぼち。