Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

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は問題読んではいたので, 問題概要説明して, ちょっと議論してたら, なんか行けそうとか言ってたから, 任せて放っていたら, なんかヌルッと通してきて, ビビり散らかしていました。


↑割とチームメンバーもこんな反応でした。

E(再)

この時点で割と10位以内は行けそうでしたが, ペナが結構終わってるので6完増えるとワンチャンやばいという状態で, 3人でEのバグとりをしようとしていました。2人は基本的にはcarrot46の主張の正誤判断とか, 独立したコードブロックのバグチェックとかをしていました。もはやEは通ればペナはどうでもいいので, 悩む前に提出みたいなことをしており, 最終的にミスにcarrot46が気付き, 残り16秒でブザービートを決めて, みんなで騒いでいました。マジでアツかった。

H

みてない。

コンテスト後

通ったああああって言ってたら順位表見たら3位!?!?!?!?!?!?ってなって騒ぎ散らかしており, 大変なことに。絶対勝てないだろって思ってたチームが3チーム以上あったので, 3位は完全に想定外でしばらく実感が湧きませんでした。
そのあとはツイートしたり, 雑談したりして, 夕食兼祝勝会みたいな感じで, たまたま買ってたシャンパ*4で祝杯を上げました。

感想

去年に続いて, 国内予選突破!!でもそれより強豪を上回っての3位が嬉しすぎます。これもひとえにチームメイトのおかげです, ほんとに。まあ下っ端なりに最低限の働きは出来たと思いますが, 折角アジアまた出れる, しかも初のオンサイトの予定ですし, 競プロも復帰して頑張ろうという気持ちになりました。アジア出場の皆さんはよろしくお願いします!
あと, なんか弊学から6チーム出場とかいうバグが発生していて流石に笑っています。
とりあえず楽しかったです!お疲れ様でした〜!

*1:だからと言って6チームも通るとは夢にも思っていなかったが…

*2:cuthbertが1人でできるって言った時は時は, 大抵任せておくとうまくいくので

*3:cuthbertは幾何担当

*4:アイドルマスターミリオンライブシアターデイズ5周年記念シャンパン, 好評発売中

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分解とかも言ってて, 悪くない線は言ってた気がするけど, 流石にキツくて, 最後の最後はもう抜かないでくれ〜〜〜〜〜!!!ってみんなでお祈り。

感想

念願の国内予選突破ってことで素直に嬉しいです!個人的にはEでかなりグダってしまって, 危うく戦犯になるところだったので, ギリギリで耐えてよかったです。今回のMVPは完全にcarrotでしたね〜仲間に恵まれました。アジア, 1大学1チームとか聞いて泣いています*4。打倒ゆたかあいず, こもれび, じあたま!首洗って待ってろ!*5

*1:確かcarrot46cuthbertMotsu_xeのASCIIでのLIS

*2:計算機科学における神託機械の如き性能という意味で, 大文字はチームメンバー3人の頭文字です。

*3:AのFAです。助かる。

*4:唯一の学内順位4位の予選突破チーム並感

*5:まあ、なんか賞品持って帰りてぇ!

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;
}

コンテスト中のACコード

B - Hydrate

思考

操作を行なった回数をT回とすると、水色のボールはA+TB個、赤色のボールはTC個となります。目標はA+TB\leq TCDです。B\geq CDのときは, 明らかに達成できません。逆にB\lt CDのときは、達成可能となり、そのようなT
A+TB\leq TCD\\
\Leftrightarrow T\geq \frac A{CD-B}\\
\Leftrightarrow T\geq\left\lceil\frac A{CD-B}\right\rceil
となり、答えは\left\lceil\frac A{CD-B}\right\rceilとなります。

実装例

#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;
    }
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

E - Mod i

思考

\mathrm{dp}_{i,j}=(数列のi番目までをj個に切り分ける通り数)

とすると、これは次のようにO(N^3)で計算できます。

\mathrm{dp}_{i,j}=\mathrm{sum}\{\mathrm{dp}_{k,j-1}|1\leq k\lt i, \sum_{l=k+1}^{i}A_ljの倍数\}

ただしこれだと間に合いません。ただ、\sum_{l=k+1}^{i}A_ljの倍数という条件が、Aの累積和をSとしてS_k\equiv S_i \bmod{j}であることに気をつけると、S_k\equiv S_i \bmod{j}なる最も右のkkとすると

