notepad

いろいろ書くメモ帳

ABC007を解いた

今回はAtCoder Beginner Contest 007を解きました.公式解説はこちら

桁DPにだいぶ苦戦しました.

A 植木算

自力完答
入力された数値から1引くだけ.簡単.

B 辞書式順序

自力完答
次の3つに場合分けすればできる.

  1. 2文字以上なら末尾を削って出力
  2. 1文字のみで"a"以外なら,1つ前のアルファベットを出力
  3. "a"のみなら"-1"を出力

C 幅優先探索

自力完答
問題文に載っているとおりに幅優先探索のプログラムを書けばできるが,実装に少し手間取った. 探索の問題は無限ループとの戦いになる.

D 禁止された数字

自力で30点.解説見て100点
4と9を含む数値の総数を答える問題.何も考えずに,数値を文字列に変換して4と9を含む数値の数を数えるというアルゴリズムを書いても,最大値が1018と大きいためTLEとなって30点しかもらえない. 公式解説を読むと,桁DPで解く方法と8進数変換でごにょごにょする方法の2つが載っていたが,せっかくなので(?)桁DPで実装することにした.

桁DPは簡単にいえば,N以下の数値の状態を「桁数」と「N未満かどうか」で表すものである. この桁DPを使って実装したプログラムがこちら.

このプログラムでは,数値がN未満かどうか(選ぶ数字が制限されるか)によって次のような処理を行なっている.

  • i桁目の時点で選ぶ数字が制限されていない場合
    • i+1桁目は{0, 1, 2, 3, 5, 6, 7, 8}の8つの数字を選ぶことができる
  • i桁目の時点で選ぶ数字が制限されている場合
    • Nのi+1桁目と同じ数字を選ぶときは,その次の桁も制限され続ける
    • Nのi+1桁目より小さい数字を選ぶときは,その次の桁は制限されない

理解できるまで時間がかかったが,たぶんこんな感じの処理を行うのが桁DPだと思う.

ちなみに,今回のプログラムは4と9を含まない数値の総数を求めるものになっているが,問題通り4か9を含む数値の総数を直接求めることもできる. その場合は,DPテーブルに「4または9が選ばれているか」を表す状態を追加する必要がある.(たぶん)

感想

D問題を自力で解けるようになるのは何時頃だろうか…