B - 双六 (Sugoroku) Editorial by TumoiYorozu
この解説は、C++ に入門したばかりの中高生レベルを想定して、考察の方法、コードの書き方の解説をします。
問題文を要約すると、以下のようになります
- 一直線のすごろくがあり、スタートとゴールを除いた N マスには 0 か 1 が書かれている。
- サイコロを振って出た目の数だけ進む。
- 0が書かれたマスに止まったら何もおこらない
- 1が書かれたマスに止まったらスタートに戻る
- サイコロは6面サイコロとは限らず、ある数 x を決めた時、1~x の数が出る
- サイコロは何回でも降って良いとき、最小で何面サイコロであればゴールする事が可能だろうか
1のマスに止まると振り出しに戻ってしまうので、1のマスを回避できる様なサイコロが欲しい。 サイコロは何回でも降って良いので、『自由な目を出せるサイコロを使う時、最小で何面サイコロであればゴールする事が可能か』と考えても良い。
1のマスに止まると振り出しに戻ってしまうので、0のマスのみ止まることを考えれば良い。
なんならサイコロは何回でも降って良いので、0のマス全て止まる勢いで考えても良い。このとき最小で何面サイコロであればゴールする事が可能だろうか。
全ての0のマスに止まれば良いので、連続する1のマスの個数を飛び越えられるかがキーである。
整理すると、『連続する1のマスの個数』の最大+1 が答えである。
以下の様に書くと、入力 N と、各マスの値 a を読み込むことができます。 次のヒントは、連続する様な1のカウント方法です。
処理① で今連続で何個目の 1 かをカウントする変数 x を用意して、処理② で if 文を用いて x を更新します。
以下のように書くことができます。 これで何回1が連続しているのか分かるので、ヒント5で考えたとおり、この連続値の最大を求めてあげれば良いです。
変数 ans に連続値の最大を記録しているとして、 このヒントはオマケです。 例えば以下のコードは(ほとんど正解に近いのですが)間違いを含んでおり、入力例1は そこで、21行目の様に、ループの中に色々な変数の値を出力してみて、毎回どの様に値が変化しているのか観察してみると良いです。 このデバッグのためのコードを実行すると、入力例1では以下のような結果が得られます。
ヒント1: 解き方の方針【起】
ヒント2: 解き方の方針【承】
ヒント3: 解き方の方針【転】
ヒント4: 解き方の方針【結】
ヒント5: 解き方の方針【Final】
ヒント6: 繰り返し文の復習
for(int i = 0; i < N; i++)
で N 回のループを表現できます。
ヒント7: 繰り返し文で入力 a を順番に読む方法の復習
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
~~処理①~~
for(int i = 0; i < N; i++) {
int a;
cin >> a;
~~処理②~~
}
~~処理③~~
}
ヒント7
ヒント8: ヒント7の実装例
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
int x = 0;
~~処理①~~
for(int i = 0; i < N; i++) {
int a;
cin >> a;
if (a == 0) {
x = 0;
} else {
x += 1;
}
~~処理②~~
}
~~処理③~~
}
ヒント9
if (ans < x) {
ans = x;
}
と書くと、最大を記録できます。
ヒント10: 微妙にバグる人へのヒント
2
が正解のところ1
が出力されてしまいます。#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
int x = 0;
int ans = 0;
for(int i = 0; i < N; i++) {
int a;
cin >> a;
if (ans < x) {
ans = x;
}
if (a == 0) {
x = 0;
} else {
x += 1;
}
// デバッグのために、毎回どの様に値が変化しているのか確かめる。
cout << "i=" << i << " x=" << x << " ans=" << ans << endl;
}
cout << ans << endl;
}
i=0 x=0 ans=0
i=1 x=1 ans=0
i=2 x=0 ans=1
i=3 x=0 ans=1
i=4 x=0 ans=1
1
さて、一体何が間違えているのでしょうか…?(間違いが1つとは限りません)
解答コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
int x = 0;
int ans = 0;
for(int i = 0; i < N; i++) {
int a;
cin >> a;
if (a == 0) {
x = 0;
} else {
x += 1;
}
if (ans < x) {
ans = x;
}
}
cout << ans + 1 << endl;
}
posted:
last update: