naoya_t@hatenablog

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

Facebook HackerCup 2018 - Qualification Round

7/7 10am〜7/10 10am JST
予選。72時間の開催期間の好きなタイミングで適当に参加して3問中1問でも通せば良い。(順位は参加のタイミングに依存するもので、QRでは特に意味をなさない)
f:id:n4_t:20180710115453p:plain:w500
facebookのお友達が参加していると結果が"Friends"スコアボードで見える。

競技中はジャッジの結果が分からないのイマイチ
→全完してた

hackercupの問題ってなんか面倒くさい…

A - Tourist (25)

剰余
// そういえばQ#コンでは最初touristが首位にいた。量子計算界でもtouristかよ

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

typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);++var)

int main() {
    int T; cin >> T;
    rep(z,T){
        ll N, K, V;
        cin >> N >> K >> V;
        vector<string> name(N);
        rep(i,N) cin >> name[i];
        ll start = K * (V-1) % N;

        set<int> att;
        rep(i, K) {
            att.insert((int)((start + i) % N));
        }

        printf("Case #%d:", 1+z);
        for (int i : att) {
            cout << " " << name[i];
        }
        cout << endl;
    }
    return 0;
}

→AC

B - Interception (30)

演算子の優先順位に従って式を1つ1つ追っていくと結局、次数が偶数か奇数かに行き着く。
(1乗なら0で0にできるけど0乗は何を入れても1、みたいな)

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

#define rep(var,n)  for(int var=0;var<(n);++var)

int main() {
    int T; cin >> T;
    rep(z,T){
        int N; cin >> N;
        vector<int> p(N+1);
        rep(i, N+1) cin >> p[i];

        printf("Case #%d: %d\n", 1+z, N%2);
        if (N%2) printf("0.0\n");
    }
    return 0;
}

→AC

C - Ethan Searches for a String (45)

文字列Aの前に、Aの先頭文字で終わるようなAのprefixを重ねて(そこで続くように)置いてみて、ethanのアルゴリズムでsubstring検出できなければそれを返す。そういうのがなければImpossibleで。

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

#define rep(var,n)  for(int var=0;var<(n);++var)

bool ethan(string& a, string& b) {
    int La = a.size(), Lb = b.size();
    int i = 0, j = 0;
    while (true) {
        if (i >= La) return true;
        if (j >= Lb) return false;
        if (a[i] == b[j]) {
            ++i; ++j; continue;
        }
        if (i == 0) { ++j; continue; }
        i = 0;
    }
}

string solve(string& a) {
    int La = a.size();
    for (int i=1; i<La; ++i) {
        if (a[i] != a[0]) continue;

        string b = a.substr(0, i) + a;
        if (!ethan(a, b)) {
            return b;
        }
    }
    return "Impossible";
}

int main() {
    int T; cin >> T;
    rep(z,T){
        string a; cin >> a;
        printf("Case #%d: ", 1+z);
        cout << solve(a) << endl;
    }
    return 0;
}

→AC