Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-07-30

Codeforces Unknown Language Round #3

19:47

Unknown Language Roundだし久しぶりに参加記.

今回はPikeという言語.聞いたことない.C++から型付けをちょっと緩めて,オブジェクトを積極的にコピーするようにした感じ.

結果.

ABCDEFGHIJTotalPlace
00:1902:48(+2)00:2300:4502:3601:2501:54(+2)02:23(+2)00:59-93213th

せめて一桁順位は取りたかったんだけど残念.

A

とりあえず配布されたソースをビルドしながらBegginer's tutorialを読む.C++の制御構文はほとんど同じように使えるらしい.入出力がちょっと独特なのと,スクリプト言語の例に漏れず配列と連想配列が特別扱いなくらいっぽい.

さしあたり必要なのは文字列→整数変換と入力のsplit方法なのでそれっぽいのを探す.変換についてはType Conversionsという節が見えたので開いてみたら,直接(int)とかキャストすれば良きに図らってくれるらしい.文字列に関してはWorking with Stringsという章があったので見てみたら,/でsplitできるということが書いてあった.iostreamの<<のようなノリを感じる.

あとは配列をarray(int)でキャストすると中身も全部intになるとか.

最低限必要な情報は揃ったのでコーディング.1辺を敷き詰めるのに何枚必要か求めればいいよね.

int main() {
    string s = Stdio.stdin->gets();
    array(int) list = (array(int))(s / " ");

    int wc = list[0] / list[2] + (list[0]%list[2] > 0 ? 1 : 0);

    if(wc*wc <= list[1]) write("YES\n");
    else write("NO\n");

    return 0;
}

C

Unknown Language Roundは難易度順とは限らないんだよなぁと思いつつ問題を見てみたら,A+Bという名前の明らかに簡単そうな問題が…….

とりあえず開く.500桁の数を足すだけで罠はなさそう.スクリプト言語だしどうせintは多倍長だよねーと思いつつ適当に大きい数を足してみたらちゃんと動いたので提出.

int main() {
    int a = (int)Stdio.stdin->gets();
    int b = (int)Stdio.stdin->gets();

    write(a+b + "\n");

    return 0;
}

B

他には特に簡単そうな名前は見えないし順番にBでも開いてみる.

数列が与えられるので,数列内の全てのペアについて小さい方が大きい方を割り切ればいいらしい.普通に二重ループで試せばいいんじゃね?

……通らない.このアルゴリズムでダメなパターンはありえない.ひどい罠の予感がするからスルーしよう.

D

文字列s1とs2が与えられて,s1をs2に指定された手数以内で変形できるかという問題.えーDPするのーと思いきや,文字列の末尾を1文字だけ削除するか,好きな文字を1文字だけ追加するかしかできないらしい.それなら先頭の一致文字数だけ数えてあとは作りなおすしかない.

文字列の長さを求めるにはsizeofを使えばいいらしい.

int main() {
    int N = (int)Stdio.stdin->gets();
    string s1 = Stdio.stdin->gets();
    string s2 = Stdio.stdin->gets();
    
    int l1 = sizeof(s1);
    int l2 = sizeof(s2);
    
    int i;
    for(i = 0; i < l1 && i < l2; ++i) {
        if(s1[i] != s2[i]) break;
    }

    int turn = 0;
    turn += l1 - i;
    turn += l2 - i;

    write((turn <= N ? "Yes" : "No") + "\n");
    return 0;
}

I

なにやらIの正解者数が多めなので見てみる.え,回転させるだけ?誤差も0.1とかぬるい.

どうせあるだろうと思ってsinとかcosとか書いたら普通に通ったので書くだけ.あと念のため言語側で提供されてるpiの値を使おうと思い,モジュールリファレンスを開く.

int main() {
    int K = (int)Stdio.stdin->gets();
    array(int) list = (array(int))(Stdio.stdin->gets() / " ");

    float sine = sin(K*Math.pi/180);
    float cosine = cos(K*Math.pi/180);

    float x = list[0]*cosine - list[1]*sine;
    float y = list[0]*sine + list[1]*cosine;
    write(x + " " + y + "\n");
    return 0;
}

E

たくさんランプが並んでて,n番のスイッチを押すとnの倍数のランプが点灯・消灯を切り替える.いくつかスイッチを押したときの最終状態を求める問題.

普通にシミュレーションしたらTLE.でもこれ,順番に依存しないよね…….ということは,同じスイッチが偶数回押されてれば無視,奇数回なら1回だけ押したことにすればいい.

ただ,これ使ってもスクリプト言語だしTLEしそうな気がするなぁ.後で考えよう.

F

なんとなくF.

