ICPC 2020 Asia Yokohama Regional 参加記

ICPC 参加記 競技プログラミング

はじめに

2021/03/17 に行われた ICPC 2020 Asia Yokohama Regional にチーム TigerSone. (etonagisa, nikutto, zaki) で参加しました。

結果は8完で9位でした、前回チーム戦をしたのは 国内予選で3人合わせて競プロブランク12ヶ月という状態で臨みました。

f:id:zaki_joho:20210317193410p:plain

standings

 

コンテスト

A: Aにしては難しくない？添字がバグりまくってるのを nagisa にデバッグしてもらって AC。

B: A 解いて見に行ったら nikutto が +1 してたので応援して AC。

C: nagisa に右手法で解けそう～と言われてグッと睨んだら6行のアセンブリが生える。5行以下を全列挙してシミュレートするプログラムを実装したら一発で通る、天才。

E: nagisa と2分探索と greedy でできそ～とか言ってたけど最後の詰めで怪しくなる。nikutto が助けに来て nagisa が実装して AC。

G: nagisa と nikutto が解いてた。

H: nikutto に投げた。

I: nikutto に投げた。

J: nagisa が 解いた。

K: suffix array 見ながら DP できそうで、コンテスト終了まで解いていたが間に合わず。

 

感想

C 問題が一番好き、Sample Input 4 を入力したら 5行の右手法アセンブリが出てきて感動。

 

大きなミスも無く、チームワークを発揮して実力的にベストな結果を出せたと思います。ICPC は今年で引退です。運営の方々、KMC の人々、そしてチームメイトに感謝しています、ありがとうございました。

 

f:id:zaki_joho:20210318162715j:plain

おまけ

誰も顔写真を送らなかったため、3人ともいらすとやになりました。運営の皆様、ごめんなさい。

f:id:zaki_joho:20210317200425p:plain

team member

 

ICPC 2020 国内予選参加記

ICPC 参加記 競技プログラミング

はじめに

 2020/11/07 に開催された ICPC 2020 国内予選に etonagisa, nukutto, zaki_ の3人でチーム名 TigerSone. で参加し、学内2位全体6位で予選通過しました。横浜でボドゲするのが楽しみです。

 

f:id:zaki_joho:20201107232359p:plain

 

コンテスト開始(?) 

ログインしようとするも database broken とか何とか表示される。メンバー全員がログインできないので、緊急連絡先に電話するも通話中になっていた。サーバー側が壊れてると判断して待機。F5ポチポチしてたらサイレント復旧してた、えぇ…。

 

コンテスト開始

A: zaki, B: nagisa, C: nikutto で分担して実装開始。

A ってこんなに簡単だったけ、A AC (3:50)

B, C は大丈夫らしいので 後ろの問題を見に行く。Dの構文解析パートは簡単だけど n=16 で解けるんか？ E は数を数えないといけなそうなのでこの時点で nikutto に丸投げをキメる。

この辺で nagisa が B AC (11:12)。D を相談するも二人でｳﾝｳﾝ言ってた。

C の実行が終わらないらしいので呼ばれて C を見に行く。問題読んで解法を聞いた辺りで実行が終了した。C AC (14:35)。

nikutto に D を説明したらすぐに 2^n 解法が降ってきた、天才か？ nagisa に見てもらいながら実装する。nikutto に E を投げる。

D を特に事故もなく実装してサンプルが合う。D AC (51:25)。standings 見たら Heno World に次いで2位だった気がする。

nikutto が E 解けそうらしいので nagisa と頑張ってもらうことにする。

ここでまた後ろの問題を見に行く、H: 問題を見てニッコリ、解かせる気、ある？G は制約と最小流量制約が見えてフローだな～復元付きだしやべ～となる。F が解けそうな気がするので考える。

nikutto が部分集合求めるのどうやるんだっけとか言ってたので伝えたら解けたらしい。E AC (1:30:07)。

この時点で G, H が全く通されていなかったので F を3人で解くことにする。ｳﾝｳﾝ言いながら大分嘘言った気がする、ごめんね。

nikutto が頑張って書くらしいので応援してたけどデバッグ間に合わなかった、時間は余裕あったし速い愚直書けばよかったと反省。

 

感想

 Fを通しきって6完したかったが、予選通過したのでまあﾖｼ。

3人とも最近競プロ引退してたけどきっちり本番でパフォーマンス出してくる nikutto と nagisa に感謝です。

2位以下に2完差付けて優勝した __KING__ やべ～。

