naoya_t@hatenablog

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

June Cook-Off 2017

f:id:n4_t:20170619041455j:plain
https://www.codechef.com/COOK83
6/19 1:00am JST〜 (2.5hrs+30min)

3完70位→5★に昇進、であります。


CodeChef Ratingが2028とかになってるけど、CodeChefのレーティングの仕組みが分かっていない。
いや勿論レーティングのメカニズムに関する記述は読んだのだけれど。
現状Long Challengeで1813、 Cook-offで1643、Lunch Timeは未レーティング
それらとは別にCodeChef Ratingというのがあるわけだけど、普通それらの平均とかになったりしないのかな。


Centeroid (CENTREE; 169, 19.26%)

https://www.codechef.com/COOK83/problems/CENTREE
最初に開いたのがこれ
いや1問目に解くには面倒すぎる
皆さん他のやつから解いてるみたいだしパス

Ada and crayons (ADACRA; 2143, 52.69%)

https://www.codechef.com/COOK83/problems/ADACRA
↑↓↑↑↓を任意区間でひっくり返して最短で揃えるやつ。ceiling(境目の数/2)。
→AC

// AC解
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)

int main() {
    int T; cin >> T;
    rep(t,T){
        string s; cin >> s;
        int N = s.size();
        int c = 0;
        rep(i, N-1) {
            if (s[i] != s[i+1]) ++c;
        }
        int ans = (c+1)/2;
        cout << ans << endl;
    }
    return 0;
}

SnackUp (SNACKUP; 1194, 52.65%)

https://www.codechef.com/COOK83/problems/SNACKUP
・審査員n人、料理レシピの種類n種類。
・ラウンドr回で、各ラウンドではk種類のレシピを選んで2皿ずつ用意し、k人の審査員に食べさせる。各審査員が食べる2皿は別々のものであること。
・全審査員がすべてのレシピを2回ずつ味わえるように采配しろ

各ラウンドで2k皿、これがrラウンドだから2kr[皿]。
審査員n人でレシピn種類で2回ずつだから2n^2[皿]。
これが等しいはずだから2kr=2n^2
kr=n^2
とりあえずk=r=nでどう?
審査員n=3人・レシピn=3種類だったら、3ラウンドで審査員を3人ずつ呼んで
R1: 12, 23, 31
R2: 31, 12, 23
R3: 23, 31, 12
みたいに1つずつずらしたレシピを出すのはどうか。
各ラウンドで用意すべき皿はすべて3レシピ各2皿になるし、審査員視点でも
judge1: 12, 31, 23
judge2: 23, 12, 31
judge3: 31, 23, 12
と、ひと通りのレシピを(ラウンド内での重複なしに)2回ずつ味わえている。
n=4なら
R1: 12, 23, 34, 41
R2: 34, 41, 12, 23
R3: 12, 23, 34 ,41
R4: 34, 41, 12, 23
審査員視点では
judge1: 12, 34, 12, 34
judge2: 23, 41, 23, 41
judge3: 34, 12, 34, 12
judge4: 41, 23, 41, 23
うまく行きそうじゃん
→AC

// AC解
#include <iostream>
#include <cstdio>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);++var)

void solve(int n) {
    int r=n, k=n;

    printf("%d\n", r);
    rep(i, r) {
        printf("%d\n", k);
        rep(j, k) {
            int sh = 2*i +j;
            int a = sh % n;
            int b = (sh+1) % n;
            printf("%d %d %d\n", 1+j, 1+a, 1+b);
        }
    }
}

int main() {
    int T; cin >> T;
    rep(t,T){
        int n; cin >> n; // 2-100
        solve(n);
    }
    return 0;
}

Centeroid (CENTREE)

再訪。再パス。

Knight Covering (KNICOV; 68, 5.12%)

https://www.codechef.com/COOK83/problems/KNICOV
3段まで。何かパターンがあるのか?あるいはDPとか?
一旦パス。

A Study in Bake Street (ADADET; 24, 7.57%)