(x+a1)(x+a2)・・・を計算すれば良いらしい.普通に配列でごりごり書けば良さげ.

………初期長さ決まってる配列ってどう書くの?

リファレンスやチュートリアル見ても書いてない.うーむ.あ,なんかArray.pushっていうのがあるぞ.これで伸ばせるんじゃないか.

これを見つけたはいいもののまたハマる.listを初期化してないのと,Array.pushは引数を破壊しないのが原因だった.だいたいC++Rubyをベースに考えてるので,こういう挙動があると引っかかってしまう.

あと配列のコピーを作る方法が良くわからないが,pike array copyとかでぐぐったらa+({})ってやればいいよ,って出てきたので従う.気持ち悪いなぁ.

array(int) mul(array(int) a, int b) {
    int len = sizeof(a);
    array(int) ans = a + ({});
    for(int i = len-1; i > 0; --i) ans[i] = ans[i-1];
    ans[0] = 0;
    for(int i = 0; i < len; ++i) ans[i] += a[i]*b;
    return ans;
}

int main() {
    int N = (int)Stdio.stdin->gets();
    array(int) list = ({});
    for(int i = 0; i < N+1; ++i) list = Array.push(list, (int)0);

    list[0] = 1;
    for(int i = 0; i < N; ++i) {
        int b = (int)Stdio.stdin->gets();
        list = mul(list, b);
    }

    int first = 1;
    for(int i = N; i >= 0; --i) {
        if(list[i] != 0) {
            if(list[i] < 0) write("-");
            else if(!first) write("+");
        }
        if(i == 0) {
            if(list[i] != 0) write(abs(list[i]) + "");
        }
        else if(list[i] != 0) {
            if(abs(list[i]) != 1) write(abs(list[i]) + "*");
            write("X");
            if(i > 1) write("^" + i);
        }
        first = 0;
    }
    write("\n");

    return 0;
}

G

文字列と数値の連想配列を作って,指定されたキーのうち一番小さいものを選ぶ.ただし,キーが配列になかったら最優先で,同じ優先度のものがあったら辞書順最大のものを選ぶ.

連想配列はmappingという名前らしい.普通に書けばいいのかーと思って書く.が,エラーで動かない.

まさかmappingも変更不可能なのか,使えねーと思いながらリファレンス読む.mkmappingという,配列を引数に取って連想配列を作ってくれる関数があるらしいので使ってみる.でもエラー.

いろいろ試してるうちに,dictを初期化してないことに気づく.またこのパターンか.まるで成長していない…….

慌てて投げたらWA.今の候補の数値を記録しておくのを忘れてた.修正して投げる.またWA.よく見たら辞書順最小を返してた…….

くだらないミスで2WAを頂く.痛い.

int main() {
    int N = (int)Stdio.stdin->gets();
    mapping(string:int) dict = ([]);

    for(int i = 0; i < N; ++i) {
        array(string) list = Stdio.stdin->gets() / " ";
        int year = (int)list[1];
        dict += ([ list[0]:year ]);
    }

    int M = (int)Stdio.stdin->gets();
    int curyear = 10000;
    string curname = "";
    for(int i = 0; i < M; ++i) {
        string candidate = Stdio.stdin->gets();
        int year = dict[candidate];
        if(year < curyear) {
            curname = candidate;
            curyear = year;
        }
        else if(year == curyear && candidate > curname) {
            curname = candidate;
            curyear = year;
        }
    }

    write(curname + "\n");
    return 0;
}

H

そろそろBを放置してるのが気になりはじめる.けどまあ,とりあえず解けるのは解いてからBを考えよう.

盤面が与えられて,*の列で表現されている戦艦が互いに接していないかを判定し,最後に戦艦のサイズと個数が合ってるかを判定する問題.サンプルの意味が一瞬分からなかったが,斜めも接触判定あるのかと気づく.

左上からスキャンしていって,*にぶつかったら縦か横に伸ばしていって,ついでに接触判定すれば良さげ.くっついていたらどうせアウトなので,接触は斜めだけ実装すればいい.ただの実装ゲー.

このへんでReference Manualを読み始める.allocate(N)でN要素の配列を作れることを知る.もっと早くに読むべきだった……!

実装して投げて1WA.4以上の長さ(に見える)戦艦があったとき領域外アクセスしてた.

修正してもう1WA.4以上の長さの戦艦があったらその時点でアウトにしなきゃいけなかった.

string get(array(array(string)) field, int row, int col) {
    if(row < 0 || 10 <= row) return "0";
    if(col < 0 || 10 <= col) return "0";
    return field[row][col];
}