ICPC 2019 Asia Bangkok Regional 参加記(コンテスト)

ICPC 参加記

はじめに

The 2019 ICPC Asia Bangkok Programming Contest の参加記です.
チーム TigerSone で出場しました.
チームメイトは etonagisa, nikutto です.

5泊7日バンコク旅行となりましたが, とりあえずこの記事ではコンテストについて書きます.

結果は 14問中8完で12位でした. WF行くには11完は必要そうで, つらい.

コンテスト

大体時系列順.

-20分(09:30)

・09:30 から開始のはずだが当然のように遅延する. ボランティアの学生っぽい人も困惑.

-10秒

・突如人力カウントダウンが始まる.

0分

・いきなりコンテストのポータルサイトが落ちていてプリンターと scoreboard が使用不能. どうなってんねん.
・問題文は印刷したものが渡されたが, 14問ある. 多くない?
・とりあえずどれから解けばいいか全く分からないので nikutto が環境設定している間に読むことにする.

10分

・A問題が解ける気がしたのでちょっと書きかけて全然解けてないことに気付く. 後回しに.
・Hが自明らしく eto と nikutto がペアプロを始める.
・依然 scoreboard は壊れているので問題を読み進める.

69分

・Hの実装が全然自明でなくて出力形式もカスだったっぽくて二人が大変そうだった. HをAC(69分).
・ここで scoreboard が復活して他のチームが何を解いてるか問題番号付きで見える. randomized とは何だったのか...
・A, D, F あたりが若干通っていたか.

・K, M がすぐ解けそうだったので nikutto に渡して, eto と D のペアプロを始める.

108 分

・eps の位置が間違っていて 1WA 出したが D を AC.

114分

・nikutto が M を AC.
・A が2秒考え直したら明らかだったのでコンピュータが空いてる間に BIT を写経したりする.

・F がすぐ書けるらしいので eto, nikutto がペアプロする.
・この辺で scoreboard 見たがいつの間にか randomized されていた. ワクワクしちゃうな.

139分

・F, AC.

142分

・A, AC.
・ここで nikutto が K を書き始めるもライブラリの LCA を写そうとしたところで誤って SCC のコードが書かれていたことに気付く.(???)
・B が解けそうな構築だったので eto と考える.

162分

・nikutto がその場で LCA を錬成して K, AC. ゴリラ.
・nikutto に N を伝えた後, B が gray code っぽくできるということになり eto と書き始める.

191分

・B, AC.
・N を nikutto が書き始める.
・問題ストックが無くなってきたのでこの間に eto と問題共有をする. C, E, L は不可能そう. G, J はまだ人間に解ける見た目をしているのでちょっと考えることにする.

240分ぐらい

・nikutto が N で WA.
・ここで順位表を見ると Cafe Mountain しか通してないことが分かる. (提出すろとペナで問題と順位表の対応関係が分かる) 他のチームも無限に WA を出していてヤバなので一旦諦めて I を書くことにする.

・I は nikutto によると遅延セグ木に(2次)多項式を載せるらしい. ペアプロを始める.
・実装方針の不一致により揉める.
・サンプルが一発で合ってしまったので提出. WA.
・この問題, 問題文には書かれていないが実は mod を取って出力する問題. どういうことやねん. eto も呼んでデバッグ.

282分

・I, AC.
・N を eto, nikutto のペアプロに切り替える.
・残り時間はほとんど無いが, 自分は G, J を考えることにする.

300分

・コンテスト終了. N は通らなかった.
・終了3秒後にオーバーフローが見つかる. 悲しい.

コンテスト後

・girigiri と同じ部屋だったので話を聞くと F のジャッジが壊れていたらしい. かわいそう.
・秒速で yes/no が進む. Cafe Mountain はずっと1位だった. やべ〜.

反省

・序盤に H を選んだのは仕方ないか? 考察自体は一番簡単だったらしい.
・B を通した後の動きが悪かった. I を先に書き切るか, N をペアプロすべきだった.

・サンプルをちゃんと読むようになった. 誤読が無かったのは進歩か. (???)

・とはいえ, 理想ムーブでも N に加えて G or J を通せたかというと微妙. 単純に弱いね.

感想

・上位に入るには10完が必須で, 参加者のレベルが高いコンテストだったように思う.
・運営は全てがガバガバのワクワクコンテストなのに問題がまともすぎてびっくりしてしまった.
・会場で常にガイド役の学生(日本語めっちゃ上手い)が付いてくれて助かった.
・ところで横浜まで2週間を切ってるらしい.

