読者です 読者をやめる 読者になる 読者になる

Codeforces Beta Round #42 (Div. 2)

結果から言うと4完で28位/92位(DIV2/ALL)でした。

Cの問題文読み間違えてロスったり、Dのコーディングにえらい時間かかった挙句にコーナーケース見逃してて一回Hackされたりした。

A - Football

よく分からんけど、頻出のチーム出力。

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    string s,b;
    int m = 0,n;
    map<string,int> data;
    cin >> n;
    rep(i,n){
        cin >> b;
        data[b]++;
        if(data[b] > m){
            s = b;
            m = data[b];
        }
    }
    cout << s << endl;
}

2min Submit. 496Pt.

B - Letter

文字列a,bが与えられる。

aに出てきた文字を使って、bの文字列がつくれるか判定しろ(大文字と小文字は区別される)。

ゴリ押し直感実装。if(~~ !=' ')いらない。

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    string a,b;
    int m = 0,n;
    char used[200] = {0},next[200] = {0};
    bool flag = true;
    getline(cin,a);
    getline(cin,b);
    rep(i,a.length())if(a[i] != ' ')used[a[i]]++;
    rep(i,b.length())if(b[i] != ' ')next[b[i]]++;
    rep(i,26)if(next['A'+i] > used['A'+i])flag = false;
    rep(i,26)if(next['a'+i] > used['a'+i])flag = false;
    cout << (flag?"YES":"NO") << endl;
}

8min Submit. 968Pt.

C - Lucky Tickets

問題文読み間違えてて、与えられた中でつくれる"最大の3の倍数"のつくれる個数を出力しろみたいな問題だと思っていた。(難問のハズなのに・・・。)とみんながSubmitしまくっているのを見て判明したのは、これは単純に二個ずつ組み合わせて何個3の倍数つくれるか問題だということだった。

本番では桁毎に足して倍数判定していたけど、明らかに蛇足で、これだけで足りる。

元々3の倍数(3で割った余り0)なら、他の3の倍数とくっつけあわせりゃドッキング後も3の倍数なので、2で割って余ったら切り捨てる。

余り1と余り2を組み合わせれば余り0になる3の倍数が出来上がる。

少ない方の数分しかドッキングできないからそうする。

#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n;
	cin >> n;
	int data[3]={0};
	rep(i,n){
		int p; cin >> p;
		data[p%3]++;
	}
	int ret = data[0]/2 + min(data[1],data[2]);
	cout << ret << endl;	
}

29min Submit. 1326Pt.

D - Journey

なんかグリッドが与えられて、各マスは一度しかたどれない。

1からはじめて一筆書き的にもどってこれるか。どうやってももどってこれないんだったらワープゾーン設置しても構わないからもどってきなさい。

最初シミュレートするソース書いててめちゃくちゃ時間食ったし、困難なことに気づいて、規則的なループを実装する方針に切り替えたけどそっちの方が明らかに楽だった。

適当に机上計算して成り立つことを確認してそれを打ち込んだ。ワープゾーンは必ず1コで足りる。

正直座標x,y入れ替えるだけでいいのにいちいち似たようなソースが混ざってたり、1,2のケースに至っては完全に手打ち。このケースでHackされたのでそれに通るようにした。

n=1,m=1のケースは与えられない。(2≦nmらしい)

超スパゲッティーソース

int main(){
    int n,m;
    cin >> n >> m;
    if(n == 1 && m == 2){
        cout << "0" << endl;
        cout << "1 1" << endl;
        cout << "1 2" << endl;
        cout << "1 1" << endl;
        return 0;
    }
    if(n == 2 && m == 1){
        cout << "0" << endl;
        cout << "1 1" << endl;
        cout << "2 1" << endl;
        cout << "1 1" << endl;
        return 0;
    }

    if(n == 1 || m == 1){
        cout << "1" << endl;
        cout << n << " " << m << " " << "1 1" << endl;
        if(n==1){
            rep(i,m)cout << n << " " << i+1 << endl;
        }else{
            rep(i,n)cout << i+1 << " " << m << endl;
        }
        cout << "1 1" << endl;
        return 0;
    }

    if(n%2 == 0){
        cout << "0" << endl;
        rep(i,n-1)cout << i+1 << " " << 1 << endl;
        rep(i,m)cout << n << " " << i+1 << endl;
        P c = {n,m};
        rep(i,n-1){
            c.x--;
            cout << c.x << " " << c.y << endl;
            if(i%2==0){
                rep(i,m-2){
                    c.y--;
                    cout << c.x << " " << c.y << endl;
                }
            }else{
                rep(i,m-2){
                    c.y++;
                    cout << c.x << " " << c.y << endl;
                }
            }
        }
    }else if(m%2 == 0){
        cout << "0" << endl;
        rep(i,m-1)cout << 1 << " " << i+1 << endl;
        rep(i,n)cout << i+1 << " " << m << endl;
        P c = {n,m};
        rep(i,m-1){
            c.y--;
            cout << c.x << " " << c.y << endl;
            if(i%2==0){
                rep(i,n-2){
                    c.x--;
                    cout << c.x << " " << c.y << endl;
                }
            }else{
                rep(i,n-2){
                    c.x++;
                    cout << c.x << " " << c.y << endl;
                }
            }
        }
    }else{
        cout << "1" << endl;
        cout << n << " " << m << " 1 1" << endl;
        
        P c = {1,1};
        
        rep(i,m){
            cout << c.x << " " << c.y << endl;
            
            if(i%2==0){
                rep(i,n-1){
                    c.x++;
                    cout << c.x << " " << c.y << endl;
                }
            }else{
                rep(i,n-1){
                    c.x--;
                    cout << c.x << " " << c.y << endl;
                }
            }
            if(c.x == n && c.y == m)break;
            c.y++;
        }
    }
    cout << "1 1" << endl;
}

終了2分前 Submit. 806Pt.

E

コンテスト中チラっと見たけど、なんか速度とか出てきた時点でアレだったので読んでない。

Read.

結果

スコア: 3596

DIV2順位: 28

DIV1順位: 92

レート: 13351543(+208)

感想

あおこーだー!最近単調減少だったので嬉しい!

Dみたいな問題はCodeforcesでしか見かけないなーと思った。柔軟なジャッジシステムならではと感じる。

そういや、Dは"Output any of them."的記述は無かったけど、質問したらやっぱり"Output any of them."だったそうです。

ちゃんと明記してよね!僕が英文読んでないだけかもしれないけど。