https://www.codechef.com/COOK83/problems/ADADET
ほとんど解かれてないけど…とりあえず問題を読む。
・とりあえずanswer配列を-1で満たす
・ビルを右側から順に訪れて、屋上から左方向に(手前から)1つずつビルを見ていく。見えたビルの最大仰角を記録しておく(水平方向すなわちθ=0から始める。屋上位置がこの最大仰角より下のビルは手前のビルの陰に隠れるからスキップする)
見える全てのビルに(というかanswer配列に)、今立ってるビルの番号をマークする。
・既にマーク済みの(もっと右にあるビルが見通せる)ビルに当たったら、自分はそのビルと、そのビルをマークしたビルの屋上を結ぶ線より下にいるし、そのビルより上に見えるビルは全て、そのビルをマークしたビルからも見えるはずだからここでスキャンを中止し、立ち位置を1つ左にずらす
・ちなみに屋上が視線上にある場合(斜めに一直線に並んでいる場合)は視野を塞がないみたい
・これで正しい答えは出るはず(サンプルケースも通った)
・計算量は?尺取りというわけではないし、各ビルからの平均スキャン長がnより大幅に小さくなることを期待したいが、例えばy=\log(x_n-x)みたいな、なだらかな、右に高いビルがなくて左隣りしか見えないような並びになってたら最悪で、\displaystyle\frac{n(n-1)}{2} 回のスキャンになるよね
・とりあえず投げた
→AC(え?これで通っちゃっていいの?)

いや、1\le n\le10^5, 1\le x_i, h_i\le10^6 で、それぞれ整数で、同じ高さのビルはない、という制約ではそのlogカーブみたいな並びは作れないのか?
・すべてのビルは左隣りより1だけ低く、ビルの間隔だけが1ずつ順に狭まっていく方式:ビル10^5本で合計5\cdot10^9 近くのスペースが必要。幅10^6ではビルは1414本しか立てられない
・ビルの間隔は同じで、左から10^6,10^6-1,10^6-3,10^6-6,\cdotsと順に傾斜をきつくしていく方式:同じく1414本しか立てられない
・ということは、部分的にlogカーブになっていてもその区間長は高々1414
・とはいえ、幅1414のlogカーブを70組並べたようなデータだったらどうするよ
という鬼畜サンプルデータを作って試したらローカルで9.5秒かかった。用意されてたテストケースが易しかっただけか。(想定解は多分もっと賢いやつだろう)

ADADET: ~10 minutes before the round I generated new test data, but solutions of testers didn't match! I got very nervous, it turns out that I was comparing files with diff and the testers output were in differente format (spaces, line breaks). Hint: Think in the structure of the convex hulls.

...

you basically have to maintain a upper convex hull going downwards while going from N to 1
notice that if you have the convex hull maintained for an interval [a..b] , then it can be extended to [a-1,b] or [a,b+1] easily if its stored in a deque , so sort the values according to height and keep a dsu and do small to large merging to merge deques.


convex hullで考えろって事なんだけど。どゆこと?

あ、鬼畜データを作る時に考えていたようなlogカーブ的なやつを(左下から右上に膨らむ)凸包と見て、使えるやつ(ターゲットになるやつ)だけで凸包を作って、一番近いのを撃つ、ってこと?
いや、例えばサンプルケースの左から3番目4番目の高さが逆だったら 5 5 4 -1 7 7 -1 になるはずだけど、この場合、描かれる凸包ってどんな形?
(未解消)

// AC(え?これで通っちゃっていいの?)解
// いろいろ略
void solve(int n, vector<int>& x, vector<int>& h) {
    vector<int> ans(n, -2);
    for (int me=n-1; me>0; --me) {
        int xm=x[me], hm=h[me];
        double thmax = 0.0;
        for (int you=me-1; you>=0; --you) {
            if (ans[you] > me) break;
            int xy=x[you], hy=h[you];
            if (hy <= hm) continue;
            int dx = xm-xy, dh = hy-hm;
            assert(dx > 0 && dh > 0);
            double th = atan2(dh, dx);
            if (th >= thmax) {
                ans[you] = me;
                thmax = th;
            }
        }
    }
    for (int i=0; i<n; ++i) {
        printf("%d", 1+ans[i]);
        putchar((i == n-1) ? '\n' : ' ');
    }
}

