Treeone’s Blog

競技プログラミングの記録など

九州大学プログラミングコンテスト2018 (QUPC2018) ABCDFHI問題

10/20(土) に開催された 九州大学プログラミングコンテスト2018 (QUPC2018) の ABCDFHI 問題の writer でした。

beta.atcoder.jp

各問題の解説は既に公開しているので、問題についての適当なコメントとコードを載せていこうと思います。

QUPC2018解説.pdf - Google ドライブ

EGJ 問題はこっち

ei1333.hateblo.jp

A問題

問題ページ : A - QUPC

0 完防止用の問題。正解者は 275 人。

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << 2010 + 4 * n << endl;
}

B問題

問題ページ : B - Tapu & Tapi

これ好きだけど、Wrong Answer が大量発生していて申し訳ない気持ちになった。(ア)
正解者は 199 人。

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

int main(){
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        long long a, b, c;
        cin >> a >> b >> c;
        bool ans = true;
        long long s = a * 100 + b * 10 + c;
        if(s & 1) ans = false;
        s /= 2;
        s -= min(a * 100, s / 100 * 100);
        s -= min(b * 10, s / 10 * 10);
        s -= min(c, s);
        if(s) ans = false;
        cout << (ans ? "Yes" : "No") << endl;
    }
}

C問題

問題ページ : C - Ito Campus

300 〜 400 点くらいの問題がなかなか生えなくて困った。簡単枠を生やすのが難しすぎる。
正解者は B 問題の約半分の 96 人で、予想していたよりも難しかったっぽい。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 1e9;
string s[1000];
queue<P> q;
int h, w, x, sy, sx, gy, gx;
int d[1000][1000], e[1000][1000];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

int main(){
   cin >> h >> w >> x;
   for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) d[i][j] = e[i][j] = INF;

   for(int i = 0; i < h; i++){
       cin >> s[i];
       for(int j = 0; j < w; j++){
           if(s[i][j] == 'S'){
               sy = i; sx = j;
           }else if(s[i][j] == 'G'){
               gy = i; gx = j;
           }else if(s[i][j] == '@'){
               q.push({i, j});
               d[i][j] = 0;
           }
       }
   }
   while(!q.empty()){
       P p = q.front(); q.pop();
       for(int i = 0; i < 4; i++){
           int ny = p.first + dy[i];
           int nx = p.second + dx[i];
           if(s[ny][nx] == '#' || d[ny][nx] != INF) continue;
           d[ny][nx] = d[p.first][p.second] + 1;
           if(d[ny][nx] < x) q.push({ny, nx});
       }
   }
   q.push({sy, sx});
   e[sy][sx] = 0;
   while(!q.empty()){
       P p = q.front(); q.pop();
       if(p.first == gy && p.second == gx){
           cout << e[gy][gx] << endl;
           return 0;
       }
       for(int i = 0; i < 4; i++){
           int ny = p.first + dy[i];
           int nx = p.second + dx[i];
           if(e[ny][nx] != INF || d[ny][nx] <= x || s[ny][nx] == '#') continue;
           e[ny][nx] = e[p.first][p.second] + 1;
           q.push({ny, nx});
       }
   }
   cout << -1 << endl;
}

D問題

問題ページ : D - Novelist

想定は区間スケジューリングだけど、DP で解いた人多そう。
正解者は 62 人で、E 問題よりも少なかった。
水色くらいの人が 4 完できるつもりで作ったけど、実際 4 完できたのは青くらいか?

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 2e9;

int n, m, l;
vector<int> a[100000], b[100000];
vector<P> d;

int main(){
    cin >> n >> m >> l;
    vector<int> t(n);
    for(int i = 0; i < n; i++) cin >> t[i];
    for(int i = 0; i < m + l; i++){
        int city, day;
        cin >> city >> day;
        if(i < m) a[city - 1].push_back(day);
        else b[city - 1].push_back(day);
    }
    for(int i = 0; i < n; i++){
        b[i].push_back(INF);
        sort(b[i].begin(), b[i].end());
        for(int j = 0; j < a[i].size(); j++){
            int tmp = *upper_bound(b[i].begin(), b[i].end(), a[i][j] + t[i]);
            if(tmp < INF) d.push_back({tmp + t[i], a[i][j]});
            else d.push_back({INF, a[i][j]});
        }
    }
    sort(d.begin(), d.end());
    int ans = 0, last = 0;
    for(int i = 0; i < d.size(); i++){
        if(last < d[i].second){
            ans += 2;
            last = d[i].first;
        }
    }
    cout << ans - (last == INF) << endl;
}

F問題

問題ページ : F - Team Making

直前に用意していた最終問題が炎上してしまい、急遽出題することになった問題。
制約に bitDP って書いてあるけど、E 問題の半分以下の 30 人にしか解かれなかった。

