読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#007

ABC

- A問題「植木算」

(http://abc007.contest.atcoder.jp/tasks/abc007_1)

問題概要:
N本の木が一直線にあってその間がいくつあるかという問題です。

解法:
N-1を出力して終わりです。

ソースコード:



- B問題「辞書式順序」

(http://abc007.contest.atcoder.jp/tasks/abc007_2)

問題概要:
ある文字列を与えられ、それよりも辞書順で小さい文字列をどれか一つ出力すればよい。

解法:
全ての辞書順文字列の中で最小は"a"なのでこれを出力すればいい。注意点として"a"が入力で与えられたときはそれよりも小さい文字列が存在しないので-1を出力する。

ソースコード:



- C問題「幅優先探索

(http://abc007.contest.atcoder.jp/tasks/abc007_3)

問題概要:
幅優先探索をする問題です。
結構手順が書いてあってやさしい。

解法:
現在のマスからの四方の相対距離を配列にまとめると実装が楽です。
dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
また、到達不可能なマスを-1として迷路の外側の到達不可能なマスで囲ってしまえばif文が減らせて楽になります。
あとは一般的なBFSをキューを使って実現するだけです。

ソースコード:



- D問題「禁止された数字」

(http://abc007.contest.atcoder.jp/tasks/abc007_4)

問題概要:
A≤N≤Bを満たすNのうち、4と9が含まれるものの数を出力しろという問題です。
この形式の問題はエレベーターというタイトルの問題で闇に落ちたので苦手です。

解法:
全探索をしようとするとnを桁数としたときにO(n*10^n)となってしまい10^18は通常の計算機では間に合いません。
ここで、4と9が含まれない数字の個数に着目します。MからNのうち4と9が含まれない数字の個数を[M,N]と表すと、
[1,B]-[1,A-1]=[A,B]という式が成り立つことがわかります。
また、これを少し変更して[A,B]=[0,B]-[0,A-1]とします。
これで0からNまでの4から9の含まれない数字の個数を計算する関数を作れば解が出力できることがわかります。
[0,N]について考えましょう。
Nが10進表記でABCDE,,,という形だとします。(0≤A,B,C,D,E≤9)
0≤M≤Nを満たすM=abcdeについて、(0≤A,B,C,D,E≤9)
a<Aのときbcdeの組み合わせは8^4通り(4と9を除いた8通りの数字が四桁)
a=Aのかつb<Bのとき、8^3通り、、、
となるためdp[ABCD]=(A-1以下の4と9を除いた数の個数)*8^|BCDE|+dp[BCDE]というように再帰的に求められます。
したがって繰り返しは桁数分のみでいいので最大18回のループで終了します。
ソースコード: