なぜか繰り返しが1回多くなるので原因を教えて下さい！

Question

該当のソースコード

C言語

#include <stdio.h>

int main(void){

int n;
int a[200000];
int count[200000];

scanf("%d",&n );

for (int i = 1; i < n; i++) {
  scanf("%d", &a[i] );
  count[a[i]]++;
}

for ( int i = 1; i <= n; i++) {
    printf("%d\n", count[i] );
}

  return 0;
}

現在、C言語を勉強中の初心者です。初歩的な質問かもしれませんがお手柔らかにお願いします。
以下のような問題を解いているのですが、上のプログラムを実行するとscanfのfor文がなぜか1回多く繰り返してしまいます。
例えばn=5とすると、4回だけ繰り返すように書いてるつもりですが、実行すると5回繰り返されてしまいます。
調べてもどうしてもわからないため、なぜ1回多く繰り返されるのか教えて下さい。

問題文
N人の社員からなる会社があり、各社員には1,...,N の社員番号が割り当てられています。
社員番号 1の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど1人います。
XさんがYさんの直属の上司であるとき、YさんはXさんの直属の部下であるといいます。
社員番号iの社員の直属の上司の社員番号がAiであることが与えられます。各社員について直属の部下が何人いるか求めてください。

制約
2≤N≤2×10^5
1≤Ai<i

Comments

[archiver]

for文は２つありますが、どちらのfor文ですか？
（何となく、後者かな）

[nagak]

前者の方です。
for (int i = 1; i < n; i++) {
scanf("%d", &a[i] );
count[a[i]]++;
}
ご教授お願いします！

[YT0014]

1回多く繰り返している、と判断した根拠は何でしょうか？
コードを見た限り、scanf()は、最初の1回と(入力値-1)回しか、呼ばれないように見えます。
もし、count[]の出力結果から判断されているのなら、初期値が不定(０とは限らない)なので、意味がありませんが。

[cateye]

>int a[200000];
>int count[200000];

ローカル変数にしては、大きすぎませんか？（int==4byteで、１．５MiB有ります）

[nagak]

1回多く繰り返していると判断した根拠ですが、実行し以下のように入力すると、
5
1 1 2 2
目標としては以下のように出力されるように書きたいのですが、
2
2
0
0
0
実際は
5
1 1 2 2 　を入力したあと結果が出力されず、適当になにか数字を１つ追加で入力すると結果が出力されます。そのため、scanfが5回繰り返されているのではないかと判断しました。
そしてなぜなのかわからないのですが、1つ数字を追加で入力してもcountに反映されなく、目標とした正しい結果が出力されます。

[nagak]

>int a[200000];
>int count[200000];
大きすぎるのではないかという指摘についてですが、
問題の制約が2≤N≤2×10^5だったため、N=2×10^5でも対応できるようにと考えこの大きさにしました。

[amiya]

(関係ない内容でしたm(__)m)

[KoichiSugiyama]

Windows 10 のWSL(SUSE Linux)でコンパイルして確認しました。
5 (enter)
1 1 2 2 (enter)
でも
5 (enter)
1 (enter)
1 (enter)
2 (enter)
2 (enter)
でも結果は
2
2
0
0
0
となりますが、どのように入力されていますか？

[nagak]

virtualbox上のubuntu18.04でコンパイルしているのですがその2パターンで入力してenterまたはスペースを押しても何も結果が出力されません。数字または文字を入力してからenterを押すと出力されます。

[cateye]

（環境依存、処理系依存なのですが）ローカル変数は、スタックに取られます。そのため、領域を取りすぎるとスタックを破壊する可能性が有ります。
出来れば外部（関数の外）に取ったほうが、そういった問題が起こらなくなります。＞nagakさん

[KoichiSugiyama]

だとしたらscanf("%d", &a[i] );の前にprintf("社員(%d)の上司は?”, i);と入力ガイドを入れて1回ごとにenterを押して実行してみてはどうでしょうか？ループが一つ多いのかどうかはっきりすると思います。

[nagak]

皆様のおかげ無事問題を解決できました。
本当にありがとうございました！

Answer 1

本当にそのコードですか？
scanf の "%d" のあとに"\n" を入れて、scanf("%d\n", &a[i]); としていませんか？

Comments

[nagak]

確認したところご指摘どおりscanf("%d\n", &a[i]);になっていました。
自分でいろいろ試しているうちに変えてしまっていたようです。
修正して実行したところ無事、目標とした出力結果が出ました！
本当にありがとうございました！

Answer 2

返答内容から、状況を理解いたしました。

結果ですが、ループは、想定通りの回数となっております。

ただ、最後の入力時、scanf()が、入力終了を判断できず、キー待機状態で止まります。
その後、数字(または空白かも)が入力されることで、このscanf()の結果が確定し、追加の数字が入力バッファに残っている状態になります。

KoichiSugiyamaさんの確認時にあるように、入力完了として(enter)が押されれば、所定のループ回数で終わることが確認できるでしょう。

このような動作をするため、scanf()の使用には注意が必要です。

Comments

[nagak]

enterまたはスペースを押しても結果が出力されない状態です。数字または文字を入力してからenterを押すと出力されます。

Answer 3

ungetcは連続して使う事は保証されておらず、
以下のコードはNGでした。

---

とりあえず、何が起きているのか可視化してみた(つもり)。
[]の中は入力ストリームに溜まってる内容を1バイトずつ16進数で表示したもの。
(とりあえずなので、数は一桁ずつが前提です)

#include <stdio.h>

void printSIN(){
    int c[256],*p;
    printf("buf:");
    for(p=c; (*p=getchar())!=EOF; p++)
        printf("[%02X]",*p);
    printf("\n");
    while(p>=c) ungetc(*p--,stdin);
}

int main(void){

int n;
int a[200000];
int count[200000]={0};

scanf("%d",&n );

for (int i = 1; i < n; i++) {
    
    printf("---#%d---\n",i);
    
    printSIN();
    
  scanf("%d", &a[i] );
  count[a[i]]++;

    printf("get:[%x](%d)\n",a[i]+'0',a[i]);

    printSIN();
}

    printf("---END---\n");


for ( int i = 1; i <= n; i++) {
    printf("%d\n", count[i] );
}

  return 0;
}

Comments

[kazuma-s]

JIS X 3010：2003 (ISO/IEC 9899：1999)
7.19.7.11 ungetc関数
...
　どの処理系でも 1 文字の押戻しを保証する。ストリームに対して読取り又は
ファイル位置付けを 1 回も間にはさまずに ungetc 関数を何回も繰り返し呼び
出すと，失敗することがある。

[amiya]

おお…こういう使い方はNGなんですね。ありがとうございます。