競技プログラミング風 C++問題集【第6回】

数値ローテイト（難易度：★★☆☆☆）

問題

引数で与えられたint型数値の最上桁の数字（1～9)を最下位桁に移動する関数 int rotate(int n) を実装しなさい。
ただし、0 <= n < 100,000,000 とし、範囲外の場合は -1 を返すものとする。

例えば、1234 が与えられると 2341 を、1020 が与えられると 201 を、7 が与えられると 7 を返す。
[java] #include <iostream> // 標準入出力ライブラリ
#include <string>
using namespace std; // std 名前空間使用
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
int rotate(int n) {
// ToDo: ここにnの各桁の数字をローテイトした値を返すコードを記述
return 0;
}
int main() {
DO_TEST( rotate(1234567) == 2345671 );
DO_TEST( rotate(1020) == 201 );
DO_TEST( rotate(9) == 9 );
DO_TEST( rotate(-1234) == -1 );
DO_TEST( rotate(100000000) == -1 );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・各桁をローテイトするには、数値をひとまず文字列に変換するといいぞ。
・数値→文字列変換には string to_string(int) を使うといいぞ。
・文字列の先頭文字は str.front() または str[0] で取り出せるぞ。
・文字列の先頭文字を削除するには str.erase(str.begin()) とするといいぞ。
・文字列に文字 ch を追加するには str + ch または str.push_back(ch) だぞ。
・または、for文を使って、自分で文字をローテイトしてもOKだぞ。
・最後にローテイトされた文字列を int atoi(const char* str) 使って数値に変換し、それを返すんだぞ。

解答例

[java] int rotate(int n) {
if (n < 0 || n >= 100000000) return -1;
auto t = to_string(n); // 数値→文字列変換
auto d = t.front(); // 先頭文字を取得
t.erase(t.begin()); // 先頭文字削除
t += d; // 元の先頭文字を末尾に追加
return atoi(&t[0]); // ローテイトされた文字列を数値に変換
}
[/java]

解説

最初に n の範囲をチェックし、範囲外であれば -1 を返す。
数値の各桁をローテイトするには、いったん文字列に変換した方が楽なので、string to_string(int) を使って文字列に変換する。次に、for文を使って自前で文字をローテイトしてもよいのだが、回答例のように、先頭文字をいったん取得・削除し、元の先頭文字を末尾に追加するとよい。
で。最後にローテイトされた文字列を int atoi(const char*) を使って数値に変換するとよい。

あみだくじ（難易度：★★★☆☆）

問題

下図のように、左側からスタートし、右側にゴールする「あみだくじ」を考える。

競技プログラミング風C＋＋問題集【第6回】_01

‘-‘, ‘+’, ‘|’, ‘ ‘ 文字で構成される、あみだくじを表す文字列配列と、何番目の線からスタートするかを引数で与えられ、何番目の線にゴールするかを返す関数 int amida(const vector<string>& lines, int n) を実装しなさい。
ただし、線の番号は 0 オリジン（最初の線が0番）とし、線番号 n は偶数のみが与えられるものとする。

例えば、上図の場合は、0 → 2, 2 → 4, 4 → 0 となる。

また、下図のように偶数ラインに ‘|’ があり、その上下に ‘|’ がある場合は、上下がつながっているとみなし、上下・左右方向のそれぞれの線はつながっていない（立体交差している）ものとする。なので、下図の場合は、0 → 4, 2 → 2, 4 → 0 となる。

競技プログラミング風C＋＋問題集【第6回】_02

なお、あみだくじ文字列は常に正常なものが与えられるものとし、それが不正な場合の処理は特に行わなくてよいものとする。
ただし、n が不正な場合は -1 を返すものとする。
[java] #include <iostream> // 標準入出力ライブラリ
#include <vector>
#include <string>
using namespace std; // std 名前空間使用
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
int amida(const vector<string>& lines, int n) {
// ToDo: ここにコードを記述し、あみだくじの結果を返すように
return 0;
}
int main() {
vector<string> a1 = {
"-+—-+—",
" | | ",
"-+–+-+-+-",
" | | ",
"—-+—+-"};
DO_TEST( amida(a1, -1) == -1 );
DO_TEST( amida(a1, 0) == 2 );
DO_TEST( amida(a1, 1) == -1 );
DO_TEST( amida(a1, 2) == 4 );
DO_TEST( amida(a1, 3) == -1 );
DO_TEST( amida(a1, 4) == 0 );
DO_TEST( amida(a1, 5) == -1 );
vector<string> a2 = {
"—-+—–",
" | ",
"—-|—–",
" | ",
"—-+—–"};
DO_TEST( amida(a2, 0) == 4 );
DO_TEST( amida(a2, 2) == 2 );
DO_TEST( amida(a2, 4) == 0 );
vector<string> a3 = {
"—–+—–",
" | ",
"–+–|–+–",
" | | | ",
"–+–|–|–",
" | | ",
"—–+–+–"};
DO_TEST( amida(a3, 0) == 2 );
DO_TEST( amida(a3, 2) == 4 );
DO_TEST( amida(a3, 4) == 6 );
DO_TEST( amida(a3, 6) == 0 );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・あみだくじのデータは lines 配列に文字列で入っているので、lines[n] を最初からたどっていくといいぞ。
・for文でカラム位置を 0 から文字列長-1まで回し、switch 文で処理を分けるといいぞ。
・’-‘ の場合は、次のカラムに移動するといいぞ。
・’|’ の場合は、立体交差なので、何も処理せず次のカラムに移動するといいぞ。
・’+’ の場合は上または下のラインに移動（n を更新）だぞ。
・最後に現在のライン番号を返せばいいぞ。

解答例

[java] int amida(const vector<string>& lines, int n) {
if (lines.empty() || n % 2 == 1 || n < 0 || n >= lines.size()) // エラーチェック
return -1;
const int len = lines[0].size();
for (int c = 0; c != len; ++c) { // 最初のカラムから順にチェック
switch (lines[n][c]) {
case ‘-‘: break;
case ‘|’: break; // 立体交差
case ‘+’:
if (n != 0 && lines[n – 1][c] == ‘|’) { // 上方向に | がある場合
n -= 2;
while( lines[n][c] == ‘|’ && n != 0 && lines[n – 1][c] == ‘|’) {
n -= 2;
}
} else if (n < lines.size() – 1 && lines[n + 1][c] == ‘|’) { // 下方向に | がある場合
n += 2;
while( lines[n][c] == ‘|’ && n < lines.size() – 1 && lines[n + 1][c] == ‘|’) {
n += 2;
}
}
}
}
return n;
}
[/java]

解説

あみだくじのデータは lines 配列に文字列で入っているので、lines[n] を最初からたどっていくとよい。
具体的には、回答例のように添字 c を 0 からデータ長-1まで回す。現在行は n なので、switch( lines[n][c] ) で文字を調べ、分岐する。
文字が ‘-‘ であれば別の行に移ったりしないので、次のカラムに進む。
‘|’ だった場合も、立体交差なので、同じ様に次のカラムに進む。
‘+’ の場合は、n を 2 だけ増減させて、下または上のラインに移る処理を行う。同じカラムにさらに ‘|’ がある場合は、先のラインに移動し、これを繰り返す。
最後のカラムまで到達した場合は n を返す。