いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AOJ-ICPC 100 Next Mayor書いてたらコーディングでやらかしてた話

Next Mayor | Aizu Online Judge
実装力が足りないと思ってとりあえずAOJ端っこから解いていくかなって思ってる
で、この問題を実装していたらよくわからないことが起きて頭を抱えた
書いたソースがコレ

#include<iostream>
using namespace std;
#include<vector>
 
int main(){
  while(1){
    int n,p;
    cin>>n>>p;
    if(n==0&&p==0)return 0;
    vector<int> a(n,0);
    int pool=p;
    int i;
    while(1){
      for(i = 0;i<n;i++){
        if(pool==0){
          pool+=a[i];
          a[i]=0;
        }else{
          pool--;
          a[i]++;
        }
        if(a[i]==p)break;
      }
      if(a[i]==p)break;
    }
    cout<<i<<endl;
  }
  return 0;
}

2重ループの抜け方が酷いが楽してしまったのが悲劇だった
これで問題のテストケースを投げると1か所だけ通らない
その箇所単体で投げたら通る
初期化ミスしか思い浮かばなかったが見当たらない
コーナーケースを考えてもどうあがいてもわからなかった
隣に座ってた友人に聞いたら配列外参照をしているとのこと
じっくり考えたら気づいた、forループをi=n-1で抜けるとi=nの状態で次の行に入る
で、そのまま抜けてしまうのでテストケース3 3の場合i=3でループ抜けしていることになる
その時たまたま配列外参照したポイントが正解とかぶってしまったのでループを抜けてそれが答えになっちゃったらしい
伝わりにくいけどそういうことらしい
なのでループ部分を改善したらAC

#include<iostream>
using namespace std;
#include<vector>
#include<cassert>
 
 
int main(){
  while(1){
    int n,p;
    cin>>n>>p;
    if(n==0&&p==0)return 0;
    vector<int> a(n,0);
    int pool=p;
    int i=0;
    while(1){
      for(i = 0;i<n;i++){
        //assert(0<=i && i<n);
        if(pool==0){
          pool+=a[i];
          a[i]=0;
        }else{
          pool--;
          a[i]++;
        }
        //assert(0<=i && i<n);
        if(a[i]==p)break;
      }
      //assert(0<=i && i<n);
      if(a[i]==p&&i<n)break;
    }
    cout<<i<<endl;
  }
  return 0;
}

最初からまじめにフラグとかで実装すればよかったなぁ
assertはその値の範囲から逸脱していた場合処理を停止してくれるというものらしいです
割と便利だなぁと思った

・追記
修正すべき箇所が残っていたのをすっかり忘れて2人から同じ指摘をしていただきました

if文やその他の条件式は前から処理されるので

if(a[i]==p&&i<n)

としてしまうと先にa[i]がpと一致するか調べ(ここで配列外参照が起きる)、その後iがnより小さいかを判定するので

if(i<n&&a[i]==p)

とすることで先にiがnより小さいかを判定し、負ならそのまま判定を終了してくれるので配列外参照が起こらないって話でした

こう言うことをちゃんと覚えるための忘備録なので気を付けようと思います
短絡評価というのは知らなかったなぁ