ICPC 国内予選 2022 参加記
oraCle_MaChine(carrot46, cuthbert, Motsu_xe)で参加, 結果は全体3位!!!予選突破いたしました!
チームについて
以前書いた記事
motsu-xe.hatenablog.com
をご覧ください。
コンテスト前
我が家に集まって雑談したり, お菓子を食べながら作戦会議をしていました。
まず目標については, アジア出場権の獲得で, 今年は東大のチームでアジア狙えるチームが多すぎだったので, 東大3位は全く意識せず, 全体10位を見据えることにはなるかな〜と言っていました*1。
自分は最近競プロから離れてしまっており, コンテストに出ること自体がかなり久々で, 早解きとかできる気がしなかったので, Aをcarrot46, Bをcuthbertが解いて, 自分はC以降を眺めて, 問題概要とか誰が解けそうかを把握しておく係をすることに決めました。
コンテスト中
(問題の考察というよりは, 会話中心に書きます)
コンテスト開始がいっつも遅れがちなので、今回普通に定時に始まってびっくりしました。
A
carrot46が割とサクッと通してくれました。
C
carrot46がAを解いている間に, Motsu_xeが読んでいて, 問題概要をcarrot46に伝えて, 練習は固めたほうがよくて, 休憩は満遍なくばらしたほうがいいよねぇってことだけ考えたわよってcarrot46に伝えたら, ほな塊の数全探索したら終わりやんって言ってきて, それはそうだなぁってなりました。実装はcarrot46に投げました。ちょっとバグらせてたけど, しばらくしたら通してくれました。
B
cuthbertがバグかなんかで苦しんでいたが, ヘルプいる?って聞いたら, いやなんとかなるって言ってたので, 任せたら*2しばらくしたら通してくれました。
D, E, F
2人がB, Cを解いてる間に, Motsu_xeがD, E, Fを読んでおいて, 軽く考えたりしていました。D, Fは丁寧にやればまあできそう(え?)みたいな気持ちにはなってましたが, Eはできる気しないなぁみたいなことを言ってたら, 2人が合流しました。Eはなんか見た目フローっぽいみたいなこと言ってたけど, フローに落とせそうもないから違うかぁとなったりしてる間に, cuthbertがDはやればできそうだからやるわ〜とか言ってたので, Dは任せました(その後のことは知らないんですが, 1人で勝手に通してました, 偉すぎ)。 Eをcarrot46とMotsu_xeで相談(cuthbertもちょいちょい口挟んでくれた)していて, なんやかんや思いついたので, Motsu_xeが実装始めて, carrot46はFを見ることになりました。が, 直後Fを見たcarrot46が, 前何文字か削った時の一番若いやつ持つとかでできそう?みたいな発想を投げてきたので, Motsu_xeがそれ詰めて実装するわ〜みたいになって, 結局Eの実装はcarrot46に投げて, Fは自分がその後詰めて通しました。この時点で5完9位でしたが, ペナが重く, 5完が増えたら抜かれる(実際すぐ11位とかになった)なとなり, 6完すれば割と通りそうなので, Eを通せれば!って感じになっていました。Eはcarrot46がバグり散らかしてて大変そうで, 私もサポートに入ったりしました。
G
さらっとDを終わらせたcuthbertが次何やる?と聞いてきたので, 2人はE, F解いてたので, Gは幾何だから見てみて*3, と言って, 一応Motsu_xeは問題読んではいたので, 問題概要説明して, ちょっと議論してたら, なんか行けそうとか言ってたから, 任せて放っていたら, なんかヌルッと通してきて, ビビり散らかしていました。
は?
— こるとん (@kyort0n) 2022年7月8日
↑割とチームメンバーもこんな反応でした。
E(再)
この時点で割と10位以内は行けそうでしたが, ペナが結構終わってるので6完増えるとワンチャンやばいという状態で, 3人でEのバグとりをしようとしていました。2人は基本的にはcarrot46の主張の正誤判断とか, 独立したコードブロックのバグチェックとかをしていました。もはやEは通ればペナはどうでもいいので, 悩む前に提出みたいなことをしており, 最終的にミスにcarrot46が気付き, 残り16秒でブザービートを決めて, みんなで騒いでいました。マジでアツかった。
H
みてない。
コンテスト後
通ったああああって言ってたら順位表見たら3位!?!?!?!?!?!?ってなって騒ぎ散らかしており, 大変なことに。絶対勝てないだろって思ってたチームが3チーム以上あったので, 3位は完全に想定外でしばらく実感が湧きませんでした。
そのあとはツイートしたり, 雑談したりして, 夕食兼祝勝会みたいな感じで, たまたま買ってたシャンパン*4で祝杯を上げました。
感想
去年に続いて, 国内予選突破!!でもそれより強豪を上回っての3位が嬉しすぎます。これもひとえにチームメイトのおかげです, ほんとに。まあ下っ端なりに最低限の働きは出来たと思いますが, 折角アジアまた出れる, しかも初のオンサイトの予定ですし, 競プロも復帰して頑張ろうという気持ちになりました。アジア出場の皆さんはよろしくお願いします!
あと, なんか弊学から6チーム出場とかいうバグが発生していて流石に笑っています。
とりあえず楽しかったです!お疲れ様でした〜!
ICPC 国内予選 2021 参加記
oraCle_MaChine(carrot46, cuthbert, Motsu_xe)で参加, 結果は全体9位で予選突破いたしました!
チームについて
本ブログでoraCle_MaChineについて語ったことがなかったので, 軽く語りたいと思います。
弊チームはPGBattle 2019の際, 私が2人を呼んで結成(当時のチーム名は46beosux*1 )したチームでした。一応PGBattle用のチーム, 後々ICPCも出れればいいなぁと思って招集したチームではありました。結成時のレートは黄1青2のチームでした。
そして去年のICPCの国内予選にも同メンバーで出場, この際チーム名をoraCle_MaChineに改名*2しました。結果は予選敗退, 確かペナ差10分程度での惜敗だった記憶があります。
その他有志コンなど様々な大会に同チームで出場しましたが, まあ今まで結果という結果は残せてきていませんでした。
ICPC 国内予選
閑話休題。勝てたらいいね〜見たいなノリだったんですが, チームレート表みたいの見たら, 普通に上位10位に入ってて, これ勝てたらいいねじゃなくて, 普通に勝つべきなのでは?となって震えてました(震えてない)。黄1青2で結成したチームがいつの間にか橙3人になっててびっくりしちゃったねぇ。
開始前の作戦としては, carrot46がA, Motsu_xeがBをさっさと解いて, cuthbertがC以降を眺めて解けそうなやつから解くみたいなことだけ決めていました。
去年は最初全然始まらず, 電凸とかしたなぁ, 今年も始まらなかったらウケるなぁwと言いつつ16:30になると, サイトが重すぎて, これは…wとなっていた。結果的には去年よりはマシで, 1, 2分でなんとか開始。
carrot46にサクッとAを通していただき*3, 自分はBの問題文の理解に苦しみつつ, ちょっと遅れて通す。cuthbertがCで苦戦してて大変そうと思いつつ, carrotと2人でDをみて, carrotがなんか出来そうだったからcarrotに任せて自分はEへ。Eで最短経路なのにmodなのかとか言ってたが, タクシーは高々50回くらいしか使わんから, 頂点100倍化Dijkstraで常勝!w(←嘘)とか言って提出。1WA出してそんなバカなと言って, carrotに見せたらmodなんだ〜とか言ってきて, mod取り忘れた〜〜〜〜(←馬鹿)とか言って再提出、2WA。交互のパターンとかだとやばいやんけ(最初に考察してたのに忘れてた)ってcarrotに言われて, まじやんけ〜つって実装追加してなんやかんやあってAC。
とか言ってる途中にcarrotは結構前にDを通してくれてたので, ABDE4完。cuthbertが大変そうだけど, 時間かければ絶対できると言ってたので, 信じて任せてたら通してくれて5完。確かこの時点で6位とかで, 上位もほぼ6完できてないから, ワンチャン5完で耐えるかなぁと祈る。
FGHどれならワンチャンあるか見たいな話で, 全員でFに特攻。carrotがいい感じの言い換えとか, DM分解とかも言ってて, 悪くない線は言ってた気がするけど, 流石にキツくて, 最後の最後はもう抜かないでくれ〜〜〜〜〜!!!ってみんなでお祈り。
29分の弊チーム「あと1分!さっさと終われ!」
— Motsu_xe (@Motsu_xe) 2021年11月5日
30分の弊チーム「こんてすといずおーばー!
30分の弊チーム「31分終了!?フザケンナブッコロス」
31分の弊チーム「おわったああああああ!」
ABC207 解説
AtCoder Beginner Contest 207の解説記事です。私は2100点(91:09)31位でした。Dが銀河最難関で困り果てました。余裕持って解けなかったので解説の公開が遅れました。
A - Repression
思考
3つの整数から大きい2つの和を答える問題です。実装例ではsortしていますが、sumからminを引くなどの実装が、言語によってはかなり簡単にできます。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int a[3]={}; for(int i{};i<(3);++i){ cin >> a[i]; } sort(a, a+3); cout << a[1] + a[2] << endl; }
B - Hydrate
思考
操作を行なった回数を回とすると、水色のボールは個、赤色のボールは個となります。目標はです。のときは, 明らかに達成できません。逆にのときは、達成可能となり、そのようなは
となり、答えはとなります。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ ll a, b, c, d; cin >> a >> b >> c >> d; if(b>=c*d){ cout << -1 << endl; } else{ cout << (a-1)/(c*d-b) + 1 << endl; } }
C - Many Segments
思考
ちゃんとやるだけなんですが、まともにやろうとすると破滅します。整数の区間だと思って、全て半開区間に帰着させてから解こうとしていたんですが、よく見ると実数の区間の話らしいので、これでは解けません。
ただlとrを2倍してみると、整数の区間だと思って解いても問題なくなるため、簡単に実装できます(偶数しか無くなって、端っこでバグらないためです。証明は各自でお願いします)。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> l(n), r(n); for(int i{}, t;i<(n);++i){ cin >> t >> l[i] >> r[i]; l[i] *= 2, r[i] *= 2; if(t==1) ++r[i]; else if(t==3) ++l[i], ++r[i]; else if(t==4) ++l[i]; } int ans{}; for(int i{};i<(n);++i){ for(int j{};j<(i);++j){ if(!(r[i]<=l[j] or r[j]<=l[i])) ++ans; } } cout << ans << endl; }
D - Congruence Points
思考
かなり難しいです。
N=1の場合は自明にYesなので、以下Nは2以上とします。
平行移動と回転操作は、可換ではありませんが、回転させたあとに平行移動させるのと同じ動きを、平行移動させた後に回転させることでも達成できます。また平行移動同士、回転移動同士は1回にまとめることができます。
よって1回平行移動させてから1回回転させればいいことがわかります。
またTを平行移動させた集合にSを一致させられることと、SをTに一致させられることは同値です。
よってTは適当に平行移動して、重心は原点にあるとして良いです。
回転操作によって、重心と原点の距離は変わらないため、Sを1回平行移動させた時点で、Sの重心は原点にある必要があります。よってSを平行移動させて、原点に移動させれば、あとはSを回転させてTに一致させられるかを判定すれば良いです。
Sには原点でない点が含まれています。その点が、回転でTのどの点に一致するかを全探索すると、回転の角度の候補がたかだかN個求まります。この全ての角度についてSを回転させて、Tと一致するかを求めれば良いです。
整数だけでこれを処理するのは難しいので、小数に甘えて、誤差に気をつけて計算するといいです(std::complexとかを使うと楽です)。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int A{}, B{}, C{}, D{}; vector<int> a(n), b(n), c(n), d(n); for(int i{};i<(n);++i){ cin >> a[i] >> b[i]; A+=a[i], B+=b[i]; a[i]*=n, b[i]*=n; } for(auto&i:a) i-=A; for(auto&i:b) i-=B; for(int i{};i<(n);++i){ cin >> c[i] >> d[i]; C+=c[i], D+=d[i]; c[i]*=n, d[i]*=n; } for(auto&i:c) i-=C; for(auto&i:d) i-=D; if(n==1){ cout << "Yes" << endl; return; } if(!a[0] and !b[0]){ swap(a[0], a[1]); swap(b[0], b[1]); } map<pair<int,int>, bool> mp; for(int i{};i<(n);++i){ mp[make_pair(c[i],d[i])] = true; } using com = complex<double>; vector<com> x(n); for(int i{};i<(n);++i){ x[i]=com(a[i], b[i]); } constexpr double eps = 1e-9; for(int i{};i<(n);++i){ if(a[0]*a[0]+b[0]*b[0]==c[i]*c[i]+d[i]*d[i]){ com tmp(c[i], d[i]); tmp/=x[0]; map<pair<int,int>, bool> mp2; bool fl = true; for(int j{};j<(n);++j){ com y = x[j]*tmp; int X = lround(y.real()), Y = lround(y.imag()); if(abs(y.real()-X)>eps or abs(y.imag()-Y)>eps){ fl = false; break; } if(!mp[make_pair(X, Y)] or mp2[make_pair(X, Y)]){ fl = false; break; } mp2[make_pair(X, Y)] = true; } if(fl){ cout << "Yes" << endl; return; } } } cout << "No" << endl; }
E - Mod i
思考
(数列の番目までを個に切り分ける通り数)
とすると、これは次のようにで計算できます。
がの倍数
ただしこれだと間に合いません。ただ、がの倍数という条件が、の累積和をとしてであることに気をつけると、なる最も右のをとすると
のように計算できます。これでで計算できました。
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll = long long; int main(){ int n; cin >> n; vector<ll> a(n); for(auto&i:a) cin >> i; auto dp = vector(n+1, vector<modint1000000007>(n+1)); auto b = vector(n+1, vector(n+1,-1)); b[1][0] = 0; dp[0][0] = 1; ll s{}; for(int i{};i<(n);++i){ s+=a[i]; for(int j{1};j<=n;++j){ if(b[j][s%j]!=-1){ dp[i+1][j] = dp[b[j][s%j]][j] + dp[b[j][s%j]][j-1]; } b[j][s%j] = i+1; } } modint1000000007 ans; for(int j{1};j<=(n);++j){ ans += dp[n][j]; } cout << ans.val() << endl; }
F - Tree Patrolling
思考
高橋君が自分の頂点しか警備しない場合、これは標準的な二乗の木DPで、DFSしながら、各ノードの部分木で、警備された頂点がK個となる通り数を配列で持つことによって計算できます*1。
これを少し派生させて、各ノードについて、
「自身は警備されていない、部分木について警備された頂点がK個となる通り数」
「自身は警備されているが、高橋君はいない、部分木について警備された頂点がK個となる通り数」
「自身に高橋君がいる、部分木について警備された頂点がK個となる通り数」
を3つの配列で保持してやると、2乗の木DPで計算できます。
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using mint = modint1000000007; struct sq{ vector<mint> a, b, c; }; vector<mint> conv(const vector<mint>&a, const vector<mint>&x){ vector<mint> na(a.size()+x.size()-1); for(int i{};i<(a.size());++i){ for(int j{};j<(x.size());++j){ na[i+j]+=a[i]*x[j]; } } return na; } sq square(vector<vector<int>>&e,int i,int p){ vector<mint> a={1}, b={1}, c={1}; int ch{}; for(auto j:e[i]) if(j!=p){ ++ch; auto [A, B, C]=square<T>(e,j,i); vector<mint> x=A, y, z=A; if(x.size()<B.size()+1) x.resize(B.size()+1); for(int k{};k<(B.size());++k) x[k+1]+=B[k]; y=x; if(y.size()<C.size()+1) y.resize(C.size()+1); for(int k{};k<(C.size());++k) y[k+1]+=C[k]; z.resize(max({A.size(), B.size(), C.size()})); for(int k{};k<(B.size());++k) z[k]+=B[k]; for(int k{};k<(C.size());++k) z[k]+=C[k]; a = conv(a, x), b = conv(b, y), c = conv(c, z); } if(b.size()<a.size()) b.resize(a.size()); for(int k{};k<(a.size());++k) b[k]-=a[k]; c.resize(c.size()+ch); for(int k{c.size()};--k>=ch;) c[k]=c[k-ch]; for(int k{};k<(ch);++k) c[k] = 0; return {a, b, c}; } int main(){ int n; cin >> n; auto e = vector(n, vector<int>()); for(int i{}, u, v;i<(n-1);++i){ cin >> u >> v;--u, --v; e[u].push_back(v); e[v].push_back(u); } auto [a,b,c] = square(e, 0, -1); a.resize(n+1);b.resize(n);c.resize(n); cout << 1 << '\n'; for(int i{1};i<=n;++i){ cout << (a[i]+b[i-1]+c[i-1]).val() << '\n'; } }
終わりに
EFも普通に大変で、かつDが異常難易度だったので、かなりむずかった印象です。
*1:尤もこの設定なら、ただの二項係数で計算できます
ABC206 解説
AtCoder Beginner Contest 206(Sponsored by Panasonic) の解説記事です。私は2100点(61:20)78位でした。
A - Maxi-Buying
思考
消費税の計算、もっと一般に有限小数、もっと一般に有理数の掛け算は、安易にdoubleなどの浮動小数点数を用いると、誤差でバグりやすいため、などのように実装すると安全です。
まあ正直少数使っても通るとは思います。?:の三項演算子を用いても良いですが, 条件式3つあると頭が壊れるので、安全にif文で書いています。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; n*=108; n/=100; if(n>206) puts(":("); else if(n==206) puts("so-so"); else puts("Yay!"); }
B - Savings
思考
1からMまでの整数の和はであることが知られていますから、2分探索などで境界を求めても良いですが、冷静になると日程度しかかからないため、愚直にシミュレーションしても十分高速です。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; for(int i{1};;++i){ n-=i; if(n<=0){ cout << i << endl; return; } } }
C - Swappable
思考
Aが相異なるi, jを探すのは難しいですが, Aが同じi, jを探すのは容易です。よって全体からこれを引くことを考えます。となる(i, j)の組の総数は、なるiの個数をとしてとなることを利用して、登場する全てのCについてこれを考えれば良いです。これはstd::mapなどを用いて容易に実現可能です。
オーバーフローには気をつけましょう。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ ll n; cin >> n; map<int,ll> mp; for(int i{},a;i<(n);++i){ cin >> a; mp[a]++; } ll ans = n*(n-1)/2; for(auto&[a,b]:mp){ ans-=b*(b-1)/2; } cout << ans << endl; }
D - KAIBUNsyo
思考
とは同じ色にする必要があります。ここで登場する色を頂点とし、とを結ぶ辺を追加した、無向グラフを考えます。この連結成分にある色は最終的に同じ色になっている必要があり、逆に同じ連結成分にない色は同じにする必要があります。よって各連結成分を同じ色にするコストを考えればよく、これは(連結成分のサイズ)-1です。よってatcoder::dsuなどを用いて、これを計算すれば良いです。*1
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; int main(){ int n; cin >> n; vector<int> a(n); for(auto&i:a) cin >> i, --i; dsu d(200000); for(int i{};;++i){ if(i>=n-1-i) break; d.merge(a[i], a[n-1-i]); } cout << 200000 - d.groups().size() << endl; }
E - Divide Both
思考
求めたい集合は
となり、D以上U以下の互いに素な2以上の自然数の組の数を求める問題に帰着できました。これをで解くことができれば、調和級数からで解けて、十分高速です。
実際にこれは前計算の下で、で計算することができます。あるdに対して、両方dの倍数の組の数を求めるのは容易です。これから、包除原理を用いて、足し引きすることで、求めることができます。このとき、足し引きする際の係数は前計算計算できます*2。
実装例
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int l, r; cin >> l >> r; vector<ll> k(r+1, 1); for(int i{2};i<=(r);++i){ for(int j{2*i};j<=r;j+=i){ k[j] -= k[i]; } } ll ans{}; for(int g{2}; g<=r; ++g){ ll d = max(1, (l-1)/g), u = r/g; ans += (u-d)*(u-d); for(int j{2}; j<=u; ++j){ ans -= k[j] * (u/j-d/j)*(u/j-d/j); } } cout << ans << endl; }
F - Interval Game 2
思考
この手のゲームでは、とりあえずGrundy数を計算できるかどうかを考えることが有効です。
このゲームは、半開区間を頂点に、共通部分がある区間に辺を貼ったグラフで、1つの頂点を取り除いたら、辺で直接繋がっている頂点も取り除かれるとして、操作できなくなった人が負けというゲームになっています。一般のN頂点グラフについて考えると、これはGrundy数を計算するのに、残っている頂点の集合とかを考えないといけなそうで、多項式時間で解くのはかなり困難に見えます*3。
そこで区間であることを利用して、残っている辺の集合がいい感じになるのではないかと予想します。すると、ある区間を取り除くと、その左側、その右側の区間に分離し、それぞれは完全に独立したゲームになることがわかります。独立したゲーム*4のGrundy数は、それぞれのGrundy数のxorになることが知られているため、ある区間に含まれる区間についてのGrundy数を、区間が狭い順に計算してやれば良いことがわかります。*5
Grundy数を計算しているところですが、今回は時間に余裕があるのでlogつけていますが、線形でもできます。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> L(n), R(n); for(int i{};i<(n);++i){ cin >> L[i] >> R[i]; } auto G = vector(101, vector(101, 0u)); for(int len{1};len<=(100);++len){ for(int l{};l<=(100-len);++l){ int r = l + len; vector<int> tmp; for(int i{};i<(n);++i){ if(l<=L[i] and R[i]<=r) tmp.push_back(i); } set<unsigned> st; for(int i:tmp){ st.insert(G[l][L[i]]^G[R[i]][r]); } unsigned nw{}; for(unsigned u:st){ if(nw < u){ break; } else{ ++nw; } } G[l][r] = nw; } } puts(G[0][100]?"Alice":"Bob"); }
終わりに
EF共になかなか歯応えのある回だったと思います。Fでくだらないミスに気付くのに十分時間をかけてしまったのはかなりもったいなかったです。
ABC205 解説
AtCoder Beginner Contest 205 の解説記事です。私は2100点(43:06)25位でした。
A - kcal
思考
一般的な比の問題です。誤差や出力方式にだけ気をつけましょう。自分は小数出力の時は何も考えずにsetprecision(20)を付けていますが、失敗したことはないです。入力は整数ですが、どうせ浮動小数点数で扱うので、最初からdoubleで受け取っています。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ double a, b; cin >> a >> b; cout << setprecision(20) << a/100.0*b << endl; }
B - Permutation Check
思考
ある2つの数列が、一方の並び替えによって他方が得られるための必要十分条件は、2つの数列をソートした列が一致することです。今回は片方の数列はすでにソートされているので、Aをソートして(1,2,...,N)と一致するかを確認すれば良いです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(auto&i:a) cin >> i,--i; sort(begin(a),end(a)); for(int i{};i<(n);++i){ if(i!=a[i]){ cout <<"No" << endl; return; } } cout << "Yes" << endl; }
C - POW
思考
Cが奇数のときはAとBの大小を、Cが偶数のときはAの絶対値とBの絶対値の大小を比較すれば良いです。ちゃんと証明しようとすると若干大変ですが、偶数のときは割と明らかで、奇数のときは符号に気をつければ割と明らかです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int a,b,c; cin >> a >> b >> c; if(c%2){ if(a==b) cout <<"="; else if(a<b) cout<<"<"; else cout<<">"; } else{ if(abs(a)==abs(b)) cout <<"="; else if(abs(a)<abs(b)) cout<<"<"; else cout<<">"; } cout<<endl; }
D - Kth Excluded
思考
これどうやってもできそうに見えるんですが、丁寧にやらないと実装が破滅したり、下手したらTLEしそう、かなり厄介な問題だなぁという気持ちになります。
多少遅くてもTLEしないなら実装を簡単なの方法を考えます。最初に思いついたのは、二分探索です。K番目を求めるのは難しいですが、Xが何番目かを求めるのはそこそこ簡単なので、実際この方針でもできると思います*1。ですが、2分探索2回することになり、めんどいので、やめます。
の区間では、数が1増えると、番目も1増えるので、どの区間に属しているかと、が何番目かがわかればすぐに計算できるので、これをmapを利用して実装します。最初にこの方針が直感的に生えたんですが、実装めんどそうで棄却しちゃったんですが、やりたいことを整理したら、思ったよりも綺麗にかけることに気づきました。
実装例
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n,q; cin >> n >> q; vector<ll> a(n); for(auto&i:a) cin >> i; map<ll, ll> mp; mp[0]=0; for(int i{};i<(n);++i){ mp[a[i]-i] = a[i]+1; } for(ll _{},k;_<(q);++_){ cin >> k; auto it = mp.upper_bound(k); --it; cout << it->second + k-it->first << '\n'; } }
E - White and Black Balls
思考
i=N+Mの時点で条件を満たさないような場合は並べる方法は存在しません。以下並べる方法は存在するとします。
グリッドグラフを(0,0)から、右にN回、上にM回移動することで(N,M)に移動する問題を考えます。この設定で、右下の一部に侵入できないとした時の、移動の仕方の総数が求めるものです。
ここで、余事象を考えます。つまり右下に侵入してしまう場合を考えます。侵入してしまった場合の経路を、初めて侵入した位置で、下図のように折り返すことで、(0,0)から(M+K+1, N-K-1)への経路と1対1対応させることができます。
よって存在する場合は
通りとなります。
これ最近似たような話( (N,M)のカタラン数みたいな)をチームの人達と話したときに、この手法を聞いてなかったら、かなり沼っていた気がします。まあまともに考察しなくても、実験でエスパーできる範囲だとは思います。
実装例
#include<bits/stdc++.h> using namespace std; template <class Mint> struct combination; //二項係数の構造体 int main(){ int n, m, k; combination<modint1000000007> comb(2000001); cin >> n >> m >> k; if(n>m+k){ cout << 0 << endl; } else{ cout<<(comb(n+m, n)-comb(n+m, n-k-1)).val() << endl; } }
F - Grid and Tokens
思考
典型キーワードは「こんなんフローしかないやろ」です。制約が小さく、いわゆる多項式時間ならなんでも通る問題*2で、問題も明らかにマッチングっぽいので、流石にフローです。
ただどうフローを流すかは、結局天才構築か、経験によるパターンマッチング(激ウマギャグ)か、天啓を待つなどして思いつく必要があります。
グリッドのマッチングは、列や行をノードとして、ソースから行ノードに1流す、列ノードからシンクに1流す、とすることで、各行各列に1つだけしかマッチングできなくできます。さらに、マッチングできる行と列の対応は、駒に従います。1つの駒で1つのマッチングしかできないので、駒ノードは2つ作り、その2つの間に1だけ流すなどとやればできそうです。
こんな感じでフローと戯れていると、最終的に下図のようなフローの最大流が答えになることがわかります。
あとはACLを使って、丁寧に辺を張ればOKです。
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; int main(){ int h,w,n; cin >> h >> w >> n; int s=2*n+h+w, t=s+1; mf_graph<int> g(t+1); for(int i{};i<(h);++i){ g.add_edge(s,2*n+i,1); } for(int i{};i<(w);++i){ g.add_edge(2*n+h+i, t, 1); } for(int i{},a,b,c,d;i<(n);++i){ cin >> a >> b >> c >> d;--a,--b; for(int j{a};j<c;++j) g.add_edge(2*n+j, 2*i,1); for(int j{b};j<d;++j) g.add_edge(2*i+1, 2*n+h+j,1); g.add_edge(2*i, 2*i+1, 1); } cout << g.flow(s, t) << endl; }
終わりに
図を使った解説記事、初めて書いた気がします。雑な手書きでごめんなさい。コンテスト中にちゃんとした描画ソフトで解説書くのは難しいです。
ABC204 解説
AtCoder Beginner Contest 204 の解説記事です。私は2100点(45:41)30位でした。*1
A - Rock-paper-scissors
思考
3人じゃんけんでは、全員バラバラか、全員同じ手を出せばあいこになります。もしアラフェネの出した手が同じなら、サーバルも同じ手、アラフェネが別の手を出していれば、サーバルは残りの1手を出せば良いです。バラバラなら、3からアラフェネの手の合計を引く(xorとかでもいいです)などで簡単に実装できますが、どうやってもいいです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int x, y; cin >> x >> y; if(x==y) cout << x << endl; else cout << 3-x-y << endl; }
B - Nuts
思考
愚直にシミュレーションするだけで簡単に解けます。実装例では配列で受け取っていますが、その必要すらありません。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); ll ans{}; for(auto&i:a){ cin >> i; ans += max(i-10, 0); } cout << ans << endl; }
C - Tour
思考
スタート地点を固定して考えます。すると、DFSなりBFSなりで、到達可能な点を全列挙することでで解くことができます。よってスタート地点を全て考えるとで解くことができ、十分間に合います。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n, m; cin >> n >> m; auto e = vector(n, vector<int>()); for(int i{},a,b;i<(m);++i){ cin >> a >> b; --a, --b; e[a].push_back(b); } ll ans{}; for(int s{};s<(n);++s){ vector<bool> vis(n); vis[s] = true; queue<int> q; q.push(s); while(!q.empty()){ ++ans; int i = q.front();q.pop(); for(auto&j:e[i]) if(!vis[j]){ vis[j] = true; q.push(j); } } } cout << ans << endl; }
D - Cooking
思考
片方のオーブンを使用する料理の集合をとすると、料理を作るのにかかる時間はとなります。これはとすれば、とかけます。よって、料理の部分集合の合計調理時間として表される時間を全て求めることができれば、十分です。これは一般的な部分和問題で、簡単なDPで実装できます。std::bitsetを使用すると、実装量と実行時間を共に抑えられます。
実装例
#include<bits/stdc++.h> using namespace std; bool chmin(int&x,int y){if(x>y){x=y;return true;}return false;} int main(){ int n; cin >> n; vector<int> t(n); int s{}; bitset<100001> v; v[0] = 1; for(auto&i:t){ cin >> i, s+=i; v |= (v << i); } int ans = INT_MAX; for(int i{};i<=s;++i) if(v[i]){ chmin(ans, max(i, s-i)); } cout << ans << endl; }
E - Rush Hour 2
思考
辺の長さが状況によって異なる最短経路問題ですが、このような場合でも到達時点での最短な行き方をするようなダイクストラ法が回ることが知られています(類題(ネタバレ注意))。ある辺を辿るときに、最速な辿り方を考えます。結論から言うとが成立している間は待つのがよく、そうでない時は直ぐに渡るのが良いです。これはが成立している時は、1秒待てば、辺が1以上縮み、そうでない時は、辺が高々1しか縮まないことから言えます。よってこれに基づいてダイクストラ法を回せば良いです。
待つ待たないの境界時刻は、2次方程式を解けば十分高速に求められますが、誤差が怖いので、2次方程式を大雑把に解いた後、その付近で境界を適当に見つけるなどすると楽です(2分探索などでもOKです)。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ int n, m; cin >> n >> m; struct edge{ ll to, c, d; }; auto e = vector(n, vector(0, edge({}))); for(int i{},a,b,c,d;i<(m);++i){ cin >>a >> b >> c >> d; --a, --b; e[a].push_back(edge({b, c, d})); e[b].push_back(edge({a, c, d})); } vector<ll> dis(n, 1ll << 60); dis[0] = 0; using P = pair<ll, int>; priority_queue<P, vector<P>, greater<>> pq; pq.emplace(0, 0); while(!pq.empty()){ auto[D, u] = pq.top();pq.pop(); if(u == n-1){ cout << D << endl; return; } if(dis[u] < D) continue; for(auto[v, c, d]:e[u]){ if(d < D or d < (D+1)*(D+2)){ ll L = c + (d/(D+1)); if(dis[v]>D+L){ dis[v] = D+L; pq.emplace(D+L, v); } } else{ ll tmp = floor(sqrt(d+0.25)-2.5); chmax(tmp, 0); while(d >= (tmp+1)*(tmp+2)) ++tmp; ll L = c + (d/(tmp+1)); if(dis[v] > tmp + L){ dis[v] = tmp + L; pq.emplace(tmp+L, v); } } } } cout << -1 << endl; }
F - Hanjo 2
思考
Hがやたら小さく、Wがやたら大きいので、列の状態を適当に持って、漸化式を行列累乗などで解く問題だとおおよそ予想が立ちます。持つべき状態ですが、
列目より左が全て埋まっており、列目の埋まっている集合が、であるような敷き詰め方の通り数)
とすれば、この遷移はを次元ベクトルとして見れば、行列で書くことができます。この行列に関しては、実際に全ての埋め方を調べてやることで簡単に求めることができます。
時間計算量は、行列の構成に*2、行列累乗にとなり、十分高速です。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int h; ll w; using mint = modint998244353; template<class T> struct mat{}; //行列のライブラリ void rec(int b, vector<vector<mint>>&m, int i,int x, int y){ if(i == h){ ++m[y][b]; } else if((x>>i)&1) rec(b, m, i+1, x, y); else{ rec(b, m, i+1, x, y); rec(b, m, i+1, x, y|(1<<i)); if(i<h-1 and ((x>>(i+1))&1)==0) rec(b, m, i+1, x|(1<<(i+1)), y); } } int main(){ cin >> h >> w; auto m = vector(1<<h, vector<mint>(1<<h)); for(int b{};b<(1<<h);++b){ rec(b, m, 0, b, 0); } mat<mint> mt(m); mt = pw(mt, w); cout << mt(0,0).val() << endl; }
終わりに
今回はかなりサクサクめに解けたので、割と満足しています。
ABC203 解説
AtCoder Beginner Contest 203(Sponsored by Panasonic)の解説記事です。私は2100点(75:49)74位でした。
A - Chinchirorin
思考
最初同じものが2つ必ずあると思って、a,b,cのxorを出力しそうになりましたが、必ずしもそうでないので、チェックする必要があります。変に楽をしようとして、長さ3の配列に入れてソートしていますが、正直言われたままやる方が良い気がします。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int a[3]; for(int i{};i<(3);++i){ cin >> a[i]; } sort(a, a+3); if(a[0] == a[1]) cout << a[2] << endl; else if(a[1] == a[2] ) cout << a[0] << endl; else cout << 0 << endl; }
B - AtCoder Condominium
思考
N, Kは十分小さいので、全ての部屋番号を求めて、実際に足せば良いです。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin >> n >> k; int ans{}; for(int i{1};i<=(n);++i){ for(int j{1};j<=(k);++j){ ans += 100*i + j; } } cout << ans << endl; }
C - Friends and Travel costs
思考
真面目にシミュレーションすることもできますが、まず持ってるお金で限界まで進み、友達の下をすでに通り過ぎていたら、その時点でその友達からお金をもらうと考えてもよく、こう考えると実装が楽になります。
実装例
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n, k; cin >> n >> k; vector<ll> a(n), b(n), p(n); for(int i{};i<(n);++i){ cin >> a[i] >> b[i]; } iota(begin(p),end(p),0); sort(begin(p),end(p),[&](int i,int j){ return a[i] < a[j]; }); ll nw = k; for(auto&i:p){ if(nw < a[i]){ break; } else{ nw += b[i]; } } cout << nw << endl; }
D - Pond
思考
最初、全てのK*Kの区画について、中央値を求める問題と誤読してとか*1しか思いつかず、もう一度問題文を読むと、中央値の最小値を求める問題でした。
「中央値がX以下となる区画が存在する」という問題を解くことができれば、二分探索で解くことができます。中央値がX以下となるためには、その区画の半分以上*2がX以下であることが必要十分です。よって各マスについて、X以下かどうかだけの情報でよく、これは二次元累積和などを用いれば、の前計算で、各区画についてでX以下のマスの個数を答えることができるため、解くことができました。
中央値の定義を癖で昇順で考えて、サンプル合わずに首をひねり、そのデバッグ中に二分探索の上限を引き下げたのを忘れて、1e9を19にしたまま提出し1WA出て悲しい気持ちになります。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin >> n >> k; auto a = vector(n, vector(n, 0)); for(auto&v:a) for(auto&i:v) cin >> i; int l = -1, r = 1e9, m; auto s = vector(n+1, vector(n+1, 0)); int lim = (k*k+1)/2; while(r - l > 1){ m = (l+r)/2; s.assign(n+1, vector(n+1, 0)); for(int i{};i<(n);++i){ for(int j{};j<(n);++j){ s[i+1][j+1] = (a[i][j] <= m); } } for(int i{1};i<=(n);++i){ for(int j{1};j<=(n);++j){ s[i][j] += s[i][j-1]; } } for(int j{1};j<=(n);++j){ for(int i{1};i<=(n);++i){ s[i][j] += s[i-1][j]; } } bool f = false; for(int i{};i<=(n-k);++i){ for(int j{};j<=(n-k);++j){ if(s[i][j] - s[i+k][j] - s[i][j+k] + s[i+k][j+k] >= lim){ f = true; break; } } if(f) break; } if(f) r = m; else l = m; } cout << r << endl; }
E - White Pawn
思考
ある行について、白の置ける列が減る条件と、増える条件を考えていきます。
まず白の置ける列が減る条件は、もともとポーンが置けた列に、黒が置かれていることです。
次に白の置ける列が増える条件は、その列の隣にポーンが置けたときに、その列に黒が置かれていることです。ただし、増える条件は減る条件よりも優先されることに注意が必要です。
よって白の置ける列の集合を管理して、上の方の行から黒が置かれている点について、白の置ける列の変動をチェックすれば良いです。これはstd::setなどを用いれば、などで実行可能です。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; int main(){ int n, m; cin >> n >> m; map<int, vector<int>> mp; for(int i{}, x, y;i<(m);++i){ cin >> x >> y; mp[x].push_back(y); } set<int> st; st.insert(n); for(auto[x, v]:mp){ vector<int> pu, er; for(auto y:v){ if(y and st.count(y-1)) pu.push_back(y); else if(y < 2*n and st.count(y+1)) pu.push_back(y); if(st.count(y)) er.push_back(y); } for(auto y:er) st.erase(y); for(auto y:pu) st.insert(y); } cout << st.size() << endl; }
F - Weed
思考
高橋君と青木君の操作回数を共に考える必要があります。こういう問題は、いわゆる頂点倍化などの方法を取ることで、グラフの最短距離の問題に帰着できます。一見青木君の操作回数も、高橋君の操作回数も多く、頂点倍化すると頂点が増え過ぎて破滅するように見えますが、実は高橋君の操作回数は、高々30回程度であることがわかります(操作後の高さの最大値が半々になっていくことからわかります)。
Aはソート済として、(x以下番目の草を高橋君の操作回数y回で全て抜くための青木君の最小の操作回数)とします。これは適当に辺を生やすと、個くらいで、かつ各辺の長さは1以下となるので、0-1BFSでよしなに解くことができます。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin >> n >> k; vector<int> a(n); for(auto&i:a) cin >> i; sort(begin(a),end(a)); using P = pair<int, int>; vector<int> p(n); auto e = vector(n+1, vector<int>()); for(int i{};i<(n);++i){ p[i] = upper_bound(begin(a),end(a),a[i]/2) - begin(a); e[p[i]].push_back(i+1); } auto d = vector(n + 1, vector(32, INT_MAX)); deque<P> dq; dq.emplace_back(0, 0); d[0][0] = 0; while(!dq.empty()){ auto[x,y] = dq.front();dq.pop_front(); if(x < n and d[x+1][y] > d[x][y] + 1){ dq.emplace_back(x+1, y); d[x+1][y] = d[x][y] + 1; } if(x and d[x-1][y] > d[x][y]){ dq.emplace_front(x-1, y); d[x-1][y] = d[x][y]; } if(y < 31){ for(auto i:e[x]) if(d[i][y+1] > d[x][y]){ dq.emplace_front(i, y+1); d[i][y+1] = d[x][y]; } } } for(int i{};i<(32);++i){ if(d[n][i]<=k){ cout << i << " " << d[n][i] << endl; break; } } }
終わりに
途中で書くのに飽きて、Fの解説が適当すぎるのは申し訳ないです。奇跡的に後で思い返したら、書き換えるかも。