\mathrm{dp}_{i,j}=\mathrm{dp}_{k,j}+\mathrm{dp}_{k,j-1}

のように計算できます。これでO(N^2)で計算できました。

実装例

#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;
}

コンテスト中のACコード

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';
    }
}

コンテスト中のACコード

終わりに

EFも普通に大変で、かつDが異常難易度だったので、かなりむずかった印象です。

*1:尤もこの設定なら、ただの二項係数で計算できます

ABC206 解説

AtCoder Beginner Contest 206(Sponsored by Panasonic) の解説記事です。私は2100点(61:20)78位でした。

コンテストページ

A - Maxi-Buying

思考

消費税の計算、もっと一般に有限小数、もっと一般に有理数の掛け算は、安易にdoubleなどの浮動小数点数を用いると、誤差でバグりやすいため、\mathbb{floor}(108N/100)などのように実装すると安全です。
まあ正直少数使っても通るとは思います。?:の三項演算子を用いても良いですが, 条件式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!");
}

コンテスト中のACコード

B - Savings

思考

1からMまでの整数の和はM(M+1)/2であることが知られていますから、2分探索などで境界を求めても良いですが、冷静になるとO(\sqrt{N})日程度しかかからないため、愚直にシミュレーションしても十分高速です。

実装例

#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;
        }
    }
}

コンテスト中のACコード

C - Swappable

思考

Aが相異なるi, jを探すのは難しいですが, Aが同じi, jを探すのは容易です。よって全体からこれを引くことを考えます。A_i=A_j=Cとなる(i, j)の組の総数は、A_i=Cなるiの個数をnとしてn(n-1)/2となることを利用して、登場する全ての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;
}

コンテスト中のACコード

D - KAIBUNsyo

思考

A_iA_{N+1-i}は同じ色にする必要があります。ここで登場する色を頂点とし、A_iA_{N+1-i}を結ぶ辺を追加した、無向グラフを考えます。この連結成分にある色は最終的に同じ色になっている必要があり、逆に同じ連結成分にない色は同じにする必要があります。よって各連結成分を同じ色にするコストを考えればよく、これは(連結成分のサイズ)-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;
}

コンテスト中のACコード

E - Divide Both

思考

求めたい集合は

\{(x,y);L\leq x, y\leq R, g=\gcd(x,y), g\neq1, x\neq g, y\neq g\}\\
=\bigsqcup_{g=2}^{R}\{(x,y);L\leq x, y\leq R, \gcd(x,y)=g, x\neq g, y\neq g\}\\
=\bigsqcup_{g=2}^{R}\{(gX,gY);L\leq gX, gY\leq R, \gcd(X,Y)=1, X\gt1, Y\gt1\}\\
=\bigsqcup_{g=2}^{R}\{(X,Y);\max(2, \lceil L/g\rceil)\leq X, Y\leq \lfloor R/g\rfloor , \gcd(X,Y)=1\}

となり、D以上U以下の互いに素な2以上の自然数の組の数を求める問題に帰着できました。これをO(U)で解くことができれば、調和級数からO(R\log R)で解けて、十分高速です。

実際にこれは前計算O(R\log R)の下で、O(U)で計算することができます。あるdに対して、両方dの倍数の組の数を求めるのは容易です。これから、包除原理を用いて、足し引きすることで、求めることができます。このとき、足し引きする際の係数は前計算O(R\log R)計算できます*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;
}

コンテスト中のACコード

F - Interval Game 2

思考

この手のゲームでは、とりあえずGrundy数を計算できるかどうかを考えることが有効です。

このゲームは、半開区間を頂点に、共通部分がある区間に辺を貼ったグラフで、1つの頂点を取り除いたら、辺で直接繋がっている頂点も取り除かれるとして、操作できなくなった人が負けというゲームになっています。一般のN頂点グラフについて考えると、これはGrundy数を計算するのに、残っている頂点の集合とかを考えないといけなそうで、多項式時間で解くのはかなり困難に見えます*3

そこで区間であることを利用して、残っている辺の集合がいい感じになるのではないかと予想します。すると、ある区間を取り除くと、その左側、その右側の区間に分離し、それぞれは完全に独立したゲームになることがわかります。独立したゲーム*4Grundy数は、それぞれの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");
}