int check(array(array(string)) field, int row, int col) {
    return get(field, row+1, col+1) == "0" &&
           get(field, row+1, col-1) == "0" &&
           get(field, row-1, col+1) == "0" &&
           get(field, row-1, col-1) == "0";
}

int main() {
    int N = (int)Stdio.stdin->gets();
    while(N--) {
        array(array(string)) field = allocate(10);
        for(int i = 0; i < 10; ++i) {
            field[i] = Stdio.stdin->gets() / "";
        }

        array(int) count = allocate(5);
        int ok = 1;
        for(int row = 0; row < 10; ++row) {
            for(int col = 0; col < 10; ++col) {
                if(get(field, row, col) == "*") {
                    int width = 1;
                    int height = 1;
                    ok &= check(field, row, col);
                    field[row][col] = "+";

                    //Horizontal
                    while(get(field, row, col+width) == "*") {
                        ok &= check(field, row, col+width);
                        field[row][col+width] = "+";
                        width++;
                    }
                    if(width == 1) {
                        //Vertical
                        while(get(field, row+height, col) == "*") {
                            ok &= check(field, row+height, col);
                            field[row+height][col] = "+";
                            height++;
                        }
                    }
                    int size = max(width, height);
                    if(size <= 4) count[size]++;
                    else ok = 0;
                }
            }
        }
        if(ok && count[1] == 4 && count[2] == 3 && count[3] == 2 && count[4] == 1) write("YES\n");
        else write("NO\n");

        if(N) Stdio.stdin->gets();
    }
    return 0;
}

E

戻ってきた.

やっぱりさっきの方法以外考えつかない.とりあえず実装して最大ケースつっこんでみよう.

モジュールリファレンスを見たらArray.countなる関数を発見.これ使えば一発ですね.

……あれ,普通に一瞬で終わった.結構速いんじゃん.

int main() {
    int N = (int)Stdio.stdin->gets();
    array(int) lamps = allocate(N+1);
    array(string) init = Stdio.stdin->gets() / " ";
    for(int i = 0; i < N; ++i) {
        if(init[i] == "on") lamps[i+1] = 1;
    }

    int M = (int)Stdio.stdin->gets();
    array(int) keys = (array(int))(Stdio.stdin->gets() / " ");
    mapping(int:int) cnt = Array.count(keys);
    array(int) ks = indices(cnt);

    for(int i = 0; i < sizeof(ks); ++i) {
        int k = ks[i];
        if(cnt[k] % 2 == 0) continue;
        for(int j = k; j <= N; j += k) {
            lamps[j] ^= 1;
        }
    }

    for(int i = 1; i <= N; ++i) {
        if(i != 1) write(" ");
        write(lamps[i] ? "on" : "off");
    }
    write("\n");
    return 0;
}

J

区間が3つ連続しているときは全部同じ色にしてはいけない,という条件で複数の区間を塗り分けるとき,何色必要かという問題.

もしかしてこれ,3つ連続してる場所があるときだけ2色で,他のときは1色でいいんじゃないか?ただ実装がミスりそう.まだ解いてないBやろう.

B

やはりよくわからない.non-zero intergersってあるけどそれなら小さいほうから順番に割ってけば解けるよなぁ…….

……ん,non-zero integers?まさかこれ,負数がくるのか?map(list, abs)を掛けて投げてみる.Accepted.なんじゃそりゃー.

int main() {
    int N = (int)Stdio.stdin->gets();
    array(int) list = (array(int))(Stdio.stdin->gets() / ",");
    list = sort(map(list, abs));

    int ok = 1;
    if(list[0] == 0) {
        ok = 0;
    }
    else {
        for(int i = 0; i < N; ++i) {
            for(int j = i+1; j < N; ++j) {
                if(list[j] % list[i] != 0) {
                    ok = 0;
                }
            }
        }
    }

    write((ok ? "" : "NOT ") + "FRIENDS\n");
    return 0;
}

J

3つ連続してる判定なら3重ループ回せばいけるけど,N=1000だし普通にTLEしそう.いいや,とりあえず書いてみよう.

→間に合わず.あとでPracticeで投げたらやっぱりTLEでした.

krotonkroton 2011/07/31 00:52 Eは他にもO(n^1.5)の解法とかありますよ。これだと計算量が見積もれるのでちょっと安心です。
http://ideone.com/cQYkA

tatuyan_edsontatuyan_edson 2011/07/31 13:26 はじめまして。
Cの「どうせintは多倍長だよねー」という辺りに、経験の差を感じます。
多倍長だと思わずに七面倒臭い文字列処理を書いたので…。
既存言語に縛られてるとダメですね。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/osa_k/20110730
 |