#include <bits/stdc++.h>
using namespace std;
 
int N, K, A[20];
long long dp[1 << 20];

int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> A[i];
    dp[0] = 1;
    for(int bit = 0; bit < (1 << N); bit++){
        int i;
        for(int j = 0; j < N; j++) if(!(bit & (1 << j))) i = j;
        dp[bit + (1 << i)] += dp[bit];
        for(int j = 0; j < i; j++){
            if(!(bit & (1 << j)) && A[i] + A[j] <= 2 * K){
                dp[bit + (1 << i) + (1 << j)] += dp[bit];
            }
        }
        for(int j = 0; j < i; j++){
            if(bit & (1 << j)) continue;
            for(int k = j + 1; k < i; k++){
                if(!(bit & (1 << k)) && A[i] + A[j] + A[k] <= 3 * K){
                    dp[bit + (1 << i) + (1 << j) + (1 << k)] += dp[bit];
                }
            }
        }
    }
    cout << dp[(1 << N) - 1] << endl;
}

H問題

問題ページ : H - ukuku

manacher の気持ちになると解ける?
1 億人に解かれると思っていたけど、7 人にしか解かれなかった。

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

int n, r, idx;
string s;
bool f[200001][26];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) s += "$";
    for(int i = 0; i < n; i++){
        cin >> r;
        r /= 2;
        if(s[i] == '$'){
            for(int j = 0; j < 26; j++){
                if(!f[i][j]){
                    s[i] = 'a' + j;
                    break;
                }
            }
            idx++;
        }
        if(i - r - 1 >= 0) f[i + r + 1][s[i - r - 1] - 'a'] = true;
        while(idx <= i + r){
            s[idx] = s[i - (idx - i)];
            idx++;
        }
    }
    cout << s << endl;
}

I問題

問題ページ : I - Buffalo

この問題の tester を引き受けてくれたことがきっかけでうしくんが QUPC に関わることになった。EGJ 問題の writer までやってくれた。
ありがとうしくん。たべるのは最後にしてやる。むしゃむしゃ
1 億人に解かれると思っていたけど、5 人にしか(以下略)

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
long long c[MAX + 1], d[MAX + 1], n, k, a, ans;

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a;
        c[a]++;
    }
    for(int i = 1; i <= MAX; i++){
        long long r = MAX / i * i, sum = 0;
        for(int l = i; l <= MAX; l += i){
            while(r > 0 && l + r >= k){
                sum += c[r];
                r -= i;
            }
            if(2 * l >= k) d[i] += c[l] * (sum - 1);
            else d[i] += c[l] * sum;
        }
    }
    for(int i = MAX; i >= 1; i--){
        for(int j = i + i; j <= MAX; j += i){
            d[i] -= d[j];
        }
    }
    for(int i = 1; i <= k; i++){
        if(k % i == 0) ans += d[i];
    }
    cout << ans / 2 << endl;
}

最後に

面白い問題を生やせるようになりたいね
次回の QUPC は 2022 年です (?)

ACM-ICPC 2018 国内予選 参加記

2018年7月6日(金) に行われた ACM-ICPC 国内予選に参加した.
結果は21位 (大学別9位) で無事国内予選を突破.

国内予選結果 | ACM-ICPC 2018 Asia Yokohama Regional

f:id:treeone:20180715014152p:plain

チーム紹介

今年のチーム名は konjo_jam で,メンバーは Treeone, T1610, 後輩氏.
去年の yellow_jam から先輩が抜けて後輩氏が新たに加わった.


当日まで

今年もチームメンバー全員が集まったのはプロコンサークル内でのチーム決めの時だけ.去年よりもチームの戦力が落ちていて国内予選を突破できるか不安になる.AOJ-ICPC を全然解いていなかった Treeone さんが予選当日までに 100 問くらい埋めていた.えらい.

国内予選当日

[-2:00] 大学の ICPC オンサイト会場に到着.今年は弊学から 4 チーム参加した.

[-0:20] 大雨の影響で T1610 が別のキャンパスから来られなくなり,特別措置を申し込む.

[0:00] 問題文を印刷し,A 問題を後輩氏に任せる.

[0:06] A 問題を AC.後輩氏には C 問題を読んでもらい,Treeone が B 問題に取り掛かる.連鎖消滅パズル並みの虚無.まぁ卓越したコーディングスキルをお持ちなのでね,このくらいは.

[0:11] 大雨による特別措置が認められ,T1610 がリモート参加できることになった.D 問題以降を読んでもらう.

Treeone さんが B 問題をバグらせていてつらそう.後輩氏が C 問題を書けそうなので交代する .
後輩氏もバグらせていてつらそう.何回か PC を交代する.

[0:50] 順位表を見ると B より C の方が解かれていたので,後輩氏の C 問題のコードを読むことにした.計算式が間違っているのを見つけて修正.サンプルが合う.
[1:03] C 問題を AC.

B 問題のバグっている場所を見つけて修正する.サンプルが合う.投げてみる Wrong Answer 悲しいね.
またバグを発見して修正.何故かもう 1WA を叩き出してしまう.
初期化を忘れていた.頭が付いてない.
[1:23] B 問題を AC.

後輩氏から D 問題の概要を聞く.ワクワク枝刈り全探索を実装しようとしていると,T1610 が半分全列挙でできると言うので任せる.
[2:03] D 問題をAC.

D の実装を任せている間に E, F, G を読んでいた.F は幾何で G は構文解析っぽい.人間に解ける問題に見えない.E の浮動小数点数の話は 5 億年ぶりに見た.2 年前期必修のコンピュータアーキテクチャ以来.浮動小数点数の気持ちになると,指数部が変わるときに仮数部の最下位 bit の情報が失われるので,指数部が変わるタイミングを頑張って求める.サンプルが合わないので,気合いでサンプルを合わせる.さすがに合ってる訳ないよな〜と言いながら投げてみる Correct Answer さすが僕.ありがとう,コンピュータアーキテクチャ
[2:39] E 問題を AC.

この時点で 48 位から 17 位に上がる.やっと予選突破を確信できる順位になって安心する.

[3:00] 最終結果は21位.予選突破できるか不安なレベルだったので,個人的にはかなり良い結果.サークルの他のチームは例年以上に冷えていた.弊も 2 チーム通過できるようにならないかなぁ.

反省

途中まで南極並みに冷えていて危ない.一人がリモート参加だったとはいえ,チーム内の連携には課題が残った.つりーわんしゃんが AOJ-ICPC を全然解いていないので,アジア地区までに精進してほしい.

最後に

うしくん焼いて食べるぞ🍴🐮🔥


ICPC 国内予選 2017 参加記

初参加記。チームyellow_jamで http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp に参加しました。

結果

ABCDFを解いて5完で19位。無事、国内予選通過!

f:id:treeone:20170715182639p:plain

チーム紹介

チーム名:yellow_jam
弊学を卒業した偉大な先輩のハンドルネームから

メンバー:強い先輩、強い同期、@treeone79
(名前書いていいか分からないので一応)

当日まで

チーム全員が集まれたのは模擬国内と前日の2回。

同期氏が当日実験で1時間以上遅れそうということで、コンテスト序盤を2人でうまく立ち回る必要があった。

前日に立てた作戦では、僕はまずA問題をやって、その間に先輩がBとCを見て、Cの解法がすぐ思いついたら僕にBを残してくれることになった。

コーチのkonjo氏からは5完目標と言われてたけど、4完できたらいいねーという感じ。

当日

  • -1:30

4限がなかったので15時前には学内オンサイト会場に着いて、ひたすら過去のAB問題の早解きをやっていた。

  • 0:00

問題文を印刷して、僕がAに取りかかる。問題読んですぐに2重ループ回すだけじゃんってなったけど、緊張からか手間取ってしまう。
模擬国内で提出ミスをしたので慎重に提出する。

  • 0:09

A問題をAC。C問題が簡単そうということで、先輩がCをやって僕はBを読む。Bは面倒だけどやるだけっぽい。

  • 0:17

先輩がC問題をAC。Bのコーディングを始める。僕が実装で苦戦してる間に、想定していたよりも早く同期氏が到着して、先輩とDの考察を詰めていた。

  • 0:37

やっとB問題を通す。
先輩がDの実装をしている間に、同期氏と先の問題を読む。
H問題の幾何はINF時間あればできるという気持ちになったけど(それはそう)、国内予選は3時間しかないので切ることにした。

  • 0:52

D問題をAC。4完できてひとまず安心する。この時点で10位とかだったと思う。
EがヤバそうなのでFの考察をする。
同期氏と折り紙をして遊んでいたら、規則性を見つけたので同期氏に説明する。
今日何もコード書いてないじゃんと同期氏を煽って実装を投げる。
途中でバグっていたので全員でコードを読む。
座ってるだけをしている間にEとGを考えるけどよく分からない。

  • 2:40

F問題をAC。この間2時間くらい座っていた。残り20分だけど先輩がEの実装を始める。

  • 3:00

コンテスト終了。5完19位で大学内1位、予選通過できたっぽくて安心。

感想

今まで参加してきたチーム戦の中で一番うまく回っていて良かった。
これ読むと 自分は何も やってない (575) ので、アジア地区予選までには戦力になれるように精進したい。