見出し画像

ABC161【D問題の復習】法則に気がつかなくて困った

4月4日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 161」に参加した。

【今回の結果】
     順位:5570 位(参加者:約 9922 名 上位 56 %くらい)
    レート:651(前回:666 前回比:-15)
パフォーマンス:506(前回:227)

前回のnoteではもうちょっと練習をつんでから臨みたいと言っていたが、あまり練習ができずに参加だったので、半ばレートが下がるなぁと思っていたらその通りになった。全6問出題され、A、B、C問題はACできた。B問題では割り算を雑に扱ってしまい3WA。あい変わらずである。

今回は、時間を60分くらいを残してD問題に進んだが、ルンルン数の生成方法を思いつくことができず終わってしまった。そこで、D問題の復習する。

【D問題の復習】

問題文は以下のリンクをご確認ください。


この問題はルンルン数がきちんと生成することだけがポイント。
解説PDFより動画解説の方がわかりやすかった。

1桁のルンルン数は、1, 2, 3, 4, 5, 6, 7, 8, 9
2桁のルンルン数は、10, 11, 12, 21, 22, 23, 32, 33, 34, ..., 98, 99

となり、1桁のルンルン数 1 について、0(= 1 - 1), 1, 2(= 1 + 1)を末尾にそれぞれ加えると、

10, 11, 12

となる。また、1桁のルンルン数 2 について、1(= 2 - 1), 2, 3(= 2 + 1)を末尾にそれぞれ加えると、

21, 22, 23

となる。すなわち、加える前の末尾の数から、付け加える数を決めることができる。9の場合は、10(= 9 + 1) を末尾に加えることができないことに注意する。

以上の考えをベースすれば、1桁のルンルン数、2桁のルンルン数...とルンルン数を生成できる。

なるほど。

2桁のルンルン数はまだ手書きとかでも列挙できる数だったので、実際に列挙して何か法則はないものかと考えたが、思いつくことができなかったなぁ。これも練習量が足らないのだろうな。

動画解説を見ながら、ACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;

int main() {

 int K;
 cin >> K;

 vector<long long> a;
 for (int i = 1; i < 10; i++){
   a.push_back(i);
 }

 bool flg = true;
 while (flg) {

   if (K <= a.size()) {
     cout << a[K - 1] << endl;
     return 0;
   }

   K -= a.size();
   vector<long long> old;
   swap(old, a);

   for (int i = 0; i < old.size(); i++) {
     for (int j = -1; j < 2; j++) {
       int d = old[i] % 10 + j;
       if (d < 0 || 9 < d) {
         continue;
       }
       long long r = old[i] * 10 + d;
       a.push_back(r);
     }
   }

 }

 return 0;
}

でもこのコードの

 K -= a.size();
 vector<long long> old;
 swap(old, a);

この3行が難しい。なかなか思いつかんなぁ。今回も動画解説見て「すごいなぁ」と感心していた。

AtCoderを始めたときはJavaで参加していて、途中でC++に変えた。ABCの問題をJavaで埋めていたのをC++でやり直していたのだが、やっとABCのC問題をすべてC++で埋めた。これでD問題の練習に進める。引き続き、がんばろう。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ありがとうございます!
1
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。

この記事が入っているマガジン

AtCoder参加記録
AtCoder参加記録
  • 25本

AtCoderのABC等に参加した記録です。

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。