だらだら競プロ適当解説：AtCoder Beginner Contest 007
AtCoder Beginner Contestの第7回。
なんやかんやで月一更新。
ゆるくいこう。
総評
全体的に全部難しくなってない？
特に解説付きとはいえC問題で幅優先探索は結構ハードル上がった感がある。
Cは単純実装力、Dも実装力よりではあるが思考問題でもある。
知識問題はほとんどないが、全体的に重めになったように感じる。
A - 植木算
ありがちなA問題。
略解
int n; cin >> n; cout << n - 1 << endl;
ポイント
おそらくほとんど解説は必要ない。
木の数 - 1が間の数になるので入出力ができれば事足りる問題。
B - 辞書式順序
問題がクッソ長くて読みたくない。
嗚呼、活字離れ世代になんと過酷な問題なこと乎
略解
string A; cin >> A; // aが一番小さいのでaの時は不可能. if (A == "a") { cout << -1 << endl; } else// それ以外の時は一番小さいaを返せばいいはず. { cout << "a" << endl; }
ポイント
問題文をすごい簡単に要約すると、なんでもいいので自分より辞書的に早いものを返せという問題。
なんでもいいというので楽して解くと、"a"の時はなし、それ以外は”a”を返せばよい。
このあたりはヒントっぽいものが例に載っているのでそれに気が付ければすぐ解けたかもしれない。
これも知識的には文字の入出力ができれば十分なので比較的優しい問題ではある。
もちろん問題文がやたらと長く、難解なのでそれを読み解ければという話であるが。
C - 幅優先探索
問題名がもう答えです。本当にありがとうございました。
略解
char Map[50][50];// マップ情報. int Memo[50][50];// 歩数情報. pair<int, int> s, g; int R, C; queue<pair<int, int>> pos;// 今いる場所. // 入力. cin >> R >> C; cin >> s.first >> s.second; cin >> g.first >> g.second; // indexのずれを整えよう. s.first = s.first - 1; s.second = s.second - 1; g.first = g.first - 1; g.second = g.second - 1; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { cin >> Map[i][j]; Memo[i][j] = INF;//ついでに初期化. } } // 初期位置は距離0に. Memo[s.first][s.second] = 0; pos.push(s);// スタート地点を登録. // 探索. while (!pos.empty())// 空になるまで. { // 上下左右に確認. int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1, -1 }; // キューの一番上を見て今の場所に. pair<int, int> nowpos = pos.front(); pos.pop();// ちゃんと取り出しておく. for (int i = 0; i < 4; i++) { pair<int, int> nextpos(nowpos.first + dy[i], nowpos.second + dx[i]); if (Map[nextpos.first][nextpos.second] == '#') { // 壁なのでこれ以降探索しない. continue; } if (Memo[nextpos.first][nextpos.second] != INF) { // 踏破済みなのでこれ以降探索しない. continue; } // 歩数をメモ. 前の歩数+1でいいはず. Memo[nextpos.first][nextpos.second] = Memo[nowpos.first][nowpos.second] + 1; // 壁でも踏破済みでもないのでキューに詰める. pos.push(nextpos); } } // ゴール位置の歩数を出力. cout << Memo[g.first][g.second] << endl;
ポイント
問題文に書かれた幅優先探索について理解できればおおよそ解けたも同然である。
xyの地点が与えられたとき、C++の場合は基本的にはpair
スタート地点をキューに入れ、そこから上下左右に進み、それぞれをキューに入れていき、動けなくなるまで続ければよい。
上下左右の確認は上記、dxdyの変数とforを使うと比較的容易い。
気を付ける点は一度通った場所は二度通らないことである。ちゃんと何らかの方法でメモしておこう。
また、何歩歩いたかの情報もメモする必要がある。
今回はメモ用の2次元配列を用意したが、キューを複数使って歩数をメモする方法もある。
queue<pair<int, int>> pos[2]; int hosu=0; // 探索. while (!pos[id].empty())// 空になるまで. { …… // キューの一番上を見て今の場所に. pair<int, int> nowpos = pos[id].front(); pos[id].pop();// ちゃんと取り出しておく. …… pos[(id+1 )%2].push();// 次のキューに入れておく. …… } hosu++; id=(id+1)%2;// 次のキューにする. // 両方のキューがからじゃなかったらもう一周やる.
この場合はゴールに着いた時点で操作を打ち切る必要がある。
ちょっと面倒なので今回はオススメしないが、このやり方の場合、距離ごとに探索の個数を制限したり調整したりできるのでマラソン系の問題では役に立つ考え方かもしれない。
D - 禁止された数字
とても難しい問題ですが私は解けました。
私は解けました。
略解
long long A, B; long long sumA = 0;//longlongはいらない気がするが. long long sumB = 0;//longlongはいらない気がするが. long long summemo[18];// ある桁の弾くべき数メモ. cin >> A >> B; // summemoをまず埋める. summemo[0] = 2;//１桁目は4と9の2つ. for (int i = 1; i < 18; i++) { // i+1桁目が4か9ならすべて、そうでないならsummemo[i-1]個ダメなはず. summemo[i] = 2 * pow(10, i) + 8 * summemo[i - 1]; // 例えば2桁なら 0[4,9] 1[4,9] … 4[0-9] … などなど. // 3桁でも同じ要領のはず. } // 0からAまでのダメ数字を確認. A -= 1; { string strA = std::to_string(A); int Adigit = strA.size();// Aの桁数. // 上の桁から処理していく. for (int i = Adigit; i > 0; i--) { // 一番最後の数字以外は単純にsummemoでいいはず. int num = strA.at(Adigit - i) - '0';// 今確認中の桁の数字. int sub = num - 1; // 一桁目だけ仕方ないので特殊処理. if (i == 1) { if (4 <= num) { sumA += 1; } if (9 <= num) { sumA += 1; } } else { if (num != 0) { sumA += num * summemo[i - 2];// 添え字が微妙にずれて分かりにくいが. } // 確認桁に4が含む場合. if (4 <= sub) { // メモ分はマイナス. sumA -= summemo[i - 2]; // 全部OKなので. sumA += (long long)pow(10, i - 1); } // 繰り越し桁が弾く数の場合. if (num == 4 || num == 9) { // それ以下の桁はすべて弾くので終了処理. sumA += A % (long long)pow(10, i - 1) + 1; // 456 なら 456 % 100 = 56 + 1 (0の分だけ足さないと……) break; } // 例えば336だった場合、0XX 1XX 2XX までは それぞれsummemo[3-2]個のはず. // 3の場合は 3[0-3]? になるので別処理が必要. // 最終桁の場合は端数を考えないといけないので次の桁の処理に. // 次のforループになると、 36の処理になって、0X 1X 2X 3[0-6] になる. } } } // 同様に0からBまでのダメ数字を確認. …… // 間のダメ数字の数なので. cout << sumB - sumA << endl;
ポイント
AからBまでというと難しくなるので、0からA-1と0からBを求めて引き算するというのが良さそうということに気が付けると良い。
これは以前の左上を起点とした長方形の面積を求めて要らない部分を足したり引いたりしてやりくりするというのに少し似ている。
一度に2つのことをやろうとすると困難なのでよほど速度を気にする場合を除いてはこういうやり方が良いと思う。
(この手の問題でよほど速度を必要とすることはまあない。時間が足りない場合は解き方がそもそも間違っていると考えたらいい)
例のごとく全探索するのは困難なので、どうにかまとめなくてはいけない。目をつける所は、どこなら纏められるかということである。
私は各桁ごとのダメ数字の数をはじめに求めてみた。
例えば1桁目なら4と9の2つ、2桁なら 0[4,9] 1[4,9] … 4[0-9] … 9[0-9]である。
これは前の桁の時のダメ数字の数が分かっていると上記に記載されているように比較的簡単に求めることができる。
新たな桁の数字が4や9の場合は後ろがどんな数字でもよい。そうでないなら前の桁の時のダメ数字の数と一致する。
良く分からなければ実際に数字を書いてみたりして規則性を確かめてみるのが良いと思う。
これで例えば99や999999といったキリのいい数字の場合は速やかに求められる。
99と100はダメ文字数が一緒なので、ここでは分かりやすく実質100のダメ数字の数として使っている。
さてこれで1000は速やかに数が数えられるとして問題になるのは1345とかの場合である。
端数分はどうあがいても特殊な処理で数えざるを得ない。
これは0[000-999]と1[000-345]にまず分ける。
0[000-999]は前述のように1000のダメ文字数が分かっているので即時解答できる。
1[000-345]はさらに10[00-99] 11[00-99] 12[00-99] 13[00-43]に分ける。
この時、前の３つは同様に100のダメ文字数の数からすぐ解ける。
そして同様に13[00-43]を分解する。
この作業の際に、4や9が現れたらその以降はすべてダメ文字と解釈できる。
例えば、512とかの場合、4[00-99]はメモされたダメ文字数ではなく、100個である。
上の桁から順番にこんなことをやっていくと最後には全部解けるという寸法である。
想定解は動的計画法を利用して探索するが、基本的な考え方は上記の解法からさほど遠くない。
要するに、端数か端数でないかを記録しておき、端数部分でないなら共通化できるはずということである。
競プロerは動的計画法を使いがち、私はパワーで上から解きがちという良く分かる違いはあるものの、根っこの部分はだいたい同じ発想である。
私は正直なところ言われないと動的計画法で書こうとは思わないだろうなという気がしている。もう少し動的計画法に対する信頼と視野の広さと適用力を得たほうがいいのかもしれない。
余談
配信ではやたらバグらせていたが、もとをただせばpowをlong longで明示してキャストしないと失敗するという問題だった。
ワーニング表記によればwindowsのx64環境下では明示キャストをしなくても大丈夫なようだったのだが、サーバ環境ではどうやらだめだったらしい。
配信ではいやそこは大丈夫だろみたいなことを言っていたと思うがまさにそこだった。
環境依存の問題もあるので、キャストはできるだけ正しくしたほうが良さそうである。
ちなみにキャスト問題以前に、あまりに数字が大きくなるとdoubleの丸め誤差が出そうで怖いので、long long用に自前のpowを書くというのが多分一番安全だっただろう。
また、業務ではちゃんと(long long)ではなく、static_cast<long long>という大変長ったらしいやつを書くことを推奨する。そちらのほうがいろいろと安全だからである。
だらだら配信
どんな感じの思考で解法に至ったのか知りたい稀有な人用。
ABC007のABC
ABC007のD試行錯誤
ABC007のD解決
