yukicoder contest 173 - u_sho競プロぶろぐ

　お久しぶりの投稿ですね。先に言っておきますと、きょうもSyntaxHighlighterの実装はしておりません。さぼりました。やる気なくてごめんなさい。

　そんな私は昨日(今日かな？)、yukicoderに参加しまして、「こ、これがyukicoderか・・・」と洗礼を受けた気分であります。(←ここまで朝)

　(こっからAtCoder後→)もう問題行っちゃいます。まずは No.564 です。問題名は「背の順」、自分の背の高さがクラスで何番目か気になっちゃう系男子、なる君が登場するおはなしです。いつものように２以上の自然数Nがもらえるので、なる君の身長Hとクラスメイトの身長H[N-1]を使って、なる君がクラスで何番目の身長なのか教えてあげてください。

　ここで私は「身長と言えば小さい順だろ」みたいな固定観念があったせいでWAを食らうわけですが(←サンプルケースみてない(2回目))、みなさんは勘違いしませんでしたかね。

#include <iostream>
using namespace std;

int main(void){
    int h, N;
    cin >> h >> N;
    int H, ans=1;
    for(int i=1; i<N; i++){
        cin >> H;
        if(H>h)ans++;
    }

    if(ans%10==1){
        cout << ans << "st\n";
    }else if(ans%10==2){
        cout << ans << "nd\n";
    }else if(ans%10==3){
        cout << ans << "rd\n";
    }else{
        cout << ans << "th\n";
    }

    return 0;
}

　解法はですね、はじめになま君がクラスで一番身長が高いと仮定(ans=1)してあげてですね、なま君よりも身長の高いおともだちが出てくるたびに、なま君の順位を一つ落としてあげるんですね(ans++)。もちろん最下位から一つづつ上げてやってもいいんですよ。私は大きい順にむかついた(自業自得)のでしませんでしたが。

　んじゃ次！　No.565 です。問題名は「回転拡大」、yukicoは問題名が日本語なのでわかりやすくていいですね。いつもと違ってH×Wの画像を時計回りにR度回転させてK倍に拡大して返せばOKです。いつものNくんが出てこないから(←関係ない)簡単でした(なお"<="の"="忘れて提出1回でACもらえなかった模様)。

　ちな「これで絶対合ってる」と思って提出した2回目のコードですが、問題のテストケースが死んでたようで、問題の難易度がコンテスト中に上がって下がってテストケースが直ってACにしてもらうのに15分くらいかかりました。今回はunratedだってさ、もともとyukicoにレーティングはないけどね。

#include <iostream>
using namespace std;
int main(void){
    int R, K, H, W;
    cin >> R >> K;
    cin >> H >> W;

    char c[H][W];
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin >> c[i][j];
        }
    }

    if(R==0){
        for(int i=0; i<H; i++){
            for(int kk=0; kk<K; kk++){
                for(int j=0; j<W; j++){
                    for(int k=0; k<K; k++){
                        cout << c[i][j];
                    }
                }
                cout << endl;
            }
        }
    }else if(R==180){
        for(int i=H-1; i>=0; i--){
            for(int kk=0; kk<K; kk++){
                for(int j=W-1; j>=0; j--){
                    for(int k=0; k<K; k++){
                        cout << c[i][j];
                    }
                }
                cout << endl;
            }
        }
    }else if(R==90){
        for(int j=0; j<W; j++){
            for(int kk=0; kk<K; kk++){
                for(int i=H-1; i>=0; i--){
                    for(int k=0; k<K; k++){
                        cout << c[i][j];
                    }
                }
                cout << endl;
            }
        }
    }else if(R==270){
        for(int j=W-1; j>=0; j--){
            for(int kk=0; kk<K; kk++){
                for(int i=0; i<H; i++){
                    for(int k=0; k<K; k++){
                        cout << c[i][j];
                    }
                }
                cout << endl;
            }
        }
    }

    return 0;
}

　(K倍にする)イコール(K回おなじものを出力する)です。「4重ループが汚い」とかいう声は却下です。競プロerはACこそ正義です←

　んで次は1時間悩んで結局「実装重ッ！」ってなってとばした No.566 です。問題名は「だいたい完全二分木」、いつものように自然数NKがいただけるので、１から(2^NK)-1 までの自然数を二分探索木につっこむと、深さがK以上3K以下になるような１から(2^NK)-1 までの自然数の順を出力すればいいらしいんだけど、ちょっと考えると、ちゃんとアルゴリズム組めば、深さはKぴったりでいい(というかその方が組みやすそう)なことが分かるんだけど、実装が重い。いや完全二分木作って最後の3,1,2を3,2,1にかえるだけなんだけどね。今年のICPC国内予選のB問題と同じくらいアルゴリズム難易度と実装難度がかみあってない。絶対星2じゃない！(←自分が解けないだけ)　

　私は結局飛ばしちゃったんですが、なんとなんと、想定解法のうち1つに、

二分探索木に $1, \dots, N$ をランダムな順序で挿入したときの高さの期待値は最大でも 4.311lnNで抑えられることが知られている(参考)．ここで， $N = 2^{K}$ とするとおおよそ3Kとなる．
実際，(1,…,N)をランダムに並び替えた操作列は高確率で条件を満たす(ただし，K=2のケースは1/3の確率で高さが1になるので注意が必要である)．興味があればUTPC 2011 Jを解くとよい．

とか書いてあって、なるほどWA出してもペナルティのないyukicoならではだなあと思った。冒頭のはそれ。

　次の問題？　これに1時間かけたんだから解いてるわけないよね。うん。

　とか言ってる間に日付をまたいでしまいました。あはは。またね。おやすみ。