AtCoderの良解答からみるプログラミングのテクニック06(ビギナー向け) C++
このシリーズ第一回
hajimekata-nyumon-donyu.hatenablog.com
前回
hajimekata-nyumon-donyu.hatenablog.com
drken(けんちょん)さんの記事の進行で進みます。
こんにちは、今回も学んだことを共有させていただきます。
途中に他の方のコードを引用しますが、そのコードの著作権はそのコードを書いた方が有しています。
元のコードが見たい場合は
今回から第九回までは問題名 提出#〇〇〇〇〇
で検索をすれば見ることができます。提出#〇〇〇〇〇
のかたちで紹介させていただきます。が十回目からはリンクを張ることにしました。検索してもでず、地道に番号から探さないと見つけられないみたいだからです。
※注 スマホだとコードは見にくいのでPCモードかPCで見たほうが良いです。
At Corder で見つけた解答から得たもの
・ABC090_B
提出 #4568846より
signed main(void) { int a, b, cnt = 0; string s, front, end; cin >> a >> b; REP(i, a, b + 1) { s = to_string(i); front = s.substr(0, 2); end = s.substr(3, 2); reverse(all(end)); if (front == end) { cnt++; } } cout << cnt << endl; return 0; }
前回学んだto_string( )が使われていますね。忘れた方は前回の記事で復習できます。 が、簡単に説明を書いておきますね。 to_string()は数字を引数とする関数です。to_string('数字')と書きます。 すると、引数を文字列に直した結果を戻り値として返してくれんでしたね。 そして、どうやら見慣れないsubstr( )というものがありますね。 これは以下のように書くことができます。
const std::string s = "hello"; // 2番目から3要素だけ抜き出した部分文字列を取得する { std::string result = s.substr(2, 3); std::cout << result << std::endl; //出力結果 ‘llo‘
substr();は第一引数に‘‘‘どこから‘‘‘という情報を与えます。次に、第二引数で‘‘‘何要素文‘‘‘抜き出すかという情報を与えます。そうすることで、今回の例の場合hello
の二番目の要素であるl(エル)
から3文字分抜き出した部分文字列を取得できます。
次に、youtubeの解説と同じ解法を紹介します。
signed main(){ int a, b; cin >> a >> b; int cnt = 0; FOR(i,1,10){ REP(j,10){ REP(k,10){ int x = 10000*i+1000*j+100*k+10*j+i; if(x >= a and x <= b) ++cnt; } } } cout << cnt << endl; return 0; }
これは10001以上99999以下の数字の中にあるA以上B以下という条件を満たす回文が存在するならカウント変数をインクリメントしてくださいね。というコードです。 10000も問の条件に含まれますが回文でないことは自明なので10001~99999の間で探索できます。 ちなみに、
int x = 10000*i+1000*j+100*k+10*j+i;
これは回文を表すことは自明ですよね。
提出 #4581500より
int main() { int A, B; cin >> A >> B; int ans = 0; for (int i = A; i <= B; i++) { string s; s = to_string(i); if (s[0] == s[4] && s[1] == s[3]) ans++; } cout << ans << endl; return 0; }
これは、回文であれば整数ijkmn(i,j,k,l,m,nはそれぞれ桁を表す。例12345)ではなく、ijkji(例12321)のようになっていることを利用しています。先程の解答に近いですね。 to_string( )によってint型をstring型に変換してやって0番目の要素と4番目の要素が等しく1番目と3番目の要素が等しいならば回文である。 というロジックですね。 次は僕の解答です。先程の解答を整数のまま再現した場合と考えていいです。はじめに、関数を定義しています。この関数の戻り値は回文の個数。つまり解です。
int kai(int i){ int cnt = 0; int one = i % 10; //一桁目 int ten = (i / 10)%10; //二桁目 int tho = (i / 1000)%10; //三桁目 int man = (i / 10000); //四桁目 if(one == man && ten == tho) //一桁目==四桁目 && 二桁目==三桁目 ++cnt; return cnt; } signed main() { int a,b; cin >> a >> b; int ans = 0; FOR(i, a, b+1) ans += kai(i); cout << ans; return 0; }
このシリーズ第5回、つまり前回の時に学んだ10進法表記が分かっていれば理解できるコードですね。一桁目,二桁目,三桁目,四桁目をそれぞれ求めてやって、それが回文の性質である、ijkjiを満たしているかを判別するというコードです。 10進法表記の復習をしましょう。 整数の10進法表記の処理として、一桁ずつ処理をするなら%10をすることで最下位桁を着目することができ、元の整数を/=10することで着目している桁を一つ左にずらせるんでしたね。
さいごに
今回はto_string()と10進法表記の復習ができました。さらに、新しいこととしてsubstr( );の使い方を解説しました。これで部分文字列の問題が一部解けるようになったはずです。 以上!ABC090の解説でしたー。