int main() {
    int T = loadint();
    vector<int> tmp(2);
    rep(t,T){
        int n = loadint();
        vector<int> x(n), h(n);
        rep(i, n) {
            loadvec(tmp, 2);
            x[i]=tmp[0], h[i]=tmp[1];
        }
        solve(n, x, h);
    }
    return 0;
}

Knight Covering (KNICOV)

再訪。
(とりあえずn\lt mになるように適宜swapした)
・1段の場合、全部をknightで埋めるしかないから答えはm。
・2段の場合、(1列のケースは1段で処理済)、2列なら全埋め、3列〜6列なら中2列を埋める、7列8列なら中3、4列を埋める、以降(6列ブロックを取れるだけ、それぞれ4埋め)+残りブロック(全埋め)。
・3段の場合、(1列2列のケースは1段2段で処理済)、3列〜6列なら中2列の上2段を埋める、7列8列なら中3、4列を埋める、以降…ってこれ2段のケースと同じなのか?
という考えで投げたやつがWA;


マジデスカ…

// WA解
int solve(int n, int m) {
    if (n > m) swap(n, m);
    assert(1 <= n && n <= 3);
    assert(n <= m && m <= 50);
    int ans;
    switch (n) {
        case 1: {
            ans = m; break;
        }
        case 2: case 3: {
            if (m < 6) {
                ans = 4;
                break;
            }
            int q = m / 6, r = m % 6;
            ans = 4 * q;
            switch (r) {
                case 0: break;
                case 1: ans += 2; break;
                default: ans += 4; break;
            }
            break;
        }
    }
    return ans;
}

int main() {
    int T = loadint();
    rep(t,T){
        vector<int> tmp; loadvec(tmp, 2);
        int n=tmp[0], m=tmp[1];
        int ans = solve(n, m);
        printf("%d\n", ans);
    }
    return 0;
}

Centeroid (CENTREE)

再々訪。
例えばn=2の時とか、centerが存在しないよね、と思ってnoを返す(★これは間違い;Lef f(x) be the greatest distance from u to any other vertex of the tree. A vertex u is a center if f(u) ≤ f(v) for any other vertex v.ってことは、一位タイならどちらもcenterを名乗れる)
b=0のとき、n>2なら1つのセンターに他のノードを全部くっつけたやつを返せばいい。
それ以外は、センターと、そこから距離bにあるcentroidを仮定して、センターからの「半径」rがあって(これはcentroidと逆方向に長さrの枝がセンターから1本伸びてるイメージ)centroidから見たセンター側の全てがn/2以内に収まる(b+r\le\lfloor\frac{n}{2}\rfloor)必要があって、センター側じゃない方に少なくとも1本、r-bの長さの枝が生えてて、あと残りはcentroidにぶら下げればいいかな、と。
→WA

一位タイが許されることを想定していなかった。なのでセンターからの「半径r」に許される値がもうちょっとあるのを見逃していた(というかn=2,b=0で何も考えずに"no"を返してる)

// WA解
void solve(int n, int b) {
    vector<ii> arc;
    int r, d, rem;

    if (b == 0) {
        if (n == 2) {
            goto no;
        } else {
            for (int i=1; i<n; ++i) {
                arc.push_back(ii(0, i));
            }
            goto yes;
        }
    }

    r = n/2 - b;
    if (r < 1) goto no;

    rem = n - (1 + r + b);
    if (rem < 1) goto no;
    d = r - b;
    if (d < 1) goto no;

    assert(r+b <= n/2);

    rep(i, r*2) {
        arc.push_back(ii(i, i+1));
    }
    for (int i=r*2+1; i<n; ++i) {
        arc.push_back(ii(d, i));
    }
  yes:
    printf("YES\n");
    for (auto p : arc) {
        printf("%d %d\n", 1+p.first, 1+p.second);
    }
    return;
  no:
    printf("NO\n");
    return;
}

int main() {
    int T = loadint();
    vector<int> tmp(2);
    rep(t, T){
        loadvec(tmp, 2);
        int n=tmp[0], b=tmp[1];
        solve(n, b);
    }
    return 0;
}