こんばんのしのし〜〜
20B の tatyam です。
参加記を、書きましょう (twitter の短文に乗らない細かい情報がたくさん入って運営が助かるので)
3 人分の情報がある ICPC 参加記は早く書かないと書けなくなるので、今日中に書きます。(えらい)
potato167 + noshi91 + tatyam = tonosama で参加しました。
今東工大で一番強い 3 人です。
potato と tatyam は教室を借りて、noshi は家の PC の環境が良いので家からの参加になりました。
Discord で通話を繋いでいます。
戦略
初手
A : potato
B : tatyam
C : noshi
が担当し、後は解けそうな問題から解きます。
A
potato が 2:49 で解きます。
B
親切にも 同じプレイヤーが 2 回手札を引かれる間に，少なくとも 1 対のカードが捨てられるので，遅かれ早かれゲームは終わる． と書いてあるので、問題文の通りに丁寧に実装すれば であることがわかります。手番を回すのには deque を使うと良いです。
手札を追加した後ソートを忘れたり、カードの移動する向きを読み間違えたりして 5 分以上ロスがあります。反省点です。
15:53 で解きました。
C
私が B に時間をかけている間に noshi が 11:59 で解きます。
D
potato は D を読みますが、難しそうなので E を読みます。
noshi が D を考えて、解いてしまいました。
1 度 3 乗だったと戻ってきましたが、2 乗に書き直して、AC です。42:35 で解きました。
E
D が解かれている間に、私は F を読んで考えます。わかりません。G も読んで考えます。わかりません。H を potato が読んでいるので E を考えます。
グリッドに括弧を書き込んで、指定された行と列だけが対応の取れた括弧列(1)となるようにする問題です。
割となんでも 0 になるので、1 はきつい条件です。+ で始まり - で終わらないと 1 にならないので、外周の 4 辺に 1 があるとかなり難しいです。まずは 4 辺が 0 として、緩い条件でなにかできないか探します。
4 辺以外全部 1 の場合は、4 辺は全部 + か全部 - で固定され、内部を市松模様にすれば :ok:。0 の列があっても外周を変えれば良いです。
4 辺のうち 3 辺が 1 であると不可能です。あとは場合分けして構成しましょう。
左 (4 辺のうち 1 辺) が 1 の場合は、左は上から貪欲に 1 の行に + 、0 の行に (置けるなら) - を置くと良くて、0 の行に + を置いた場合は右を + にして対応できます。
(ここらへんで D を AC)
左と右 (向かい合う 2 辺) が 1 の場合は、1 の行には +- を置く必要があって、0 の行には、上の方に ++ を、下の方に -- を、中央の方に +- と同じ数の -+ を置くとできそうです。
左と上 (向かい合わない 2 辺) が 1 の場合は、左と右を 1 辺のときと同様にやって…、これ左右と上下独立にできますね。
ここで解けた宣言をして、実装に入ります。
場合分けが多い実装問なので、場合分けをまとめたり、関数に切り分けたりとうまく実装したいです。デバッグも大変なので、丁寧に実装します。assert もたくさん書きます。
まず場合分けをまとめられるように 90 度回転を書きます。(90 度回転だと縦・横の片方だけ符号反転してしまうので、実装すべきは対角線を軸とした反転です。)
出力関数を書きます。ここで回転の解消と出力の validate をします。
0 辺の場合を書きます。
1 辺の場合を書きます。2 辺で使えるように関数化しておきます。
向かい合わない 2 辺の場合を書きます。
回転がダメなことに気づいて、反転を片方書きます。
左は 1 の行だけ気にして、0 の行は右に任せていいことに気が付きます。
(ここらへんで H を AC)
向かい合う 2 辺の場合を書きます。
左と右で独立に 1 辺のときと同じ貪欲をすると、0 の行が 1 になってしまうことが……ない！！
実装ができて実行すると、出力が条件を満たしていないケースがあります。あってよかった validation
1 行直すと、無事 AC です。1:47:50 で解きました。時間はかかりましたが、まあまあ上手くできたと思います。
実装コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> void chmin(T& a, T b){ if(a > b) a = b; }
template<class T> void chmax(T& a, T b){ if(a < b) a = b; }
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
while(1){
ll H, W;
cin >> H >> W;
if(H == 0) return 0;
string R, C;
cin >> R >> C;
for(char& c : R) c -= '0';
for(char& c : C) c -= '0';
vector ans(H, string(W, '+'));
for(ll i = 1; i < H - 1; i++) for(ll j = 1; j < W - 1; j++) if((i ^ j) & 1) ans[i][j] = '-';
for(ll i = 0; i < H; i++) ans[i].back() = '-';
for(ll j = 0; j < W; j++) ans.back()[j] = '-';
const ll cnt = R.front() + R.back() + C.front() + C.back();
bool yes = 0, rev = 0;
auto Reverse = [&]{
rev ^= 1;
reverse(R.begin(), R.end());
reverse(C.begin(), C.end());
reverse(ans.begin(), ans.end());
for(auto& s : ans) reverse(s.begin(), s.end());
for(auto& s : ans) for(char& c : s) c ^= '+' ^ '-';
};
auto Yes = [&]{
if(rev) Reverse();
yes = 1;
cout << "Yes" << endl;
for(auto& s : ans) cout << s << endl;
for(ll i = 0; i < H; i++) assert(R[i] == [&]{
ll san = 0;
for(ll j = 0; j < W; j++){
if(ans[i][j] == '+') san++;
else if(--san < 0) return false;
}
return san == 0;
}());
for(ll j = 0; j < W; j++) assert(C[j] == [&]{
ll san = 0;
for(ll i = 0; i < H; i++){
if(ans[i][j] == '+') san++;
else if(--san < 0) return false;
}
return san == 0;
}());
};
auto up = [&]{
assert(R[0]);
ll san = 0;
for(ll j = 0; j < W; j++){
if(C[j] || san == 0){
ans.front()[j] = '+';
san++;
}
else{
ans.front()[j] = '-';
san--;
}
}
return san == 0;
};
auto left = [&]{
assert(C[0]);
ll san = 0;
for(ll i = 0; i < H; i++){
if(R[i] || san == 0){
ans[i].front() = '+';
san++;
}
else{
ans[i].front() = '-';
san--;
}
}
return san == 0;
};
auto down = [&]{
assert(R.back());
ll san = 0;
for(ll j = W; j--; ){
if(C[j] || san == 0){
ans.back()[j] = '-';
san++;
}
else{
ans.back()[j] = '+';
san--;
}
}
return san == 0;
};
auto right = [&]{
assert(C.back());
ll san = 0;
for(ll i = H; i--; ){
if(R[i] || san == 0){
ans[i].back() = '-';
san++;
}
else{
ans[i].back() = '+';
san--;
}
}
return san == 0;
};
auto upleft = [&]{
if(!up() || !left()) return;
for(ll i = 0; i < H; i++) if(!R[i]) ans[i].back() = '+';
for(ll j = 0; j < W; j++) if(!C[j]) ans.back()[j] = '+';
Yes();
};
auto downleft = [&]{
if(!down() || !left()) return;
for(ll i = 0; i < H; i++) if(!R[i]) ans[i].back() = '+';
for(ll j = 0; j < W; j++) if(!C[j]) ans.front()[j] = '-';
Yes();
};
auto updown = [&]{
if(!up() || !down()) return;
for(ll i = 0; i < H; i++) if(!R[i]) ans[i].back() = '+';
Yes();
};
auto leftright = [&]{
if(!left() || !right()) return;
for(ll j = 0; j < W; j++) if(!C[j]) ans.back()[j] = '+';
Yes();
};
if(cnt == 0){
for(ll i = 0; i < H; i++) if(!R[i]) ans[i].back() = '+';
for(ll j = 0; j < W; j++) if(!C[j]) ans.back()[j] = '+';
Yes();
}
else if(cnt == 1){
if(R.back() || C.back()) Reverse();
if(R[0] && up() || C[0] && left()){
for(ll i = 0; i < H; i++) if(!R[i]) ans[i].back() = '+';
for(ll j = 0; j < W; j++) if(!C[j]) ans.back()[j] = '+';
Yes();
}
}
else if(cnt == 2){
if(C.back()) Reverse();
if(R.front() && C.front()) upleft();
else if(R.back() && C.front()) downleft();
else if(R.front() && R.back()) updown();
else leftright();
}
if(!yes) cout << "No" << endl;
}
}
H
これも noshi です。
(tatyam E 実装中)
noshi 「F は (なんやかんや) して木 DP で解けそう」
…
noshi 「potato が F 実装できそうなら H 書くんですけど」
…
noshi 「H 通りました」
1:29:36 で H の FA です。天才？
F
E, H が解けたので potato の様子を見ると、デバッグで苦戦しています。どうやら範囲外アクセスをしているようです。
コードをもらって XCode で動かします。XCode なら RE が起こったところでデバッガが開くんですが… コンパイラの違いでエラーが起こりませんでした。
こんなときは VSCode で動かします。vector::operator[] は #define _GLIBCXX_DEBUG をしておくと例外を投げるようになるので、例外を VSCode のデバッグで catch すると、どこで範囲外アクセスしたかが分かります。
(競プロer ならこの程度のデバッグ環境は備えるべきです (強い主張))
直して提出すると WA
勘違いがあったようで書き直します。
G
tatyam と noshi で G を考えます。
noshi「もうこれしかないと思うんだよね」
折れ線上の位置を引き伸ばして 2 次元グリッドにし、点 と点 を連結にすることを考える。
最大値の最小化なので二分探索。答えを決め打つと、各マスに移動可能な領域が定まる。
その形は楕円である。
楕円とマスの辺の重なり方を見て隣り合うマスと連結であるかチェックし、マス からマス まで DFS
noshi「二分探索しない方がうまくいくか？」
私も解法を理解しました。 :
折れ線上の位置を引き伸ばして 2 次元グリッドにすると、各マスの内部でコストは下に凸である。
コストが各マスで下に凸であるから、
- 地点 から地点 に移動するとき、地点 の属するマスで最もコストの低いところを経由するとして良い
- あるマス (の底) から辺をまたいで隣のマス (の底) に移動するとき、辺上の最もコストの低いところで最大値を取る
これより、あるマスから隣のマスに移動するときのコストは、間にある辺上でのコストの最小値 = 点と線分の距離 で求まる。
あとは min-max 半環で Dijkstra 法をすれば良い。
E はデバッグが進行していたので tatyam と noshi で同時に実装しました。
Luzhiled's Library をお借りすることにして、2 人が実装したので、double で 20 桁出力と合意を取って diff を取りました。
私が最初と最後の距離を忘れていて合わず、直すと完全一致。
2:27:09 で AC です。
単独 7 完で 1 位！がんばれ potato！
F
私は解法が分かっていないので、noshi が新しく実装、potato がデバッグ、tatyam がサポートを担当します。
2 回目の提出も WA 。あと 20 分くらい
noshi「いや〜間に合わないなこれ」
ソースコードを確認していると、potato が変なところを発見しました。
2 回目の提出のときに _GLIBCXX_DEBUG をしていて心配なので私が代理実行します。
(-Ofast -march=native -mtune=native とかつけておきましょう)
… (実行 2 ~ 3 分)
Correct answer.
… (実行 2 ~ 3 分)
Congratulations!
2:55:06 + 2 ペナルティ で AC です 🎉🎉
解法は、?() を親、?() に含まれる各要素を子とした根付き木を作り、各頂点について、左から 文字、右から 文字消す場合の辞書順最小を木 DP で求める 4 乗のものです。
文字列長 1000 といっても、?() に 3 文字使うので、3 分くらいに収まります。
結果
単独全完で優勝です！！
全完優勝すると……うれしい！ やった〜〜
ところで noshi さんは CDFGH の考察と CDGH の実装をしていませんか？
今年のアジア大会はちゃんと寝て、良いパフォーマンスを出して、今年こそ World Final にいきましょう…… 🙏
