情報オリンピック予選過去問

[pon]

情報オリンピック2008-2009の予選の3番なのですが、
問題:http://www.ioi-jp.org/joi/2008/2009-yo- ... yo-t3.html

添付したようなプログラムを組みました。
かなり遅いので、解説を見ていると同じことをしている気がします。
何が問題でこんなに遅いのでしょうか。

[toyo]

ループの一番中にある

for(int henkou=idou;henkou<idou+ren+1;henkou++){
    b[henko[/url]=b[henkou+ren+1];
}

で配列の内容を書き換えているのために処理に時間がかかるのでは
ループの中のインデントが深くなるほど処理に時間がかかるようになると思います
自分のパソコンの中を覗いたら昔書いたVisualC++2008のプロジェクトがあったのでアップしてみます
実際のゲームで画面を表示するなら配列の書き換えも必要になると思いますが計算をするだけなら移動処理はせずに数をカウントするだけでいいということです

[たいちう]

toyoさんに先を越されたけど、一応載せておきます。
アルゴリズムは一緒ですね。

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int data[10000];
int len;

int check(int index) {
    int lIndex = index;
    int rIndex = index + 1;
    int lLeft = index + 1;
    int rLeft = len - rIndex;

    for (;;) {
        int lCol = lIndex >= 0 ? data[lIndex] : 0;
        int lNum = 0;
        while (lIndex >= 0 && data[lIndex] == lCol) {
            lNum++;
            lIndex--;
        }

        int rCol = rIndex < len ? data[rIndex] : 0;
        int rNum = 0;
        while (rIndex < len && data[rIndex] == rCol) {
            rNum++;
            rIndex++;
        }

        if (lCol == rCol && lNum + rNum >= 4) {
            lLeft -= lNum;
            rLeft -= rNum;
        } else
            return lLeft + rLeft;
    }
}

void test(const string &fileName) {
    ifstream ifs(fileName.c_str());
    ifs >> len;
    for (int i = 0; i < len; i++) {
        int buf;
        ifs >> buf;
        data = buf;
    }

    int min = len;
    for (int i = 0; i < len; i++) {
        for (int c = 1; c <= 3; c++) {
            if (data == c) continue;
            if ((i > 0 && data == c) || (i < len - 1 && data[i + 1] == c)) {
                int c0 = data;
                data = c;
                int left = check(i);
                if (min > left)
                    min = left;
                data = c0;
            }
        }
    }
    cout << fileName << " : " << min << endl;
}

int main() {
    test("sample_1.txt");
    test("sample_2.txt");
    test("data_1.txt");
    test("data_2.txt");
    test("data_3.txt");
    test("data_4.txt");
    test("data_5.txt");

    return 0;
}

[toyo]

このループの意図がわかりません

for(int lop=1;lop>0;lop++){
                int idou;
                if(kesita>3){idou=kesita-3;}
                else{idou=0;}
                while(1){
//省略
                }//whileはここまで！！一回消す作業
                if(flag==0){
                    break;
                }
            }//一個変えたことによる連鎖計算終了

ループの中にflagを1にする文はありますが0にする文がありません
いったんflagが1になるとlopがオーバーフローして負になるまで繰り返してしまいます
無限ループでfor ( ; ; )やwhile(1)は見ますがfor(int lop=1;lop>0;lop++)のような書き方は変ですね

[pon]

配列を書き変えたのが良くなかったんですね
ありがとうございます

合格のボーダーの63点ギリギリしか取れなくて焦っています
何を勉強すればいいんでしょうか

[pon]

>>toyoさん
そうですね
flagの初期化の位置がおかしかったですね
flagの初期化の位置をちゃんとしてみたら、動作はかなり速くなったのですが、サンプル以外のinputに対して正確な答えを返しませんどうしてでしょう

[たいちう]

> 合格のボーダーの63点ギリギリしか取れなくて焦っています
> 何を勉強すればいいんでしょうか

・言語の知識
　　間違っても足を引っ張ることのないようにしておきましょう。
　　完璧に覚えなくても良いけど、過去問を解くのに必要な構文は
　　最低限マスターしましょう。

・アルゴリズム
　　アルゴリズムに精通していれば、問題を見た瞬間に
　　役に立ちそうなアルゴリズムを思いつく可能性が上がります。
　　良いプログラムを多く読んでおくことも大事。

・応用力
　　初見の問題で短時間で効率の良いプログラムを作るには、
　　応用力が最も必要です。
　　言語の知識が完璧でも、アルゴリズム辞典を覚えていても、
　　応用力が貧弱だと役に立ちません。
　　言語やアルゴリズムの習得を通じて、多くのプログラムに触れ、
　　多くのプログラムを書いて、応用力を養っていくのが唯一の方法だと思います。

言語とアルゴリズムは、努力次第で何とでもなりますが、
個人的には応用力はそうとは限らないと思います。
最初から応用が得意な人もいれば、努力しても応用力が身に付かない人もいます。
努力して応用力が強化される人もいるでしょうから、無駄な努力とは限りませんが。
量的な努力よりも工夫が重要だと思いますが、工夫できる人は既に応用力を
持っているともいえるし……
難しいところですね。

日本情報オリンピックだけをターゲットにした練習もあるとは思いますが、
それこそ不毛かもしれませんね。何を焦っているのか書いてもらえると、
もっとアドバイスできるかもしれませんが。

[pon]

・言語の知識
一応C++の本は読んでポインタやクラス以外は理解し覚えたつもりです(ポインタは一応意味は分かるのですが、何のために必要かが分かりません。クラスは意味がイマイチわかりませんでした。)

・アルゴリズム
これは全く知らないと言って過言でないかもしれません。
一応メモ化再帰やDPは分かりますが。

・応用力
それは自分ではよく分かりません。

自分は高2のため情報オリンピックを受けるのは最後のチャンスなので、とりあえず頑張りたいなと思っているのです。あと、単純にプログラミングができるようになりたいということです。

で、本題に戻るのですが、結局何が間違っているのでしょうか

[たいちう]

> ・アルゴリズム
> これは全く知らないと言って過言でないかもしれません。
> 一応メモ化再帰やDPは分かりますが。

まずはアルゴリズムを広く深く勉強することですね。
そして必要に応じて言語の知識を補強していきます。


> で、本題に戻るのですが、結局何が間違っているのでしょうか

まずtoyoさんに指摘された部分を直しましょう。
その後で考えても判らないならば、その時のプログラムを載せて下さい。
自分のプログラムを暫く忘れて、toyoさんや私のプログラムを解析するのも良いでしょう。

[pon]

toyoさんやたいちうさんのプログラムは分かりました。
結局は配列を並び変えていないことを除くと基本的には自分のと同じだと思うのですが、何故答えが間違えているのでしょうか

[たいちう]

> toyoさんやたいちうさんのプログラムは分かりました。

初心者のうちは、「アルゴリズムを理解する」ということは、
「何も見ないでも同じものが書ける」という意味と考えて下さい。
書けますか？


ponさんのプログラムをデバッグするのは骨なので(直すよりも1から書いた方が早いというケース)、
デバッグのヒントを。

n = 5;
a[/url] = { 1, 1, 2, 1, 1 };

という入力に対して、予想通りの答えを出せますか？

n = 7;
a[/url] = { 1, 2, 2, 3, 2, 2, 1 };
だったら？

デバッグするのに元の例題が難しいようだったら、適当な問題を入力することで
比較的簡単にデバッグできますよ。
それと、いちいち数値を入力するのは面倒ですし、間違う可能性も高いです。
ソースコードに書いてしまうか、問題ファイルを読み込むようにしましょう。

[pon]

確かに、アルゴリズムとしては理解したつもりなのですが自分には実装できなさそうです…


nが小さな値に関しては正確な答えを出すのですが…(与えられたサンプルに対しても正確な値を返しました
答えが0になる場合はbugが起こっていたので、配列の最後に4という関係のない値を入れることで解決しました
しかし、問題のようなnが100になったりすると何故か変な答えを返します。
決してnを超えたりはしないのですが

ソースコードに書いてしまうのは確か(情報オリンピックでは)禁止されているはずです
問題ファイルを読み込む方法はたいちうさんのコードを見て初めて知りました…

[たいちう]

> 確かに、アルゴリズムとしては理解したつもりなのですが自分には実装できなさそうです…

あくまでも、つもりに過ぎなかったということです。

最近ブログで読んだことですが、私も昔から実践しています。
力が付きますよ。ご参考までに。
http://www.hyuki.com/d/201005.html#i20100521225000

[pon]

で、結局自分のプログラムは何が間違っていますか?

[たいちう]

> 答えが0になる場合はbugが起こっていたので、配列の最後に4という関係のない値を入れることで解決しました
> しかし、問題のようなnが100になったりすると何故か変な答えを返します。

解決したというプログラムを載せて下さい。
No.52787のプログラムでは、↓の答えが-10002になってしまいます。

n = 5;
a[/url] = { 1, 1, 2, 1, 1 };


> で、結局自分のプログラムは何が間違っていますか?

おそらく考え方が間違っているのだと思いますが、
私にはプログラムからponさんの考え方が読み取れませんので、
私なりに直すと、やはりNo. 52665になってしまいます。

自分のプログラムの変数の意味とか、ループの意図とかうまく説明できますか？

[pon]

改訂版です。
コメントを書く部分に書いてみました。何か間違っている部分があるでしょうか

[softya]

>コメントを書く部分に書いてみました。何か間違っている部分があるでしょうか
と聞く前に。

たいちうさんの
n = 5;
a[/url] = { 1, 1, 2, 1, 1 };
を入れて試してみましたか？
答えが合いませんよね。

そもそも、プログラムをデバッガトレースしたり、中間状態をprintfしたりしてちゃんとデバッグしてますか？
理解度をアップしたいなら、まずそこから始めて見ませんか。

[たいちう]

n = 5;
int a[20000] = { 1, 1, 2, 1, 1 }; 
(0)

n = 12;
int a[20000] = { 3, 2, 1, 1, 2, 3, 2, 2, 2, 1, 1, 3 }; 
(3)

n = 12;
int a[20000] = { 3, 2, 1, 1, 2, 3, 2, 1, 3, 2, 1, 3 }; 
(12)

n = 100;
int a[20000] = {
    2, 3, 1, 2, 2, 2, 3, 2, 1, 3, 1, 1, 2, 3, 2, 3, 3, 3, 1, 1, 2, 3, 2, 2, 2,
    3, 1, 1, 1, 2, 1, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 1, 1, 2, 2,
    2, 3, 3, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 2, 3, 2,
    1, 2, 2, 1, 2, 2, 3, 3, 2, 1, 2, 3, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1,
};
(77)

今ちょっと試してみると、n = 12までは正しい答えが出せますね。
で、100の時に間違っていると。
確かにこのような場合のデバッグは少し難易度が高いですね。
今からしばらく外出しますが、今日中にはできるでしょう。


softyaさん＞

n = 5の場合は正しい答えが出ているようですよ。
softyaさんか私かどちらかが勘違いをしているみたいですので、
ご確認お願いします。私も帰宅後にもう一度確認します。

[softya]

>softyaさんか私かどちらかが勘違いをしているみたいですので、

あぁ、すいません勘違いですね。
任意の場所の任意の色を１つだけ置き換えるってのを全ての場所で行った場合のシミュレートですね。
ただ、ponさんのも解答例と一致しませんので、まだ間違いがあります。
http://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/

[たいちう]

n = 13;
int a[20000] = { 3, 1, 2, 3, 2, 2, 1, 1, 1, 3, 3, 3, 1 };

比較的短くて誤判定するパターンを見つけました。
それと、デバッグにはこのような工夫をしましょう。

void show(int *b, int len) {
    for (int i = 0; i < len; i++)
        printf("%d", b);
    printf("\n");
}

これで直せるのではないかと思いますが、どうしてもわからなければ再度聞いてください。

[pon]

解決しました。配列の書き変えがうまくいってませんでした。
(ちゃんと最後まで書きかえることが出来ていませんでした。

if(b[idou+2]==b[idou+3]){
for(int ren=1;ren>0;ren++){
if(b[idou+ren] != b[idou+ren+1]){
nn -= ren+1;
for(int henkou=idou;henkou<nn;henkou++){
b[henko[/url]=b[henkou+ren+1];
}
flag=1;
kesita=idou;
break;
}
}
break;
}

これで正確な値を出すことができました。ありがとうございます

[たいちう]

解決！マークをチェックしましょう。
その他気付いた点です。

・配列bを初期化する
・無意味なインクルードをやめる
・連続の判定を改善する

配列bの初期化は必須です。
連続の判定については、次の問題点があります。

・5連続以上を消すルールに変えた場合、if文が1つ深くなる。
・10連続以上を消すルールに変えた場合、目も当てられない。
・ルール変更がないとしても、改善すればプログラムの見通しが良くなり、
バグも減ります。

それと既に直っているかもしれませんが、
配列を書き換えて短くなった部分には0を代入しておきましょう。


最後に、折角この問題に取り組んだのだから、私かtoyoさんのプログラムも
「理解」できるようになったほうが良いと思います。

[pon]

情報オリンピックは時間の制限が結構きついのでインクルードはCopy&Pasteした方が良いと言われました

bの初期化について
一番最初に書いたprogramの時からbの初期化はしているはずです

ルールを変えた場合について
書くのがめんどくさくなるということでしょうか?

[たいちう]

> 情報オリンピックは時間の制限が結構きついのでインクルードはCopy&Pasteした方が良いと言われました

私なら今のponさんには別のアドバイスをします。
必要なものだけコピペしましょう。何が必要か瞬時に判らないなら論外です。
「十分早い時間で解けるようになる」前に、
「時間をかけたら解けるようになる」事を目指すべきです。
小手先の技を意識する段階ではありません。

せめて掲示板で質問するときには削除しておいてください。


> bの初期化について
> 一番最初に書いたprogramの時からbの初期化はしているはずです
> ...
> int n;
> scanf("%d",&n);
> int a[10000]={0};
> int b[10000];
> int nn_min=n;
> for(int loop=0;loop<n;loop++){
> scanf("%d",&a[loop]);
> b[loop]=a[loop];
> }

例えば、n = 12の時に、b[20]は初期化されますか？


> ルールを変えた場合について
> 書くのがめんどくさくなるということでしょうか?

質問の意味が判りません。
↓に説明しているとおりです。

> 連続の判定については、次の問題点があります。
>
> ・5連続以上を消すルールに変えた場合、if文が1つ深くなる。
> ・10連続以上を消すルールに変えた場合、目も当てられない。
> ・ルール変更がないとしても、改善すればプログラムの見通しが良くなり、
> バグも減ります。

[pon]

includeについて
分かりました

bの初期化について
b[10000]={0}
と最初に書くべきだということですか?

ルールを変えた問題について
10連続のときに目も当てられないのは何故ですか?

[たいちう]

> bの初期化について
> b[10000]={0}
> と最初に書くべきだということですか?

それも正解の1つです。


> ルールを変えた問題について
> 10連続のときに目も当てられないのは何故ですか?

判らないならば、そのようにルールを変更して書いてみて下さい。

[pon]

ルールを変更して書いてみたのですが、普通に動くのですが

[たいちう]

> ルールを変更して書いてみたのですが、普通に動くのですが

動作しないとは書いていません。目も当てられないと書いたのです。
それを貼ってみて下さい。

[pon]

これなのですが