コンテスト中のACコード

終わりに

EF共になかなか歯応えのある回だったと思います。Fでくだらないミスに気付くのに十分時間をかけてしまったのはかなりもったいなかったです。

*1:実装では、これが(頂点数)-(連結成分の数)と一致するのでこちらを計算していますが、atcoder::dsuなら元のままでも簡単に計算できます

*2:証明してないですが、多分メビウス関数だと思います

*3:多分無理そう、これは勘です

*4:厳密にはゲームの直和とかの話になります

*5:Gの要素数を100にしていたせいで1度REを出し、そこからそれに気付くのに12分かかりました。あまりにも愚か。for文では呼び出されないんですが、st.insertの列で呼び出されているんですね。

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

D - Kth Excluded

思考

これどうやってもできそうに見えるんですが、丁寧にやらないと実装が破滅したり、下手したらTLEしそう、かなり厄介な問題だなぁという気持ちになります。

多少遅くてもTLEしないなら実装を簡単なの方法を考えます。最初に思いついたのは、二分探索です。K番目を求めるのは難しいですが、Xが何番目かを求めるのはそこそこ簡単なので、実際この方針でもできると思います*1。ですが、2分探索2回することになり、めんどいので、やめます。

(A_i, A_{i+1})区間では、数が1増えると、番目も1増えるので、どの区間に属しているかと、A_i+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';
    }
}

コンテスト中のACコード

E - White and Black Balls

思考

i=N+Mの時点で条件を満たさないような場合は並べる方法は存在しません。以下並べる方法は存在するとします。

グリッドグラフを(0,0)から、右にN回、上にM回移動することで(N,M)に移動する問題を考えます。この設定で、右下の一部に侵入できないとした時の、移動の仕方の総数が求めるものです。

f:id:Motsu_xe:20210613220810j:plain
(N,M,K)=(4,6,1)の図

ここで、余事象を考えます。つまり右下に侵入してしまう場合を考えます。侵入してしまった場合の経路を、初めて侵入した位置で、下図のように折り返すことで、(0,0)から(M+K+1, N-K-1)への経路と1対1対応させることができます。

f:id:Motsu_xe:20210613221852j:plain
(N,M,K)=(4,6,1)の図

よって存在する場合は

\binom{N+M}N-\binom{N+M}{N-K-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;
    }
}

コンテスト中のACコード

F - Grid and Tokens

思考

典型キーワードは「こんなんフローしかないやろ」です。制約が小さく、いわゆる多項式時間ならなんでも通る問題*2で、問題も明らかにマッチングっぽいので、流石にフローです。

ただどうフローを流すかは、結局天才構築か、経験によるパターンマッチング(激ウマギャグ)か、天啓を待つなどして思いつく必要があります。

グリッドのマッチングは、列や行をノードとして、ソースから行ノードに1流す、列ノードからシンクに1流す、とすることで、各行各列に1つだけしかマッチングできなくできます。さらに、マッチングできる行と列の対応は、駒に従います。1つの駒で1つのマッチングしかできないので、駒ノードは2つ作り、その2つの間に1だけ流すなどとやればできそうです。

こんな感じでフローと戯れていると、最終的に下図のようなフローの最大流が答えになることがわかります。

f:id:Motsu_xe:20210613222833j:plain

あとは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;
}

コンテスト中のACコード

終わりに

図を使った解説記事、初めて書いた気がします。雑な手書きでごめんなさい。コンテスト中にちゃんとした描画ソフトで解説書くのは難しいです。

*1:O(Q\log A\log N)とかになると思うので、雑に書きすぎると定数倍やばいかも?流石に大丈夫そう

*2:N=100だと流石になんでもは通らない

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

C - Tour

思考

スタート地点を固定して考えます。すると、DFSなりBFSなりで、到達可能な点を全列挙することでO(M)で解くことができます。よってスタート地点を全て考えるとO(NM)で解くことができ、十分間に合います。

実装例

#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;
}

コンテスト中のACコード

D - Cooking

思考

片方のオーブンを使用する料理の集合をSとすると、料理を作るのにかかる時間は\max(\sum_{i\in S}T_i, \sum_{i\notin S}T_i)となります。これはST = \sum_{i=1}^N T_iとすれば、\max(\sum_{i\in S}T_i, ST - \sum_{i\in S}T_i)とかけます。よって、料理の部分集合の合計調理時間として表される時間を全て求めることができれば、十分です。これは一般的な部分和問題で、簡単な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;
}

コンテスト中のACコード

E - Rush Hour 2

思考

辺の長さが状況によって異なる最短経路問題ですが、このような場合でも到達時点での最短な行き方をするようなダイクストラ法が回ることが知られています(類題(ネタバレ注意))。ある辺を辿るときに、最速な辿り方を考えます。結論から言うと\frac{D}{t+1}-\frac{D}{t+2}\geq1が成立している間は待つのがよく、そうでない時は直ぐに渡るのが良いです。これは\frac{D}{t+1}-\frac{D}{t+2}\geq1が成立している時は、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;
}

コンテスト中のACコード

F - Hanjo 2

思考

Hがやたら小さく、Wがやたら大きいので、列の状態を適当に持って、漸化式を行列累乗などで解く問題だとおおよそ予想が立ちます。持つべき状態ですが、

\mathrm{DP}_{i,S}=(i列目より左が全て埋まっており、i列目の埋まっている集合が、Sであるような敷き詰め方の通り数)

とすれば、この遷移は\mathrm{DP}_{i,S}2^H次元ベクトルとして見れば、行列で書くことができます。この行列に関しては、実際に全ての埋め方を調べてやることで簡単に求めることができます。

時間計算量は、行列の構成にO(6^H)*2、行列累乗にO(8^H\log W)となり、十分高速です。

実装例

#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;
}

コンテスト中のACコード

終わりに

今回はかなりサクサクめに解けたので、割と満足しています。

*1:遅刻したせいでABCトーナメントに負けて悲しい気持ちになっています。

*2:実装の形から明らかにこうと言うだけで、多分もっと強い評価はできる

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

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;
}

コンテスト中のACコード

D - Pond

思考

最初、全てのK*Kの区画について、中央値を求める問題と誤読してO(N^2K\log K)とか*1しか思いつかず、もう一度問題文を読むと、中央値の最小値を求める問題でした。

「中央値がX以下となる区画が存在する」という問題を解くことができれば、二分探索で解くことができます。中央値がX以下となるためには、その区画の半分以上*2がX以下であることが必要十分です。よって各マスについて、X以下かどうかだけの情報でよく、これは二次元累積和などを用いれば、O(N^2)の前計算で、各区画についてO(1)で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;
}

コンテスト中のACコード

E - White Pawn

思考

ある行について、白の置ける列が減る条件と、増える条件を考えていきます。

まず白の置ける列が減る条件は、もともとポーンが置けた列に、黒が置かれていることです。

次に白の置ける列が増える条件は、その列の隣にポーンが置けたときに、その列に黒が置かれていることです。ただし、増える条件は減る条件よりも優先されることに注意が必要です。

よって白の置ける列の集合を管理して、上の方の行から黒が置かれている点について、白の置ける列の変動をチェックすれば良いです。これはstd::setなどを用いれば、O(M\log M)などで実行可能です。

実装例

#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;
}

コンテスト中のACコード

F - Weed

思考

高橋君と青木君の操作回数を共に考える必要があります。こういう問題は、いわゆる頂点倍化などの方法を取ることで、グラフの最短距離の問題に帰着できます。一見青木君の操作回数も、高橋君の操作回数も多く、頂点倍化すると頂点が増え過ぎて破滅するように見えますが、実は高橋君の操作回数は、高々30回程度であることがわかります(操作後の高さの最大値が半々になっていくことからわかります)。

Aはソート済として、D_{x, y}=(x以下番目の草を高橋君の操作回数y回で全て抜くための青木君の最小の操作回数)とします。これは適当に辺を生やすと、O(N\log A)個くらいで、かつ各辺の長さは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;
        }
    }
}

コンテスト中のACコード

終わりに

途中で書くのに飽きて、Fの解説が適当すぎるのは申し訳ないです。奇跡的に後で思い返したら、書き換えるかも。

*1:set2つとかで中央値を管理するテクで、K*Kの区間をスライドしつつ計算する。定数倍的にワンチャン間に合いそうなんだよな。

*2:偶奇で微妙にズレる


スポンサードリンク