ICPC 2019 Asia Bangkok Regional 参加記(コンテスト)
はじめに
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
次のクエリに 回答えよ.
が与えられた時,
以下の整数の積で表される
以下の数の種類数.
B
と
個の整数の集合
が与えられる.
のグリッドで,
以下の正整数を一つずつ含み, 隣接するグリッドに書かれた整数の XOR が必ず
に含まれているようなものを構築せよ.
C
頂点の木があり, 各頂点に整数が書かれている. 頂点に書かれた値を
変更するにはコスト
がかかる.
隣接頂点の値の差の絶対値を 以下にする最小コストを求めよ.
無理そう.
D
に対し,
となる最大の
を答えよ. 存在しなければ "Impossible",
を超えるなら "too big" を出力.
E
のグリッド型迷路がある. 迷路に入る前に4方向の移動確率を定め, ゴールに必要な移動回数の期待値を最小化せよ.
無理.
F
読んでない
G
長さ の 'T', 'H' からなる文字列がある.'H' の個数番目 (1-indexed) の文字を flip する, という操作を繰り返す.
全て 'T' にするのに必要な操作回数を答えよ.
難しい.
H
読んでない.
I
長さ の数列
(初期値は全て
) に対し以下のクエリを
回投げる.
1. の要素に対し順に
を加える.
2. の要素の和を答える.
J
数列 を考える.
の内2つ以上に含まれる数の内,
番目の数を答えよ
分からない.
K
頂点の木がある.
回以下のクエリに答えよ.
パス , 頂点
が与えられた時, パス中の頂点と
の距離の最小値.
L
半径 1 の球上に 個の地点が存在する. 地点との距離の最大値が最小となるような, 球上の軌道を見つけてその時の最小値を答える.
M
に対し,
を求めよ.
N
を
個,
を
個 を含み,
が隣接しないような冗長2進数の内,
以下で最大のものを出力せよ.
京都大学情報学研究科通信情報システム専攻に合格しました
2020年度 4月期入学京都大学情報学研究科通信情報システム専攻に合格しました。
気が付いたら合格発表から1ヵ月経っていたんですが院試までにやったこととポエムを書きます。
出題範囲・配点
募集要項｜入試情報｜京都大学大学院情報学研究科 にも書いていることですが、
専門基礎A(400点)、専門基礎B(400点), TOEIC/TOEFL(200点) の1000点満点です。
今年の専門基礎Aは9題から4題、専門基礎Bは8題から4題選択。とはいえ各々半分は(工学部)電気電子工学科の学生向けなので選択肢はほぼありません。
専門基礎では昨年度までと比べ、データベース ・人工知能が出題範囲から削除され、グラフ理論・計算と論理が追加されました。
面接などは無く、筆記試験のみで合否が決定されます。
結果
第一志望のコンピュータアルゴリズム分野に合格しました。
成績開示の結果は 専門基礎A: 376, 専門基礎B: 316, 英語: 171 でした。
試験直後に同期と話して予想していた点数通り。専門基礎Bの記述で少し減点されてそう。
英語(TOEIC)
3年の夏に受けたTOEIC(830点)をそのまま提出してしまった。
合格したほとんどの同期は850点前後を取っていたので何回か受け直しておけばよかった気がしている。
専門基礎A
最初から数学は捨てていて、情報理論・データ構造とアルゴリズム・計算機アーキテクチャ・プログラミング言語・グラフ理論から4題を解くつもりで勉強していた。
試験ではプログラミング言語に不可能が出たのでその他の4題を選択。グラフ理論の最後の記述以外の書いたところは合ってたっぽい。
こっちはグラフ理論以外は過去問オーバーフィッティングで対応できた。グラフ理論は競プロやってたら何とかなる問題だった。
専門基礎B
論理回路・計算機システム・オートマトンとアルゴリズム論・コンパイラとOS・計算と論理から4題を解くつもりで勉強したいた。
試験では計算と論理が完全に不可能だったのでそれ以外の4題を選んだが、昨年度までと傾向が大きく変わっていて困った。
計算機システムのキャッシュの問題、オートマトンの記述問題、OSの語句説明辺りで点を引かれていそう。
時系列
～5月上旬
研究室に配属されたり競プロしたりアトリエシリーズやったりしてた。
授業資料とか過去問を集めるなどしていた。
5月下旬
えものすけ (@emo_nosuke) と情報理論の過去問を解いたり Md (@Md19970824) と論理回路とか計算機アーキテクチャの過去問を解いていたりしていた。感謝。
6月
etonagisa や Suibaka も召喚して論理回路とかオートマトンの過去問を解いていた。感謝。
7月上旬
ICPCに出た(ICPC 2019 国内予選参加記 - Z-diary)。
計算と論理・コンパイラ・プログラミング言語の授業資料はこの辺で読んでたかな？
7月下旬
京都が暑すぎて勉強している場合ではない。
予想問題を作って解いたりしていた。一つも当たらなかったけど。(ヒープ出ると思ってたんだけどなあ)
試験2日前(08/03)
ヤマト運輸プログラミングコンテスト2019が始まったので参加！ｗ
最終的に特別賞を貰えたのでOKです。表彰式楽しかった。
試験1日目(08/05)
13時からなので余裕です。
この夜は Md の家に泊まります。
試験2日目(08/06)
試験は9時開始です。意味が分からん。
VTuber
勉強中ずっと流してた。ライブ良かった…
最後に
一緒に勉強した友人は皆第一志望に受かっていたのでめでたい。彼らがいなかったら院試勉強詰んでたと思うので感謝しかない。
ICPC 2019 国内予選参加記
はじめに
2019/07/12 に実施されたICPC国内予選に TigerSone で参加した.
チームメイトは etonagisa と nikutto です.
結果
A, B, C, D, E の5完で全体8位, 学内4位で予選通過.
去年は(違うチームで)11位で予選敗退したので嬉しい.(㈱いい生活
今年こそ予選を通過してほしいで賞 じゃないんだよね)
コンテスト環境
・OSは Ubuntu, エディタは VSCode, 言語は C++ .
・nikutto とかいう人は emacs 使ってた.
・会場は大学の計算機実験室で, プリンタは20チームで1台(???).
コンテスト前日(当日?)
icpcの準備バッチリ pic.twitter.com/jidWHSdGXl
— ざき🍆30日 (@zaki_joho) July 11, 2019
13時大学集合にしていたが eto は 14時半ぐらいに来た. 想定内.
nikutto は practice で 3WAしてた, 大丈夫か.
コンテスト内容
大体これです.
A: 気が付いたら解かれてた, Bが印刷されていないのでやることがない
— ざき🍆30日 (@zaki_joho) July 12, 2019
B: 気が付いたら解かれてた, Cが印刷されていないのでやることがない
C: 気が付いたら解かれてた, Dが印刷されていないのでやることがない
D: nikutto に投げた
E: なぎさが実装してるの見てた
F: nikutto に投げた
・序盤は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, 何. 問題読んだ時点で捨てて良かった.
感想
チームメイトが強すぎて問題読んで投げるぐらいしかすることが無い.
序盤に早解きしていたおかげでEがバグってもペナに余裕があった.
学内予選が厳しすぎるがとりあえず通ってよかった. アジアでは倒す.(suibakaのブログ)
アジア予選までにUS配列使えるようにします…
後院試くんね.
おまけ
これすき
AOJ 1620 論理式圧縮機
解法
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
問題文
ロボットのいる盤面と, 以下のEBNF(Extended BNF) で表されるプログラムが与えられる.
ロボットがこのプログラムに従って動作する時, ゴールまでのステップ数を出力せよ(到達不可能ならば-1). (プログラムの詳細, 注意事項は元の問題文参照)
プログラム:= {文};
文:= if 文|while 文|動作文;
if 文:= "[", 条件, プログラム, "]";
while 文:= "{", 条件, プログラム, "}";
動作文:= "^"|"v"|"<"|">";
条件:= ["~"], "N"|"E"|"S"|"W"|"C"|"T";
解法
ひたすらパーサーを書く.
無限ループを検出するには while文開始時に現在と同じ (位置, 向き, 命令のインデックス) を経由したことがあるかを確認すればよい.
while文, if文で cond が False だったときはその statement の終了位置まで読み進める必要があるが, これは括弧の対応関係を見れば終端が分かる.
感想
終了or無限ループ判定は例外を使うべきだった気がする.
構文解析でバグった時はどうすればいいんですかね…
AOJ 2740 みさわさんの根付き木
問題文
2つの根付き木A,Bが文字列で与えられる.(|A|, |B| <= 1000)
根付き木の各ノードは値と左右の子(or nullptr)を持つ.
二分木を合成してできる二分木を入力と同じ形式にして出力せよ.
解法
構文解析. 書き始める前に以下のページを読んだ.
構文解析 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; }
感想
パーサーより二分木がバグりそう
AOJ 2236 Rabbit Plays Games!
問題概要
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2236
主人公とn人の敵がいる. 各々HP, ATK, DEF, SPD のステータスを持つ.
ターン制で先頭を行い, 各ターンではSPDの高い順に攻撃を行う.
キャラi(主人公/敵) がキャラj に攻撃する時, 相手のHPをmin(0, ATK_i - DEF_j)減少させる.
各ターンで主人公が攻撃する相手を適切に定め, その時主人公の受けるダメージの最小値を出力せよ. (主人公のHPを超える時は-1)
1<=n<=40000, 1<=h, a, d, s<=1,000,000,000 (s は distinct)
解法
どの順番で敵を倒すか考える.
敵i を倒すのに必要なターン数 turn[i], 1ターンでその敵から受けるダメージを dmg[i] とする.
敵i, j のどちらを先に倒すべきかだが, i を先に倒す場合は turn[i] * dmg[j], j を先に倒す場合には turn[j] * dmg[i] だけ受けるダメージが増えることを考えると turn[i]/dmg[i] が小さい順に倒せば良いことが分かる. (すぐ倒せ, 受けるダメージが大きい方を先に倒すと嬉しそう)
JAG の解説スライドに書かれていない本質があって,
1. 主人公にダメージを与えられない敵は無視(一番最後に回す)
2. 主人公がダメージを与えられない敵(1. を満たす場合は除外)がいる場合は-1
3. 戦闘が終了しないようなテストケースが含まれている.(1WA, 主人公も敵もダメージを与えられない場合) 問題文をよく読むとどう出力すべきかは分かるが…
主人公のHPが無くなったらすぐreturnしないと実装によってはアンダーフローするかも.
ソースコード
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3619635#1
#include "bits/stdc++.h" using namespace std; using ll = long long; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; ll hp, atk, def, spd; cin >> hp >> atk >> def >> spd; vector<ll> h, a, d, s; for (int i = 0; i < n; i++) { ll htmp, atmp, dtmp, stmp; cin >> htmp >> atmp >> dtmp >> stmp; if (dtmp >= atk && atmp > def) { cout << -1 << endl; return 0; } if (atmp <= def) continue; atmp -= def; h.push_back(htmp); a.push_back(atmp); d.push_back(dtmp); s.push_back(stmp); } n = h.size(); vector<ll> turn(n); for (int i = 0; i < n; i++) { ll tmp = atk - d[i]; turn[i] = (h[i] - 1) / tmp + 1; } vector<int> idx(n); for (int i = 0; i < n; i++) idx[i] = i; sort(idx.begin(), idx.end(), [&](int i, int j) { return turn[i] * a[j] < turn[j] * a[i]; }); ll ret = 0, cnt = 0; for (auto i : idx) { hp -= cnt * a[i]; ret += cnt * a[i]; cnt += turn[i]; if (s[i] <= spd) turn[i]--; hp -= turn[i] * a[i]; ret += turn[i] * a[i]; if (hp <= 0) { cout << -1 << endl; return 0; } } cout << ret << endl; }
感想
問題文のラスト1文を太字にして
