trainedの問題を解くためのメモ
使用言語：c++
問題の意味
N個のボタンがあって、最初は1つ目のボタンが光っている。
光っているボタンを押すと、1つ目のボタンの光が消えて、1つ目のボタンについている番号のボタンが光る。
１つ目のボタン = 3
2つ目のボタン = 1
3つ目のボタン = 2
のように番号がついている。一つ目のボタン名3が光っているので最初に押す。1つ目のボタン名3を押すと、3つ目のボタン名2が光る。3つ目のボタン名2を押すと、3つ目のボタン名2の光が消えて、2つ目のボタン名1が光る。
この時点で、2が光っているので終了。
1つ目のボタン名3を押す→1回
3つ目のボタン名2を押す→1回
2つ目のボタン名１が光るので、2回のカウントで2つ目のボタンが光ったということになる。
2つ目のボタンが光った時点で処理を終了し、ボタン2が光るまで何回ボタンを押したかカウント値を出力するという問題。
また、ボタン2が光ることはないケースは、－1を出力する。
今回、問題の意味がなかなか理解できず、理解するのに時間がかかりました。
入力例1
3
3
1
2
出力
2
入力例2
3
3
2
1
出力
-1
問題を解くためのメモ
PDL(program design language)のように、c++で書いたりせず、まず日本語の文章で処理を書くことでプログラミング言語に依存しない高水準な設計をする。
とかいっちゃっても問題解くときは、ここまで文章にしていません。難しいのでとりあえず条件分岐書いちゃったりしてそこから検討したりしちゃいます。本当はPDLで高水準なレベルで書いた方がいいみたいです。
PDLちゃんとしておくと、建築後の壁を取り払うみたいなコードの修正になりにくく、軽微な修正になり、後の修正が楽になるみたいです。
先にコード書いてしまいがちですが、次回コードを書くときはもっと高水準なレベルでしっかり書いていきたいと思います。
まずボタンの個数とボタンの入力を受け取る。
入力から受け取ったボタンを配列に保存する。
縦に1列で入力を受け取るので、用意する配列は1次配列。
最初はひとつ目のボタンを必ず押すので、ひとつ目のボタン名によって処理を分ける。
もし、ひとつ目のボタン名が1のとき、ずっとひとつ目のボタンしか押せないのでそこで処理が終了し-1を出力する。
もし、ひとつ目のボタン名が2のとき、ひとつ目のボタンを押すとふたつ目のボタンが光るのでカウント1回して処理は終了、カウントを出力する。
もし、ひとつ目のボタン名が1でも2でもないとき、ひとつ目のボタンを押すと1でも2でもない番号が光る。
カウント1回する。
もし、上記で光ったボタン名が1の場合、ひとつ目のボタンとボタン名1が交互にしか光らず、２つ目のボタンは光ることはないので-1を出力する。
もし、ひとつ目のボタンを押して光ったボタン名が2のとき、ボタン名2を押すとふたつ目のボタンが光るのでカウント1回して処理を終了する。
ひとつ目のボタンを押して光ったのが上記のボタン名1でもボタン名2でもないとき、順次ボタンを押しつつカウントし、ボタン名2が現れたら処理を終了し累計のカウント数を出力する。
もしカウント数がボタンの数を超えたら、ボタン名2は光らないことを意味するので、-1を出力する。
ボタンの個数： int N;
ボタンを押した回数：int count = 0; // 0で初期化しておく
２つめのボタンが光らないことを意味する変数: int e = -1;
N個のボタンを受け取る配列：vector<int> vec(N);
例)
ひとつめのボタン名3を押して3つめのボタンが光るために必要な動作
3 ←ここを押すと
2
1 ←ここが光る
ひとつめのボタンはvec.at(0)で、ボタン名は3なので、
ひとつめのボタンはvectorの1次元配列vecに
vec.at(0) = 3
という形で保存されている。
３つめのボタンはvec.at(2)。
このボタンが光るので、vec.at(0) = 3
の3をvec.at(i)に代入する。
ただ、そのまま代入するとvec.at(3)となってこれは4つめのボタンなので、1引いてあげることで補正すればよさそう。
代入するボタン名をxとおく。
ここではひとつめのボタンのボタン名3がxに代入されている。
x = vec.at(0) - 1 とすると、 3 - 1 = 2となるのでこの補正でok。
i = x; とし、iにxを代入すると、vec.at(i)のi はxが代入されたiなので、
x = vec.at(i) - 1;
i = x;
と書いたうえで
if(vec.at(i) == 1){...}のように書くと、vec.at(i)は上記の例の場合でみると、
x = 2;
i = 2;
if(vec.at(2) == 1){...}のように、vec.at(2)で3つめのボタンを表していることとなり、ボタンを押す操作を表現することができる。
あと、書いたコードの挙動を確認するために、要所要所でちゃんとカウントや‐1が出る場所が把握できるように、コードを書きました。入力を試してみて、動作が正しいことが確認できたら、提出用に修正する感じでいきました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
int count = 0;
int e = -1;
int x;
int i;
cout << "ボタンの数を入力してください" << endl;
cin >> N;
vector<int> vec(N);
// ボタンの入力
cout << "ボタンを入力してください" << endl;
for(i = 0; i < N; i++){
cin >> vec.at(i);
}
// この配列に対して操作をする
// vec.at(i)に移動するたびにカウント処理
// 最初に必ず光っている1つめのボタンの処理
// i = 0のとき
// 1番目のボタン1の値が1のときボタンが1から移動しないのでカウントせず終了
if(vec.at(0) == 1){
cout << e << " error1" << endl;
}
// iが0のとき、値が2のときはカウントしてそこで終了
if(vec.at(0) == 2){
count++;
cout << count <<endl;
}
// 上記以外：iが0で値が1および2以外のときはカウントして処理を進める。
if(vec.at(0) != 1 && vec.at(0) != 2){
count++;
// vec.at(i)の値にiの値を代入して次のボタンへ移動
x = vec.at(0) - 1;
i = x;
cout << "iの値は " << i << " です。" << endl;
// i = xの値で条件分岐処理
// vec.at(i) = 1のとき、ボタン1とボタンiを往復するのでボタン2は光らないので終了
if(vec.at(i) == 1){
cout << e << " error2" << endl;
}
// 値が2だったらそこでカウントして終了
if(vec.at(i) == 2){
count++;
cout << count << endl;
}
if(vec.at(i) != 1 && vec.at(i) != 2){
while(count < N){
count++;
x = vec.at(i) - 1;
i = x;
cout << "iの値は " << i << endl;
if(vec.at(i) == 2){
count++;
cout << count << endl;
break;
}
}
if(count >= N){
cout << count << endl;
cout << "error3" << endl;
}
}
}
return 0;
}動作確認用の出力やコメントを削除した後、最終的に提出したコードはこちら。
まだまだ修正の余地がめっちゃありそうだけど、とりあえず動作だけしっかり確認したので1発で正解となりました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
int count = 0;
int e = -1;
int x;
int i;
cin >> N;
vector<int> vec(N);
for(i = 0; i < N; i++){
cin >> vec.at(i);
}
if(vec.at(0) == 1){
cout << e << endl;
}
if(vec.at(0) == 2){
count++;
cout << count <<endl;
}
if(vec.at(0) != 1 && vec.at(0) != 2){
count++;
x = vec.at(0) - 1;
i = x;
if(vec.at(i) == 1){
cout << e << endl;
}
if(vec.at(i) == 2){
count++;
cout << count << endl;
}
if(vec.at(i) != 1 && vec.at(i) != 2){
while(count < N){
count++;
x = vec.at(i) - 1;
i = x;
if(vec.at(i) == 2){
count++;
cout << count << endl;
break;
}
}
if(count >= N){
cout << e << endl;
cout << count << endl;
}
}
}
return 0;
}ifとforとwhileしか僕はまだ使えず、switch文やdo while文とかのほうが合っているケースもあるかもしれないけど、書き方が苦手なので、今後は状況に合わせて使えるように少しずつ覚えていきたいです。