問題概要

多分問題が公開されていないので説明.

A

次のクエリに T (\le 100000) 回答えよ.
N (\le 10000) , M (\le 1e7) が与えられた時, N 以下の整数の積で表される M 以下の数の種類数.

B

N (\le 8), M (\le 8) と N + M 個の整数の集合 S が与えられる.
2^N * 2^M のグリッドで, 2^{(N+M)} - 1 以下の正整数を一つずつ含み, 隣接するグリッドに書かれた整数の XOR が必ず S に含まれているようなものを構築せよ.

C

N (\le 100000) 頂点の木があり, 各頂点に整数が書かれている. 頂点に書かれた値を 1 変更するにはコスト 1 がかかる.
隣接頂点の値の差の絶対値を K (\le 1e9) 以下にする最小コストを求めよ.
無理そう.

D

X (\le 100), K (\le 100) に対し, N^{16} \le X^K となる最大の N^{16} を答えよ. 存在しなければ "Impossible", 10^{100} を超えるなら "too big" を出力.

E

N (\le 8) * M (\le 8) のグリッド型迷路がある. 迷路に入る前に4方向の移動確率を定め, ゴールに必要な移動回数の期待値を最小化せよ.
無理.

F

読んでない

G

長さ N の 'T', 'H' からなる文字列がある.'H' の個数番目 (1-indexed) の文字を flip する, という操作を繰り返す.
全て 'T' にするのに必要な操作回数を答えよ.
難しい.

H

読んでない.

I

長さ N (\le 100000) の数列 A (初期値は全て 0) に対し以下のクエリを Q (\le 100000) 回投げる.
1. [L, R] の要素に対し順に 1^2, 2^2,..., (R-L+1)^2 を加える.
2. [L, R] の要素の和を答える.

J

数列 a\_n = n(n+1)/2, b\_n = n^2, c\_n = n(n+1) を考える.
a, b, c の内2つ以上に含まれる数の内, N (\le 1e18) 番目の数を答えよ
分からない.

K

N (\le 100000) 頂点の木がある. M (\le 100000) 回以下のクエリに答えよ.
パス XY, 頂点 P が与えられた時, パス中の頂点と P の距離の最小値.

L

半径 1 の球上に N 個の地点が存在する. 地点との距離の最大値が最小となるような, 球上の軌道を見つけてその時の最小値を答える.

M

N (\le 1e18), K (\le 75) に対し, \sum_{i=1}^N (2 * i)^K を求めよ.

N

1 を P (\le 30) 個, -1 を N (\le 30) 個 を含み, 1/1, 1/-1. -1/-1 が隣接しないような冗長2進数の内, M (\le 2^{60}) 以下で最大のものを出力せよ.

ICPC 2019 国内予選参加記

ICPC 参加記

はじめに

2019/07/12 に実施されたICPC国内予選に TigerSone で参加した.

チームメイトは etonagisa と nikutto です.

 

結果

A, B, C, D, E の5完で全体8位, 学内4位で予選通過.

 去年は(違うチームで)11位で予選敗退したので嬉しい.(㈱いい生活
今年こそ予選を通過してほしいで賞 じゃないんだよね)

 

コンテスト環境

・OSは Ubuntu, エディタは VSCode, 言語は C++ .

・nikutto とかいう人は emacs 使ってた.

f:id:zaki_joho:20190714013952p:plain


・会場は大学の計算機実験室で, プリンタは20チームで1台(???).  

 

コンテスト前日(当日?)

 13時大学集合にしていたが eto は 14時半ぐらいに来た. 想定内.

 nikutto は practice で 3WAしてた, 大丈夫か.

 

コンテスト内容

大体これです.

 

・序盤はA,B,Cあたりを並列で読むつもりだったが, とにかく問題文が印刷されてこないので全員でモニタを見ながら一問ずつ解いた.

・A: ファイルの用意とかテンプレートの写経とかしている間に eto が問題文を読む. AC(5:14).

・B: 例年のB問題に比べて実装が軽そう. nikutto が図だけ見てエスパーしてAC(11:31).

・C: nikutto が set マージするだけじゃんとか言ってた. AC(29:05).

・D: 難しそうなので nikutto と eto に考察投げる. この辺りで残りの問題が印刷され始めたので読む担当をしていた. 読み終わったあたりで dp が完成していた, すごい. AC(1:01:51)

