naoya_t@hatenablog

いわゆるチラシノウラであります

TCO17 Round1A

f:id:n4_t:20170402122224p:plain
2017 Topcoder Open Algorithm - 2017 Topcoder Open
Round 1A (Qualification Round)

4/2 1:00am JST

もう2年以上SRMに顔を出していないけどArena(Javaアプレット版)がちゃんと動いてよかった。(Web Arenaはログインを試みると無限リダイレクトに陥って未だにたどり着けない)

で、2問ACで409位。上位750人枠に入れた*1ので無事Round 2進出。
レーティングの降下(-60)はDiv1/Div2混合のTCO予選ということで想定内。

次のRound 2は5/21 1:00am JST(だいぶ先だ)。

Easy (250): PingPongQueue

やるだけ、かな。シミュレーション。

class PingPongQueue {
    public:
    vector<int> whoPlaysNext(vector<int> skills, int N, int K) {
        int M = skills.size();
        vector<int> table(skills.begin(), skills.begin()+2);
        queue<int> q;
        for (int i=2; i<M; ++i) q.push(skills[i]);
        vector<int> wins(51, 0);

        sort(table.begin(), table.end());

        for(int k=1; k<K; ++k) {
             wins[table[0]] = 0;
             ++wins[table[1]];

            q.push(table[0]);
            table[0] = q.front(); q.pop();

            if (wins[table[1]] == N) {
                q.push(table[1]); wins[table[1]] = 0;
                table[1] = q.front(); q.pop();
            }

            sort(table.begin(), table.end());
        }

        sort(table.begin(), table.end()); // これ要らない
        return table;
    }
};

連勝数カウンタを(他の皆さんの実装では1つだけ、最後の勝者の分しか持っていないところを)全員分持ってるのは冗長だけれど、もし1つだけでやってたら後述の(N=1の)罠に自分もはまっていたと思う。
// 最初、連勝数カウンタをskills.size()+1分しか用意していなくてSEGV出してた...

Challenge Phase

部屋は静かだった。
人のコードはちら見したけど、落とせそうなのを見抜けず。

System Test

Passed (25'52'', 154.90 pts)

部屋唯一のredcoderさんがsystem testでEasy落としてる…なんでこれで落ちるんだ?

あ、なるほど、(連勝者を破った)新しい勝者の連勝数を1とするのはいいんだけど、Nとの比較をしていなくてN=1のときでも残っちゃう実装なのか。
自分のやつが通ったのは連勝数カウンタを人数分持ってて、新しい勝者かとか関係なく一律にincrementしていたおかげだろう。

でも、Challengeでこのredさんのコードを見て見抜けなかった(自分を含む)部屋の皆さんがEasy通せたのはたまたま感ある。

Medium (500): CheeseSlicing

DPで書きかけて怪しくなったのでメモ化再帰で。
XYZ各軸で厚さSの所でカットして合計表面積が最大になるカットを採用。
可能な分割をすべて試すのと同じ結果になるのを確かめてからsubmit。

#include <vector>
#include <algorithm>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()

int mm[101][101][101];

class CheeseSlicing {
    int S;

    int sub(vector<int>& x) {
        int m = mm[x[0]][x[1]][x[2]];
        if (m >= 0) return m;

        int at = (int)(min_element(all(x)) - x.begin());
        if (x[at] < S) {
             mm[x[0]][x[1]][x[2]] = 0;
            return 0;
        }

        int s = x[0] * x[1] * x[2] / x[at];

        vector<int> y(all(x));
        rep(i, 3) {
            if (x[i] >= S*2) {
                x[i] -= S; y[i] = S;
                int si = sub(x) + sub(y);
                s = max(s, si);
                x[i] += S; y[i] = x[i];
            }
        }

        mm[x[0]][x[1]][x[2]] = s;
        return s;
    }

public:
    int totalArea(int A, int B, int C, int _S) {
        S = _S;
        rep(a,101) rep(b,101) rep(c,101) mm[a][b][c] = -1;
        rep(a,S) rep(b,101) rep(c,101) mm[a][b][c] = 0;
        rep(a,101) rep(b,S) rep(c,101) mm[a][b][c] = 0;
        rep(a,101) rep(b,101) rep(c,S) mm[a][b][c] = 0;

        vector<int> x(3);
        x[0]=A; x[1]=B; x[2]=C;
        sort(all(x));  // これ別に要らない
        return sub(x);

    }
};
Challenge Phase

割とみんなDP書いてるのね。
謎のO(1)実装の人が1人落とされてた。

System Test

Passed (38'44'', 245.43 pts)

Hard (1000): 開いてない

レーティング

1671→1611 (-60)
もうちょい下げるかなと思ったのだけれど(Div1/Div2の区別がないTCOレーティング落とすのは想定内)
反映にかなり時間がかかっていたようだけど、やっぱりDB壊したとか何かトラブルがあったんだろうか。
f:id:n4_t:20170403140630p:plain
というか、本当に久しぶりなんだなというグラフ

*1:得点が0を超えた参加者は714人しかいなかったので714人通過か。それにしても予選参加者987人って少なくない?