CODE FESTIVAL 2017 予選A 参加記

結果

A,B,C問題を解いて3完。C問題でかなり手間取ってしまったのが痛かった。時間があってもD問題を解けたがどうかはわからないが、しっかり考えてみたかった。

 一応CODE FESTIVALの方にエントリーはしてみているけど、まぁ無理だわな。

A問題

 substrで先頭4文字だけ取ってきて比較するだけ。今考えると4文字未満のときを考慮してなかったのでC++の仕様に救われたか。まぁ親切にも入力例3で3文字のケースがあるので、問題があってもWA出す前に気づけてはいたと思うけど。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string S;
    cin >> S;
    if (S.substr(0, 4) == "YAKI")
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B問題

 2回押すと元に戻るだけだから各ボタンについて押すか押さないかだけが重要。

 行ボタンのうちi個、列ボタンのうちj個を選ぶと  i \times M + (N - i) \times j - i \times j 個が黒くなるはずで、それで解ける。

 コードだと頭が悪くて列を先に押すのと行を先に押すので結果が変わると勘違いしている。何をやっているんだ。普通に二つとも同じ式じゃないか……。というか順番によって結果が変わると思ってしまうのがかなりセンス悪い気がする。頑張ろうな。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i * M + (N - i) * j  - i * j== K
                    || j * N + (M - j) * i - i * j== K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C問題

 最初は

  • HとWが両方奇数のとき、奇数個の文字が1個、それ以外の文字は偶数個
  • そうでないとき全部の文字が偶数個

で解けると勘違いしてコードを書き始めてしまったんだけど、入力例2で失敗してちょっと困る。ここで小手先の回避方法として

  • HとWが両方2以上の時は4回以上表れている文字が最低1個は必要

という条件を付け足して、とりあえずサンプルだけ通るようにして提出してしまい、当然WA。

 しばらく考えてから、4個必要になる領域は角だけじゃないことに気づいて、HとWの偶奇によって偶偶 or 奇奇 or 偶奇(奇偶)で場合分けして書き直したが、まだ1個だけWAが出るようになった。

 どうしてもわからなかったのでそれぞれの場合分けに一個ずつassert(false)を仕込んでみたところ、奇奇のところでWAがREになったので、ここで変なことが起きていると判断した。今回はペナルティがなしということだってのでこういう邪悪なハックをやることに対する抵抗がちょっと小さかった。

 で、何が間違っていたかというと、4個以上出てくる文字が奇数になっている場合というのを考慮していなかった。たとえばaが5個出てきて、1個を中央に使って4個を対象的に使うとか、そういうことがありえるんだ。気づいたらすぐ直せてAC。結構大変だった。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0;
    int num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    if (H % 2 == 0 && W % 2 == 0) {
        if (odd_num == 0 && H * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else if (H % 2 == 1 && W % 2 == 1) {
        if (odd_num == 1 && (H - 1) * (W - 1) <= num4 * 4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        //必ずHが奇数ということにする
        if (H % 2 == 0)
            swap(H, W);

        if (odd_num == 0 && (H - 1) * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

 場合分けが美しくないと思ったのでちょっと書き直してみた。まぁ本番でこれを書きにいくことはしないかなぁ。でもこれの方が解法をちゃんと理解した上でのコードっぽい気はする。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0, num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    //4個使う領域(たとえば右上)を求めるときの長さ
    int h = (H % 2 == 0 ? H / 2 : (H - 1) / 2);
    int w = (W % 2 == 0 ? W / 2 : (W - 1) / 2);

    if (odd_num == (H % 2 == 1 && W % 2 == 1)
            && h * w <= num4)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

D問題

 時間もなかったので、単純にRYGBの順で塗れるだけ塗ってみるとか、できるだけバランスよく塗ってみるとか、簡単な方法で貪欲にやっていくのを試してみたけどWA。間違ってるパターンをいろいろ出してみて眺めているうちに時間切れ。

 ある場所に対して同じ色を塗れない位置が角の利きに似ているので一瞬Rotated Bitboardみたいな考え方が頭をよぎったんだど、それを推し進めることができなかった。マンハッタン距離は45度回転させてみるというの、ちょっと気に留めておいていいパターンだと思う。

AtCoder Regular Contest 083 参加記

結果

 C問題とD問題の2完。C問題で4WA出しながら45分以上かかって無茶苦茶焦ったけれど、なんとか落ち着きを取り戻してD問題まで通せたのは良かった。

 Rating:1521→1535(+14)

f:id:tokumini:20170916235105p:plain

C問題

 最初は貪欲法とかでできるのかといろいろ考えていたけど、場合分けが難しすぎて断念。それぞれの入力値がそこまで大きくないので全探索で解けるだろうと判断したが、愚直な全探索ではまともに実行が終わらなかった。値を出力して観察すると、waterやsugarが同じものを何度も訪れているっぽいので訪問フラグを付けてみると高速になってACできた。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

long long A, B, C, D, E, F;
long long ans_water = 0, ans_sugar = 0;

//0で初期化するとwater = 0がそのまま残り1つだけWAとなる
double max_percentage = -1;
bool visit[3001][3001];

void DFS(long long water, long long sugar) {
    //F以下でないとダメ
    if (water + sugar > F)
        return;

    //溶け残ったらダメ
    if (water / 100 * E < sugar)
        return;

    //訪問フラグを確認
    if (visit[water][sugar])
        return;

    //作った砂糖水の濃度
    if (water != 0) { //0除算を避ける
        double tmp = 100.0 * sugar / (100.0 * water + sugar);

        if (tmp > max_percentage) {
            max_percentage = tmp;
            ans_water = water;
            ans_sugar = sugar;
        }
    }
    visit[water][sugar] = true;

    //操作1
    DFS(water + 100 * A, sugar);
    //操作2
    DFS(water + 100 * B, sugar);
    //操作3
    DFS(water, sugar + C);
    //操作4
    DFS(water, sugar + D);
}

int main()
{
    cin >> A >> B >> C >> D >> E >> F;

    DFS(0, 0);

    cout << ans_water + ans_sugar << " " << ans_sugar << endl;
}

D問題

 問題の把握をしてNの大きさからいって3重ループは大丈夫だろうというところでワーシャルフロイド法が思い浮かんだ。

 まず最初に与えられた2次元配列Aの和を保持しておいて、そこから要らないものを削除していけばいいだろうと発想。

 元の2次元配列Aを3重ループで開始点、経由点、終端点と迂回する順と比較していって、より短いものがあったら最短としておかしいので-1を出力して終わり、等しかったら直接行く道は削除できるのでその分を和から引く、という方針でやったところ、半分くらいがACとなったので大まかな方針としてはあっているんじゃないかと思った。

 サンプルは全部通ってしまうので残りのWAを取るためには自分で間違っているケースを考える必要があったが、最初に正方形のように辺が張っている状態を考えて

f:id:tokumini:20170916235922p:plain

4
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
というのを試してみると答えが4になるべきところを0にしていて、まさにこれが残りの間違いだった。これはたとえば1から4へ行くルートは2を経由するのと3を経由するので2パターンあり、その2回の両方で直接ルート分を引いてしまっていたので答えがおかしくなっているということだった。よってあるノードからあるノードへの辺をすでに削除しているかを2次元配列で保持していくことでACとなった。

#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

bool flag[301][301];

int main()
{
    int N;
    cin >> N;
    vector<vector<long long> > A(N, vector<long long>(N, 0));
    long long sum = 0;
    REP (i, N) {
        REP (j, N) {
            cin >> A[i][j];
            sum += A[i][j];
        }
    }
    //同じ辺を2回カウントしているので2で割る
    sum /= 2;

    REP (i, N) { //経由
        REP (j, N) { //開始
            for (int k = j + 1; k < N; ++k) { //終端
                if (i == j || i == k)
                    continue;
                if (A[j][i] + A[i][k] < A[j][k]) { //より短く行けたらおかしい
                    cout << -1 << endl;
                    return 0;
                }
                if (A[j][i] + A[i][k] == A[j][k]) { //同じコストでいけたら直接辺は削除できる
                    if (flag[j][k] == false) { //直接辺を削除するのは1回だけだからフラグを持つ
                        sum -= A[j][k];
                        flag[j][k] = true;
                    }
                }
            }
        }
    }
    cout << sum << endl;
}

E問題

 問題文を把握したくらいで時間切れ。700点問題とはいえちょっと解ける気はしなかった。

AtCoder Regular Contest 067 反省会

C,D問題を通しての2完で322位でした。 レートは1325から1308へ。完全に停滞している。

すっかり忘れててchokudaiさんのツイートを見てからの参加だったので11分遅れでのスタートでした。

C問題 『Factors of Factorial』

最初約数の個数を求めるのはN!じゃなくてNだと思い込んでしまったのでN \leq 1000だから素数は37まで容易すればいいかな〜と気軽に考えていたけど、サンプル合わないところでやっと気づいた。どうしようか悩んだけど、結局ググッて997までの素数をコピペしてきて凌ぐことに。その際にNが大きい素数になった時のこと考えてans \leq 1ではans = 2にするみたいな意味不明な処理を消し忘れていて1WA出してしまった。

#include <bits/stdc++.h>
using namespace std;
const int MOD = pow(10, 9) + 7;

int m[168] = {0};
int p[] = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71, 73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173, 179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281, 283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409, 419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541, 547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659, 661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809, 811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941, 947 ,953 ,967 ,971 ,977 ,983 ,991 ,997
};

int main()
{
    int N;
    scanf("%d", &N);
    for (int j = N; j >= 2; j--) {
        N = j;
        for (int i = 0; i < 168; i++) {
            while (N % p[i] == 0) {
                m[i]++;
                N /= p[i];
            }
        }
    }
    long long ans = 1;
    for (int i = 0; i < 168; i++) {
        ans *= m[i] + 1;
        ans %= MOD;
    }
    printf("%lld\n", ans);
}

D問題 『Walk and Teleport』

普通に貪欲やるだけでは? と思って提出したらWA。理由は10^{9}同士の掛け算によるオーバーフローなんだけど、このときには気づかず「一番大きいギャップにあたったら一度一番右までテレポートしなきゃいけないんだ」とかわけのわからない考察を始めてしまい、めちゃくちゃ時間かかってしまった&3WA。変数をとりあえずlong longで取る癖をつけておいた方が(競プロ的には)いいんだろうなぁ。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, A, B;
    vector<int> X;
    scanf("%d%d%d", &N, &A, &B);
    X.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &X[i]);
    }
    long long ans = 0;
    for (int i = 1; i <= N - 1; i++) {
        ans += min((long long)A * (long long)(X[i + 1] - X[i]), (long long)B);
    }
    printf("%lld\n", ans);
}

E問題 『Grouping』

さっぱり方針がわからなかった。配点から見てそんなに難しくはないのかなと思ったけど、逆に典型題みたいな感じだと僕にはわからないと思ってほぼ諦めてしまった。

解説読んだら「DP[i][j] = i人以下のグループのみでj人使っている場合の数」というDPを考えるとのこと。DPで考えるなら最終的なDP[N[N]]などが答えになっているはずで、どういうものか全然思いつかなかったんだけど、なるほどこうするものか。2次元的なDPを解いた量が圧倒的に少なすぎて発想が出てこないな。Nの大きさ制限からなんとなく察し取れたりするものなんだろうか。

F問題 『Yakiniku Restaurants』

おそらく通すことはできないとわかってはいたけど、E問題よりもこっちのほうが考えてるふりができるので問題のページを開いて眺めていた。なにもわからなかった。