・E: 2秒ぐらいマッチング(exact cover problem)を考えたが普通に全探索で解けそう. F を nikutto に投げつつ eto と解くことにする. 入出力/前処理を書いている間に eto が解法を詰めていた. ペアプロの結果30分ぐらいバグったがAC(2:33:32). この時点で8位.

・F: E が通ったあたりで nikutto が O(N^3) を思いついていたが実装は間に合わなかった.. 最後10分ぐらいは順位表見ながら nikutto に祈りを捧げていた.

・G, H: 予選全体で0AC, 何. 問題読んだ時点で捨てて良かった.

 

f:id:zaki_joho:20190714014324p:plain

E問題に埋め込まれたマジックナンバー群

 

感想

チームメイトが強すぎて問題読んで投げるぐらいしかすることが無い.

序盤に早解きしていたおかげでEがバグってもペナに余裕があった.

学内予選が厳しすぎるがとりあえず通ってよかった. アジアでは倒す.(suibakaのブログ)

アジア予選までにUS配列使えるようにします…

後院試くんね.

 

おまけ

これすき

www.youtube.com

AOJ 1620 論理式圧縮機

AOJ ICPC 競技プログラミング

問題文

Boolean Expression Compressor | Aizu Online Judge

解法

4変数に0/1を代入した時の評価結果は16bitで保持できる.
よって, 与えられたBNFから生成されうる文字列の内, 短いものから順に全て列挙していっても間に合う.
最短でない論理式から最短の論理式は生成され得ないのでそこの枝刈りは必要.

ソースコード

AIZU ONLINE JUDGE: Code Review

#include "bits/stdc++.h"

using namespace std;

// <expr> := 0 | 1 | a | b | c | d | -<expr> |  (<expr> ^ <expr>) | (<expr> * <expr>)
string s;
int pos;

// (a,b,c,d) を含まない <expr> に対する値を計算
bool expr()
{
    if (s[pos] == '0')
    {
        pos++;
        return 0;
    }
    if (s[pos] == '1')
    {
        pos++;
        return 1;
    }
    if (s[pos] == '-')
    {
        pos++;
        return !expr();
    }
    assert(s[pos] == '(');
    pos++; // (
    bool x = expr();
    assert(s[pos] == '^' || s[pos] == '*');
    bool f = (s[pos] == '^');
    pos++; // ^ or *
    bool y = expr();
    pos++; // )
    if (f)
        return x ^ y;
    else
        return x & y;
}

// str を 16bit 整数に変換
int calc(const string &str)
{
    vector<vector<int>> ps(4); // a,b,c,d
    int n = str.size();
    for (int i = 0; i < n; i++)
    {
        if (str[i] == 'a')
            ps[0].push_back(i);
        else if (str[i] == 'b')
            ps[1].push_back(i);
        else if (str[i] == 'c')
            ps[2].push_back(i);
        else if (str[i] == 'd')
            ps[3].push_back(i);
    }
    int mask = 0;
    for (int i = 0; i < 16; i++)
    {
        pos = 0;
        s = str;
        for (int j = 0; j < 4; j++)
        {
            // "abcd"[j] は (i>>j)&1 にする
            char c = '0' + ((i >> j) & 1);
            for (auto index : ps[j])
            {
                s[index] = c;
            }
        }
        if (expr())
            mask |= (1 << i);
    }
    return mask;
}

// 整数値->最短論理式長
map<int, int> ret;

// ret を構築
void construct()
{
    set<string> ex = {"0", "1", "a", "b", "c", "d"};
    for (auto str : ex)
    {
        int val = calc(str);
        // cout << val << endl;
        ret[val] = 1;
    }
    // i 文字の論理式を作る
    for (int i = 2; i <= 16; i++)
    {
        set<string> tmp;
        for (const auto &ss : ex)
        {
            string ns = "-" + ss;
            if ((int)ns.size() == i)
            {
                int val = calc(ns);
                if (ret.find(val) == ret.end())
                {
                    ret[val] = i;
                    tmp.insert(ns);
                }
            }
            for (const auto &tt : ex)
            {
                ns = "(" + ss + "^" + tt + ")";
                if ((int)ns.size() == i)
                {
                    int val = calc(ns);
                    if (ret.find(val) == ret.end())
                    {
                        ret[val] = i;
                        tmp.insert(ns);
                    }
                }
                ns = "(" + ss + "*" + tt + ")";
                if ((int)ns.size() == i)
                {
                    int val = calc(ns);
                    if (ret.find(val) == ret.end())
                    {
                        ret[val] = i;
                        tmp.insert(ns);
                    }
                }
            }
        }
        // cerr << i << endl;
        for (const auto &str : tmp)
        {
            // cout << str << endl;
            ex.insert(str);
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    construct();
    string str;
    while (cin >> str, str != ".")
    {
        cout << ret[calc(str)] << endl;
    }
}

感想

書いてて楽しかった.
手元で10秒弱かかってTLE覚悟で投げたら0.94sで通った. ジャッジ速すぎ.

AOJ 2643 AI

AOJ ICPC 競技プログラミング

問題文

ロボットのいる盤面と, 以下のEBNF(Extended BNF) で表されるプログラムが与えられる.
ロボットがこのプログラムに従って動作する時, ゴールまでのステップ数を出力せよ(到達不可能ならば-1). (プログラムの詳細, 注意事項は元の問題文参照)

プログラム:= {文};
文:= if 文|while 文|動作文;
if 文:= "[", 条件, プログラム, "]";
while 文:= "{", 条件, プログラム, "}";

動作文:= "^"|"v"|"<"|">";
条件:= ["~"], "N"|"E"|"S"|"W"|"C"|"T";

AI | Aizu Online Judge

解法

ひたすらパーサーを書く.
無限ループを検出するには while文開始時に現在と同じ (位置, 向き, 命令のインデックス) を経由したことがあるかを確認すればよい.
while文, if文で cond が False だったときはその statement の終了位置まで読み進める必要があるが, これは括弧の対応関係を見れば終端が分かる.

ソースコード

AIZU ONLINE JUDGE: Code Review

長いので省略.

感想

終了or無限ループ判定は例外を使うべきだった気がする.
構文解析でバグった時はどうすればいいんですかね…

AOJ 2740 みさわさんの根付き木

AOJ ICPC 競技プログラミング

問題文

2つの根付き木A,Bが文字列で与えられる.(|A|, |B| <= 1000)
根付き木の各ノードは値と左右の子(or nullptr)を持つ.
二分木を合成してできる二分木を入力と同じ形式にして出力せよ.

みさわさんの根付き木 | Aizu Online Judge

解法

構文解析. 書き始める前に以下のページを読んだ.
構文解析 Howto · GitHub

BNF っぽく書くと
tree := "" | '(' tree ')' '[' number ']' '(' tree ')'
number := ﾃｷﾄｳ
になるのでパーサーを書く.

自分は二分木データ構造を作ってから A, B を各々二分木にし,愚直に合成してから文字列に戻す, という解き方をした.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3655784

#include "bits/stdc++.h"

using namespace std;

// パースする文字列
string s;
// 次に読み始める位置
int pos;

// 二分木ノード
struct Node
{
    int val;
    Node *l, *r;
};

// tr := (tr)[num](tr)

// 整数
int number()
{
    int ret = 0;
    while (isdigit(s[pos]))
    {
        ret *= 10;
        ret += s[pos] - '0';
        pos++;
    }
    return ret;
}

// パースして二分木のノードを返す
Node *misawa()
{
    if (s[pos] == ')')
    {
        // 空ノード
        return nullptr;
    }
    pos++;             // (
    auto l = misawa(); // left child
    pos++;             // )
    pos++;             // [
    auto v = number();
    pos++;             // ]
    pos++;             // (
    auto r = misawa(); // right child
    pos++;             // )
    Node *node = new Node;
    node->val = v;
    node->l = l;
    node->r = r;
    return node;
}

// 二分木a, b を合成
Node *rec(Node *a, Node *b)
{
    Node *ret = new Node;
    ret->val = a->val + b->val;
    ret->l = nullptr;
    ret->r = nullptr;
    if (a->l && b->l)
    {
        ret->l = rec(a->l, b->l);
    }
    if (a->r && b->r)
    {
        ret->r = rec(a->r, b->r);
    }
    return ret;
}

// 二分木を文字列に変換
string recstr(Node *node)
{
    if (node == nullptr)
        return "";
    string ret = "";
    ret += "(" + recstr(node->l) + ")";
    ret += "[" + to_string(node->val) + "]";
    ret += "(" + recstr(node->r) + ")";
    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string a, b;
    cin >> a >> b;
    s = a;
    pos = 0;
    auto at = misawa();
    s = b;
    pos = 0;
    auto bt = misawa();
    auto ret = rec(at, bt);
    cout << recstr(ret) << endl;
}

感想

パーサーより二分木がバグりそう