公式

B - 321-like Checker 解説 by physics0523


初心者の方へ
  • プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。
  • また、プログラミングコンテストの問題に慣れていない方は、 AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。
  • C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。

方針1: \(N\) を各桁に分解する

以下の方法で \(N\) を各桁に分解できます。

  • 最初、 \(D=[]\) とする。
  • \(N>0\) である間、以下を繰り返す。
    • \(D\) の末尾に \(N\)\(10\) で割った余りを追加する。
    • その後、 \(N\) を ( \(N\)\(10\) で割った商 ) に置き換える。
  • 最後に、 \(D\) 全体を反転する。

例えば、 \(N=321\) の場合以下のような動作になります。

  • \(D = []\) から始める。
  • \(321>0\) なので、 \(D\) の末尾に \(1\) を追加し、 \(N\)\(32\) に置き換える。 \(D=[1]\) となる。
  • \(32>0\) なので、 \(D\) の末尾に \(2\) を追加し、 \(N\)\(3\) に置き換える。 \(D=[1,2]\) となる。
  • \(3>0\) なので、 \(D\) の末尾に \(3\) を追加し、 \(N\)\(0\) に置き換える。 \(D=[1,2,3]\) となる。
  • \(N=0\) となったので、ここで繰り返しを終了する。
  • 最後に \(D\) を反転し、 \(D=[3,2,1]\) を得る。

この \(D\) を用いて問題文中の条件をループを使って判定することにより、この問題を解くことができます。
なお、条件の判定は

  • 全ての \(i\) について ( \(i\) 桁目 ) \(>\) ( \(i+1\) 桁目 ) なら Yes

を、

  • あるの \(i\) について ( \(i\) 桁目 ) \(\le\) ( \(i+1\) 桁目 ) なら No

に変形するとよいです。

実装例 (Python):

N = int(input())
D = []
while N>0:
    D.append(N%10)
    N //= 10
D.reverse()

for i in range(1,len(D)):
    if D[i-1]<=D[i]:
        print("No")
        exit()

print("Yes")


方針2: \(N\) を文字列として受け取る

何らかの方法で \(N\) を文字列として受け取れば、その文字列 \(i\) 文字目が \(N\) の上から \(i\) 桁目になります。
なので、その文字列を使って判定を行うと \(N\) を各桁に分解する必要がなくなります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  for(int i=1;i<s.size();i++){
    if(s[i-1]<=s[i]){
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
  return 0;
}

投稿日時:
最終更新: