AtCoderの良解答からみるプログラミングのテクニック03(ビギナー向け) C++
このシリーズ第一回(まだ見てないならここをクリックしてからのほうが良いです)
前回の記事
drken(けんちょん)さんの記事の進行で進みます。
こんにちは、今回も学んだことを共有させていただきます。
途中に他の方のコードを引用しますが、そのコードの著作権はそのコードを書いた方が有しています。
元のコードが見たい場合は
今回から第九回までは問題名 提出#〇〇〇〇〇
で検索をすれば見ることができます。提出#〇〇〇〇〇
のかたちで紹介させていただきます。が十回目からはリンクを張ることにしました。検索してもでず、地道に番号から探さないと見つけられないみたいだからです。
※注 スマホだとコードは見にくいのでPCモードかPCで見たほうが良いです。
At Corder で見つけた解答から得たもの
・ABC068_B
提出 #4392940より
//入力 int n; cin >> n; //処理 int ans = log2(n); //出力 cout << pow(2,ans) << ENT; return 0;
log使うって発想ですかね、ここから学んだのは。処理ブロックを見ると、logを使ってint型の変数ansを初期化しているのが分かります。そのためlog2(7)だったらlog2(4)と同値になるのでそれを利用して出力するという解法。覚えておきたいですね。 コメントで区分けしているのも面白いと思った。
提出 #4387441より
int n, i; std::cin >> n; for(i = 1;i <= n;i = i * 2){} std::cout << i / 2; return 0;
これは解説と同じロジックの解法ですね。ですが、もう一つ同じロジックの解法があって、友達のコードから
int main(){ int a; cin >> a; if(a >= 64){ cout << 64 << endl; } else if(a >= 32){ cout << 32 << endl; } else if(a >= 16){ cout << 16 << endl; } else if(a >= 8){ cout << 8 << endl; } else if(a >= 4){ cout << 4 << endl; } else if(a >= 2){ cout << 2 << endl; } else{ cout << 1 << endl; } }
という泥臭いといえば失礼かもしれませんがこのような解答もありました。しかし、これはテニスやったことがある人は顧問の先生にも言われたと思うのですが、粘れだとか泥臭くやれだとか、勝つため(今回なら問題を解くため)にできることを例え周りからかっこいい勝ち方だと思われなくてもやれなんて言われたことがある自分からするとハッとさせられる解答だなぁと思いました。 ださかっこいいというか。解くことに貪欲な姿勢がイカしてるというか。 そういえば、受験でも言われた気がする。確率は最後の手段で泥臭くやってもいい。受かるのが大事。みたいな。 ちなみに自分はこう解きました↓
signed main() { int n; cin >> n; vector<int> v1, copyv1; vector<int> count(n, 0); for (int i = 1; i < n+1; i++) { v1.push_back(i); } copyv1 = v1; for (int i = 0; i < n; i++) { int j = 0; while(true){ if(v1[i]%2 == 1) break; else { v1[i]/=2; ++j; } count[i] = j; } } auto maxitr = max_element(count.begin(), count.end()); int maxindex = distance(count.begin(), maxitr); cout << copyv1[maxindex] << endl; return 0; }
まぁ、なんでこうなったかというと、一番最初にAtCorderやるならこれを読めということで紹介した記事に「081_Bに似てます」って書いてたんで似た解き方をしようとした結果ですね。 で、多分最後に紹介するこれに似た解答を一番見かけた気がする。まぁ、実質二番目に紹介したのと変わらないけど。ちなみにこれは私が書いた別解です。
int main(){ int n, ans; cin >> n; for(int i=0; i<10; i++){ if(pow(2, i) > n){ ans = pow(2, i-1); break; } } cout << ans << endl; return 0; }
今回は自分の解答のコスパが悪い(コード書く時間が長いということ)ので、別解の方が参考になると思います。
おわり
以上!ABC 068の解説でしたー。
次回はここをクリック