2020-10-06

ARC104 E - Random LIS 解説

ちょっとだけ面白い解き方をしたので解説として残しておく。
E - Random LIS

問題概要

長さ $N\leq6$ の数列 $X$ は、 $i$ 番目の要素が $1\leq X_i\leq A_i$ を満たす整数として一様分布で与えられる。最長増加部分列の長さの期待値を求めよ。

解法

LISは $X_i$ の大小関係で完全に決まるから、大小関係が一致しているような数列を数え上げられれば十分。

大小関係の型の取り方は、まず一致しているかどうかを無視して $N!$ 通りの順番で並べ、隣接する2つが一致しているか否かの $2^{N-1}$ 通りを考えば良い。この際被ったもの(例えば $1\lt 2=3,1\lt 3=2$ は同じ関係である)は適当に無視すれば良い。

あとは大小関係の型が一致する数列を数え上げれば良い。このとき一致している項に関しては $A_i$ の最小を上限として選べるので、長さ $L\leq N$ の数列 $Y$ が、 $i$ 番目の要素として $1\leq Y_i\leq B_i$ の範囲を全て動くとき、単調増加列の数を数え上げるという問題に言い換えられた(ここまでがわからなかったら公式解説とか読んで)。

「初項が $x$ 以上であるような長さ $L$ の数列 $Y$ が、 $i$ 番目の要素として $1\leq Y_i\leq B_i$ の範囲を全て動くとき、単調増加列の数」を $f_Y(x)$ と定義する。ただし与えられる $B$ は単調増加として良い。*1このとき求めるべきは $f_Y(1)$ となる。ここで $Y$ から初項を除いた数列 $Y'$ を考えると
$\begin{align} \qquad f_Y(x)=\sum_{z=x}^{B_0}f_{Y'}(z+1) \end{align}$
となることに注意する。ここで上昇階乗冪というものを導入する。
$\begin{align} \qquad x^{(n)}=\prod_{i=0}^{n-1}(x+i)=x(x+1)...(x+n-1) \end{align}$
このとき、重要な性質として
$\begin{align} \qquad \sum_{x=1}^{X} x^{(n)}=\frac1{n+1}X^{(n+1)} \end{align}$
が成立する(証明は簡単)。これを利用して実際に $f_Y$ を求める。 $f_Y$ が $l$ 次の上昇階乗冪多項式で表せることを帰納的に示す。

$l=0$ のとき、数列は空なので $1$ 通りであるから $f_Y(l)=1$ となり条件を満たす。

$l>0$ のとき、長さ $l-1$ で成立しているとして $f_{Y'}(x)=\sum_{i=0}^{l-1}a_ix^{(i)}$ と書けたとする。このとき
$\begin{align} \qquad f_Y(x)&=\sum_{z=x}^{B_0}f_{Y'}(z+1)\\ &=\sum_{z=x+1}^{B_0+1}f_{Y'}(z)\\ &=\sum_{z=x+1}^{B_0+1}\sum_{i=0}^{l-1}a_iz^{(i)}\\ &=\sum_{i=0}^{l-1}\sum_{z=x+1}^{B_0+1}a_iz^{(i)}\\ &=\sum_{i=0}^{l-1}a_i\left(\sum_{z=1}^{B_0+1}z^{(i)}-\sum_{z=1}^{x}z^{(i)}\right)\\ &=\sum_{i=0}^{l-1}a_i\left(\frac{1}{i+1}(B_0+1)^{(i+1)}-\frac{1}{i+1}x^{(i+1)}\right)\\ &=\sum_{i=0}^{l-1}a_i\left(\frac{1}{i+1}(B_0+1)^{(i+1)}-\frac{1}{i+1}x^{(i+1)}\right)\\ &=\sum_{i=1}^l\frac{a_{i-1}}{i}(B_0+1)^{(i)}-\sum_{i=1}^l\frac{a_{i-1}}{i}x^{(i)}\\ \end{align}$
となり、示された。

上昇階乗冪多項式で表せることを示したついでに、具体的な計算方法もわかったので、あとは計算するだけである。

最後に計算量を確認する。 $l$ 次上昇階乗冪多項式の積分操作は素朴にやって $O(l)$ *2、代入操作は素朴にやると $O(l^2)$ かかるが、上昇階乗冪を下位の次数から順番に求めれば $O(l)$ で実行できる。よって再帰1回は $O(l)$ で実行されているから、全体で $O(l^2)$ で計算される。Ordered Bell numberを $F_N$ とすれば、全体の計算量は $O(N!2^N\log F_N+N^2F_N)$ となり、 $F_N\leq N!2^{(N-1)}$ に注意して十分高速である。

実装例

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}

template <class T> int LIS(vector<T>&a){
    int n=a.size();
    vector<T> l(n+1,numeric_limits<T>::max());
    for(int i{};i<(n);++i){
        *lower_bound(l.begin(),l.end(),a[i])=a[i];
    }
    for(int i{1};i<=(n);++i){
        if(l[i]==numeric_limits<T>::max()) return i;
    }
}

using mint=modint1000000007;

mint substitution(const vector<mint>&f,mint x){
    mint ans{},X{1};
    int n=f.size();
    for(int i{};i<(n);++i){
        ans+=f[i]*X;
        X*=x;
        ++x;
    }
    return ans;
}

vector<mint> rec(vector<int>&a){
    if(a.empty()) return {1};
    int A=a.back();
    a.pop_back();
    auto D=rec(a);
    int n=D.size();
    vector<mint> I(n+1);
    for(int i{1};i<=(n);++i){
        I[i]=-D[i-1]/i;
    }
    I[0]=-substitution(I,A+1);
    return I;
}

void solve(){
    unsigned n;
    cin>>n;
    vector<int> a(n);
    for(auto&i:a) cin>>i;
    vector<int> p(n);
    iota(p.begin(),p.end(),0);
    set<vector<vector<int>>> st;
    do{
        for(unsigned j{};j<(1u<<(n-1));++j){
            vector<vector<int>> v(1);
            unsigned b=j;
            for(auto&i:p){
                v.back().push_back(i);
                if(b&1u) v.emplace_back();
                b>>=1u;
            }
            for(auto&u:v) sort(u.begin(),u.end());
            st.insert(v);
        }
    }while(next_permutation(p.begin(),p.end()));
    mint ans{};
    for(auto&v:st){
        int N=v.size();
        vector<int> T(n),A(N,INT_MAX);
        for(int i{};i<(N);++i){
            for(auto&j:v[i]){
                T[j]=i;
                chmin(A[N-1-i],a[j]);
            }
        }
        for(int i{1};i<(N);++i){
            chmin(A[i],A[i-1]);
        }
        mint P=substitution(rec(A),1);
        int L=LIS(T);
        ans+=P*L;
    }
    for(int i{};i<(n);++i){
        ans/=a[i];
    }
    cout<<ans.val()<<'\n';
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission #17219505 - AtCoder Regular Contest 104

まとめ

コンテスト中にΣ6個くっついた変数11個のやつそのまま手元で公式求めて打ち込もうとして、WolframがΣ5つで音をあげやがったやつを改良していい感じに解けた。解説で $O(N^3)$ でやってるところを $O(N^2)$ でやってるのでいい感じかも。

*1:もし単調増加でないとしても、単調増加の範囲でしか数える必要がない。こうしとかないと、後で公式が壊れる(なぜなら範囲によって0だったりするので)。

*2:実装例では剰余にmodintを素朴に使ってるので $O(l\log \mathrm{mod})$

2020-09-23

秋分コンテスト感想

なんか9/21にこんなツイートを見ました。

みんなで早押しクイズ対戦！
リンクをタップしてゲームに参加しよう。
出題問題: 宣伝(伏線とかではない)
ルームID: 94827https://t.co/jo8kpQiTNp #みんはや
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2020年9月21日

なんの宣伝なんやろって思ったら、なんか秋分コンテストとか言うのがあるらしい宣伝クイズだった。お誕生日コンと言うのに出たことが無いので、面白そうだし、出ようかなーと思いつつ、寝た(どうして…)。

起きたら結構盛り上がってたので、やってみるかーと思いやり始めたら、思いの外面白くて、思いの外やってしまった(最初,500点くらい取ったらやめようかと思ったけど、結果は1158点で43位でした。

問題別感想

A - Introduction to ESP Returns

1,2,3,4,5で始まる数列かぁと思い、色々試す(そのまま出力、10で割った余り、桁和etc...)。そのまま出力とかで10個ACだったから、0〜9とかではidなのかなぁとか思ったけど、よく考えたら、サンプルだからダブルカウントされてるだけだった。泣いちゃった。OEISとかにも突っ込んでひたすら投げた。ダメでした。

B - Self Introduction

My name is Motsu_xe! Nice to meet you.
律儀に自己紹介したのが良かった、てっきり任意の文章が通ると思ってたら、ユーザー名が必要らしい。

C - ピクトセンス

リア充しかわからん、もっと真面目に描いてくれ。いや歯槽膿漏わからなかったのは俺が悪かった。まあ辞書覗いたりとかもっとできることはあった。REでてびっくりした、0番目もどっかにあるんだろうなぁと思いつつスルー。

D - ゴーストバスターズ

最後の方だけ読んだらわかるかなぁとか思ったけど、よくわかんなくて捨てた、ごめんなさい。

E - Soup, Abandoned

なんとなく秋分とか聞いたらそれっぽいこと言って、とりあえず色々聞いて、整数入力、整数出力なのはわかったので、これで複雑な問題な訳は無いよなぁと思って、途中でOEISなことには気づいたんですが、botのステートがあることに気づかず敢えなく死亡。

F - THE EMPTY

最後の最後に一瞬のぞいて、Textで無を提出したけどダメだった。お誕生日コンがここまで謎解き要素が多いとはね、って感じ。

G - くそなぞなぞ

序盤にのぞいて、1,2,5だけ解いてそのままにしてた、普通に難しい。

H, I - 手紙１、２

変体仮名、万葉仮名であることはおおよそ察したが普通に読むのがだるくてやめてしまった、ごめんなさい。

K - Integer Choice

全員点とってなかったからスルーしてて、最後の最後に気付いた。68選んだやつは出てきなさい。

L - Sqrt

出力形式探るために、条件分岐RE出しまくって、ようやくOutput Onlyなことに気付く。「正の平方根」とか出力したけど、正が数字であることに気付くと解けた、これ大好き。

M - I like this

最後にちろっと見ただけ。入力形式あやふやだなぁとか思ってたけど、まさかの行列なの草。時間かけてたら気づけたかも(行列で正負0がありそうなので、まあ行列式の次くらいには思いつきそう)。

N - |n|

これわかんなかったの頭悪かった。後こう言うふざけたやつはソース覗くのは常套手段だよね、今度からは気をつける。

O - 沖縄

最初自分で法則見つけるのかと思って色々試したけど、ググったら一発だった。

P - Bus Travel

やろうかと思ったけど、序盤でなんか勘違いしてるのか矛盾して萎えちゃった。

Q - Tozangya ソーシャルディスタンス確保版

スカイツリーは3秒でわかったけど、それ以外が全然わからんかった。三角形の島とか南鳥島しか知らん…ググり方もよくわからなくて捨てた。

R - 私は秋分を知る。

真に全くわからなかった。もうちょい時間かけたかったかな。電車とか駅あたりからなら行けたかも。

S - Cat nuke' Challenge

最後にちろっとのぞいて、s抜けてるのかーって思ったはいいけど、解読する時間なくて諦め。もっと満遍なく問題をみるべきだった。

T - |あ|み|だ|く|じ|

Adblockも入れてなければ、スクショで画像とってきたので、罠ガンスルーして普通に解くだけの人になってた。冴えてて最初のaの行き先以外は間違えなくてサクサク行った。

U - 帰ってきた Picture

ぱっと見でなんもわかんなかったからスルーした。

V - String Achievement

1文字, 1000文字, a〜z,繰り返し,回文,秋分を回収。制約守らないのやろうか迷ったけど、フレーバーテキストで煽られそうな気がしたからやめたけど点数入ったらしい、なんやねん。

W - 嗚呼、恍恍惚惚　曠古、杲杲煌煌、兀兀甲骨

Twitterでみんな言ってるやつやーっていいながらスルーした()。

Y - A/B Problem

pic.twitter.com/ncxmn3L4wq
— Motsu_xe (@Motsu_xe) 2020年9月22日

pic.twitter.com/JCdnO4UAsR
— Motsu_xe (@Motsu_xe) 2020年9月22日

Z - Chess

1は普通にやるだけで、2はキャスリング知ってますか？3はアンパッサンを知ってますか？私は忘れてました。4は変な勘違いしてずるしないと無理だと思いました。5,6,7はまあ普通に無理やん何これって言ってた。ジャッジコードハックとかなんやろなぁとは思ったけど、スルー。

[ - Cheat

なんかジャッジ詰まってるときに、適当にYes/No両方投げてたらいつの間にか10点入ってた、YesだとCheatできるの面白すぎでしょ。

\ - Date Formatter

最後の最後に存在に気付いて、業務じゃーんつって投げたらWA、数で表されたじゃないんじゃ。

] - 数列クイズ

数列クイズなのでOEISにぶん投げる。1個だけあるので、投げるとちょっとだけ違う。OEISが間違ってたりするのかなーと思いつつ英語読みたくないので適当に投げると、1個増やしたら通って草。

^ - 🐿

今初めて見た、何これ。

_ - Echo

よくわからないのでとりあえずそのまま出したら負の点で草。ジャッジ見て察して、フローかなんかだっけこれ…っていいながらわからないので焼き鈍したら3回目くらいで200点出たので、提出。

` - Richard ⅭⅭⅭⅭⅭⅠↃↃↃↃↃⅭⅭⅭⅭⅭⅠↃↃↃↃↃↈↈⅭⅯⅩⅩⅡ

何これ笑問題なの笑

a - Shiritori 2020'

落ち葉とムカデでクエストキーゲットして、9,10,11以外はなんとかわかった。8がどう見ても海でしかないから、9は流石に「み」だろうと、「み」で始まる言語を探していたんだけど、見つからず。なんで「ん」なの？キレ

b - 【クエストキーワード提出用問題】Autumnal Equinox Quest

結局しりとりの2個だけ。お誕生日コンに慣れていなかったので、そんな辺鄙なところにあったのかみたいなのばっかで感動している。

全体感想

適当なノリで出たんだけど、想像の100倍凝っててびっくりしちゃった。運営の技術と熱量には驚かされる。とても楽しかったので、たまにやりたいなぁと思いつつ、俺の秋分の日はどこへ…と言う気持ちにもなりました()。
運営の皆さま、ありがとうございました。

2020-05-20

くSC001 解説

くそなぞなぞコンテスト解説記事

くそなぞなぞ Short Contest 001、unratedで参加したのですが、不甲斐ない結果となってしまいました…。ABC3完600(11:18)46位でした。

コンテストページ
 解説放送
 順位・パフォーマンス表

A問題

問題

家に戻る生き物ってなーんだ？

思考

家に戻ることは「帰る」と言うので、カエルです。

回答例

kaeru

B問題

問題

現在いる部屋ってなーんだ？

思考

現在の言い換えとして「今」があり、部屋として「居間」があります。

回答例

ima

C問題

問題

古典的な病気の倉庫ってなーんだ？

思考

古典的な、の言い換えは「クラシック」くらいしかありません。文字に起こして仕舞えば、どうみても「倉」「シック」です。*1

所感

クラシックは倉庫じゃないだろ*2って思う。けど、まあ問題作るとわかるけど、そこらへんの整合性とるのはむずいんですよね。作問者の気持ちになると、語順に囚われすぎるのはよくないかもですね。

回答例

kurasiltuku

D問題

問題

マグロが到着するドアの仕掛けってなーんだ？

思考

ドアの仕掛けと言うので思いつくのが、「どんでん返し」「黒板消しトラップ」くらいしか思いつきません。マグロの直接の言い換えは「ツナ」くらいしかなくて、あとは「トロ」とか「キハダ」とかかなぁと思いましたがむり。到着の言い換えは多くて絞りきれません。

解説

マグロといえば大トロです。大トロ着くで「オートロック」とかかっています。仕掛けと言うのか、まあ仕掛けといえば仕掛けか。*3

回答例

ootorotuku

終わりに

んー、BCがクソ遅かった(ちょっと考えてわからなくてDに行ってしまった)のがダメでしたかね。Short、短いだけで、普通に難しいです。

*1:本番中クラシック、倉、シック全てをすぐに思いついてたのに、全く気づかなかったのバグ。

*2:後置修飾と考えれば倉sickと言うのはなくはない

*3:安全なドアとかのが嬉しかったかもしれない。

2020-05-17

ABC168 解説

競技プログラミングコンテスト解説記事

かなりグダグダだったけど、今回のセットで全完できたのは結構偉いと思います。2100点(95:00)34位でした。

コンテストページ

A - ∴ (Therefore)

思考

pythonとかなら楽だったなと思いながら、愚直に実装。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    n%=10;
    if(n==3) cout<<"bon";
    else if(n==0 or n==1 or n==6 or n==8) cout<<"pon";
    else cout<<"hon";
    cout<<'\n';
}

コンテスト中のACコード

B - ... (Triple Dots)

思考

場合わけしてやるだけ、Aより楽じゃね？

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int k;
    string s;
    cin>>k>>s;
    if(s.length()>k) cout<<s.substr(0,k)<<"..."<<'\n';
    else cout<<s<<'\n';
}

コンテスト中のACコード

C - : (Colon)

思考

気合で、2つの針のなす角を求めれば、余弦定理でできる。なす角は、12の向きからの時計回りの角度を求めて、差をよしなにすれば良い(よく考えるとよしなにしないでそのまま突っ込んでもcosの値に影響はない)。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    double a,b,h,m,H,M;
    constexpr double pi=3.14159265358979;
    cin>>a>>b>>h>>m;
    H=h*pi/6+m*pi/360;
    M=m*pi/30;
    cout<<setprecision(20)<<sqrt(a*a+b*b-2*a*b*cos(H-M))<<'\n';
}

コンテスト中のACコード

D - .. (Double Dots)

思考

1からDFSして行けば最短経路がわかるので、DFSしながら手前の点を書き込んでいけば良い。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> e[100000];
    for(int i{};i<m;++i){
        int a,b;
        cin>>a>>b;
        --a,--b;
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    queue<int> q;
    q.push(0);
    vector<int> ans(n,-1);
    ans[0]=0;
    while(!q.empty()){
        int i=q.front();q.pop();
        for(auto&j:e[i]) if(ans[j]<0){
            ans[j]=i+1;
            q.push(j);
        }
    }
    cout<<"Yes"<<'\n';
    for(int i{1};i<n;++i) cout<<ans[i]<<'\n';
}

コンテスト中のACコード

E - ∙ (Bullet)

思考

仲の悪い条件を整理すると、0除算とかを一旦考えないことして適当に考えると
$\begin{align*} A_i*A_j+B_i*B_j=0&\Leftrightarrow A_i*A_j=-B_i*B_j\\ &\Leftrightarrow \frac{A_i}{B_i}=-\frac{B_j}{A_j}\\ &\Leftrightarrow \frac{A_i}{B_i}=-\frac1{\frac{A_j}{B_j}} \end{align*}$
となる。なので $A_i:B_i$ と言う比が重要であることがわかる。ここで、 $A_i=B_i=0$ のものは誰が相手でも仲が悪いので、無視して、最後にその数だけ足せば良い。よって $A_i\neq0\lor B_i\neq 0$ と考えて良い。重要なのは比なので、 $(A_i,B_i)$ を比が変わらない様に、互いに素で、 $A_i>0\lor(a_i,B_j)=(0,1)$ となるようにとりなおすことにする。これは同じ比の $(A_i,B_i)$ に対して一意に定まる。
mapなどを利用して、 $(a,b)$ と $(b,-a)$ (符号などは適切に変換する)の数をそれぞれ $X,Y$ とすると、これらの $X+Y$ 個の選び方は $2^X+2^Y-1$ で、他のものの選び方とは独立している。よってこれらを適切に掛け算すれば良い。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct modint; //いつもの
modint pwr(ll,ll) //mod累乗

int main(){
    ll n,a,b,d,c{};
    using P=pair<ll,ll>;
    map<P,int> v0,v1;
    cin>>n;
    for(int i{};i<n;++i){
        cin>>a>>b;
        if(a or b){
            d=gcd(a,b);
            a/=d;b/=d;
        }
        else{
            ++c;
            continue;
        }
        if(a<0) a=-a,b=-b;
        else if(a==0 and b<0) b=-b;
        v0[make_pair(a,b)]++;
        swap(a,b);
        b=-b;
        if(a<0) a=-a,b=-b;
        else if(a==0 and b<0) b=-b;
        v1[make_pair(a,b)]++;
    }
    map<P,bool> v;
    modint s{1};
    for(auto&[p,y]:v0){
        if(v[p]) continue;
        P q(p.second,p.first);
        q.second=-q.second;
        if(q.first<0) q.first=-q.first,q.second=-q.second;
        else if(q.first==0 and q.second<0) q.second=-q.second;
        v[q]=true;
        s*=pwr(2,y)+pwr(2,v1[p])-1;
    }
    cout<<s+c-1<<'\n';
}

コンテスト中のACコード

F - . (Single Dot)

思考

いい性質が全然なさそうで、行ける場所をDFSなりBFSなりで全探索する以外できそうもないです。よく考えると、座標圧縮してやることで、 $O(NM)$ 個くらいしか考える必要がないので、気合入れて実装すれば通ります。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

template<class T> void cc(vector<T> a,unordered_map<T,int>& nm,vector<int>& c){ //座標圧縮(aが座圧前、nmが前->後、cが後->前
    sort(a.begin(),a.end());
    fr(i,a.size()){
        if(i<a.size()-1&&a[i]==a[i+1]) continue;
        nm[a[i]]=c.size();
        c.emplace_back(a[i]);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(n),c(n),d(m),e(m),f(m),v(2*n+m+1),h(n+2*m+1);
    for(int i{};i<n;++i){
        cin>>a[i]>>b[i]>>c[i];
        v[i]=a[i];
        v[i+n]=b[i];
        h[i]=c[i];
    }
    for(int i{};i<m;++i){
        cin>>d[i]>>e[i]>>f[i];
        v[i+n*2]=d[i];
        h[i+n]=e[i];
        h[i+n+m]=f[i];
    }
    unordered_map<int,int> nmv,nmh;
    vector<int> V,H;
    cc(v,nmv,V);cc(h,nmh,H);
    auto lv=vector(V.size(),vector<bool>(H.size()));
    auto lh=vector(V.size(),vector<bool>(H.size()));
    for(int i{};i<n;++i){
        a[i]=nmv[a[i]];
        b[i]=nmv[b[i]];
        c[i]=nmh[c[i]];
        for(int I=a[i];I<b[i];++I) lv[I][c[i]]=true;
    }
    for(int i{};i<m;++i){
        d[i]=nmv[d[i]];
        e[i]=nmh[e[i]];
        f[i]=nmh[f[i]];
        for(int J=e[i];J<f[i];++J) lh[d[i]][J]=true;
    }
    ll ans{};
    int X=nmv[0],Y=nmh[0];
    stack<pair<int,int>> st;
    st.emplace(X,Y);
    int limv=V.size()-1,limh=H.size()-1;
    if(X==limv or Y==limh) return puts("INF"),0;
    auto vis=vector(limv,vector<bool>(limh));
    while(!st.empty()){
        auto[x,y]=st.top();st.pop();
        if(vis[x][y]) continue;
        vis[x][y]=true;
        ans+=(ll)(V[x+1]-V[x])*(H[y+1]-H[y]);
        if(x==0 and !lh[x][y]) return puts("INF"),0;
        if(y==0 and !lv[x][y]) return puts("INF"),0;
        if(x+1==limv and !lh[x+1][y]) return puts("INF"),0;
        if(y+1==limh and !lv[x][y+1]) return puts("INF"),0;
        if(x>0 and !vis[x-1][y] and !lh[x][y]) st.emplace(x-1,y);
        if(y>0 and !vis[x][y-1] and !lv[x][y]) st.emplace(x,y-1);
        if(x+1<limv and !vis[x+1][y] and !lh[x+1][y]) st.emplace(x+1,y);
        if(y+1<limh and !vis[x][y+1] and !lv[x][y+1]) st.emplace(x,y+1);
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

終わりに

タイトルが面白くていい感じですね。問題としても気合が結構要る感じで、†競技プログラミング†って感じがしました。楽しい。

2020-05-13

ARC017 D - ARCたんクッキー

競技プログラミングコンテスト解説記事

ちょっと面白い問題だったので共有します。

D - ARCたんクッキー

問題概要

区間加算、区間gcd取得クエリを処理せよ。

思考&解法

まず遅延セグ木に載せてぇ*1となりますが、これは
$gcd(a+c,b+c) \neq gcd(a,b)+c$ なのでまあ普通に載りません。
まず部分点問題(一点更新、区間gcd取得クエリ)を考えると、これは普通にセグ木に載せることで解くことができます。
満点でも同じことをしたいなぁと思うと、区間加算というクエリが厄介になります。区間加算を単純化したいと思うと、よくあるのは階差を取るという方法です。階差を取ることで、区間加算は、2点加算へと単純化することができます。その上でどのように区間gcdを得るかを考えます。結局
$gcd(A_l,A_{l+1},..,A_r)=gcd(A_l,A_{l+1}-A_l,..,A_r-A_{r-1})$
となる*2ので、区間加算1点取得クエリで $A_l$ を、1点更新、区間gcd取得クエリで $gcd(A_{l+1}-A_l,..,A_r-A_{r-1})$ を得れれば問題を解くことができます。前者は双対セグ木*3、後者はセグ木で対応可能なので、解けました。

コード

#include<bits/stdc++.h>
using namespace std;

int gcd(int,int); //C++14だとstdに無い(1WA)

struct STree{//1点更新区間gcd用のセグ木
   STree(vector<int>&v) //vで初期化
   void update(size_t i, int x) //i番目にxを加算
   int get(size_t l, size_t r) //gcd(v_l,..,v_r-1)を取得
};

struct LST{ //区間加算1点取得用の遅延セグ木
    LST(vector<int>) //vector<int>で初期化
    void update(size_t l, size_t r, int x) //[l,r)にxを加算
    int get(size_t l, size_t r) //[l,r)の総和を取得
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,t,l,r;
    cin>>n;
    vector<int> a(n),d(n-1);
    for(auto&i:a) cin>>i;
    for(int i{};i<n-1;++i) d[i]=a[i+1]-a[i];
    STree<int> st(d);
    LST<int> lst(a);
    cin>>m;
    for(int _{},_<m;++_){
        cin>>t>>l>>r;
        --l;
        if(t){
            lst.update(l,r,t);
            if(l) st.update(l-1,t);
            if(r<n) st.update(r-1,-t);
        }
        else cout<<gcd(lst.get(l,l+1),st.get(l,r-1))<<'\n';
    }
}

Submission #11914924 - AtCoder Regular Contest 017

感想

それなりに悩んでわからなくて、解説読んだら解説記事書くかって言った直後だったので、ちょっと気軽に解説を開いちゃったんですけど、満点解法にむけての「増減クエリに大して不変な要素が無いか考える」を読んだら3秒で解けました。こういう発想をぽんと持ってくるのはどうやったらいいんでしょうかね。

*1:セグメント木に「のる」と言う時、「乗る」「載る」どちらかなのかは疑問の余地がありますが、辞書引いてもデータ構造にのると言う意味が載ってないのでわかりません。私は「載る」だと思っています。

*2: $gcd(A_l,A_{l+1},..,A_r)|gcd(A_l,A_{l+1}-A_l,..,A_r-A_{r-1})$ はクソ自明で、逆も自明です。

*3:持ってないので遅延セグ木で殴ります。

2020-05-09

くBC005 解説

くそなぞなぞコンテスト解説記事

私はABF3完900(23:27)21位でした。てぃーいけ…嘘だよな…(F通ってことなきをえました。

コンテストページ
 順位・パフォーマンス表

A問題

問題

寝不足の時に顔に出る動物ってなーんだ？

思考

寝不足の時に顔に出る物は流石に隈しかなくて、熊です。

回答例

kuma

B問題

問題

完結してない果物ってなーんだ？

思考

完結してないの言い換えとして「未完結」「未完成」「未完」などがあり、蜜柑です。

回答例

mikann

C問題

問題

肉の競りに参加する物質ってなーんだ？

思考

肉の言い換えが「ミート」「フレッシュ」「しし」、競りの言い換えが「オークション」「競売」などしか思い付かず破滅。参加→酸化で、化学系かなーと思って無理を悟りました。

解説

競りはそのまま「競る」で、肉の言い換えは「ロース」です。よってセルロース。総称(ロース→肉)言い換えは非可逆なのでかなり難しいんですよねー。

回答例

seruro-su

D問題

問題

船上で燃えているものってなーんだ？

思考

船上の言い換えとして「on ship」で温湿布(あったかいけど燃えてはない)や、「甲板(乾パン)(燃えてない)」など思いつきましたが無理。船のパーっつ多すぎてきつい。

解説

燃えるといえば火事、船の上の火事といえば、舵です。

回答例

kazi

E問題

問題

何でも神視点での話になっちゃう場所ってどーこだ？

思考

神視点といえば、三人称視点のことですね、で？

解説

答え見てもわかんない、誰か教えて。神→天、視点→主格、ですか？(視点と主格は違うか？)

回答例

tennsyukaku

F問題

問題

まさに国家がやることってなーんだ？

思考

まさにの言い換えが、あまりしぼれず、放置。国家の言い換えとして「くに」「社稷」「nation」などが思いつき、nationで終わる単語ならいくらでもありそうということで、nationで終わる単語全探索です。ドネーションがあって、「ド」が弩級のド？？まあ考えるより投げようって思ったら通りました草。

回答例

done-syonn

終わりに

いや、死ぬほどきつかった。周りも解けてなさそうだったので、俺には無理やろなーって思ってたら、F解けたので助かった。EFはちょっと??って感じもあるけど、CDは順当にむずくて、良問ではあると思う(Cにしてはむずいけど)。

2020-05-03

ABC166 解説

競技プログラミングコンテスト解説記事

Eが簡単すぎてガチで引いて調子が崩れた(言い訳)。Fで大破滅しました…。かなり嫌な気持ちです。結果は96:40 598位。

コンテストページ

A - A?C

思考

やるだけオブザイヤー2020ノミネート。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    puts(s=="ABC"?"ARC":"ABC");
}

コンテスト中のACコード

B - Trick or Treat

思考

一度でも出現したら対象から外れるので、boolの配列を持って出現をチェックします。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){int n,k,d,a;
    cin>>n>>k;
    vector<bool> v(n,true);
    for(int i{};i<k;++i){
        cin>>d;
        for(int j{};j<d;++j){
            cin>>a;
            --a;
            v[a]=false;
        }
    }
    int ans{};
    for(int i{};i<n;++i) if(v[i]) ++ans;
    cout<<ans<<endl;
}

コンテスト中のACコード

C - Peaks

思考

道の両端で、真に高くはない方が対象から外れるというだけでB問題と同じです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m,a,b;
    cin>>n>>m;
    vector<int> h(n);
    vector<bool> g(n,true);
    for(auto&i:h) cin>>i;
    for(int i{};i<m;++i){
        cin>>a>>b;
        --a,--b;
        if(h[a]<=h[b]) g[a]=false;
        if(h[a]>=h[b]) g[b]=false;
    }
    int c{};
    for(int i{};i<n;++i) if(g[i]) ++c;
    cout<<c<<'\n';
}

コンテスト中のACコード

D - I hate Factorization

思考

$X$ が5乗数として非負のものの和か差になっているかを考えればよい。 $(C+1)^5-C^5=5C^4+..\geq 5C^4$ なので、 $A\gt 1000$ とかだと明らかに差も和も該当しない。なので $A\leq 1000$ なるものだけ考えておけばよい。1000以下の非負整数Cについて連想配列mpでmp[C^5]=Cとしておいて、AかBを固定すれば簡単にチェックできる。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ll x;
    cin>>x;
    unordered_map<ll,int> mp;
    for(int i{1000};i--;){
        ll c{1};
        for(int j{};j<5;++j) c*=i;
        if(mp[c+x])
            return cout<<mp[c+x]<<" "<<i<<endl,0;
        if(mp[x-c])
            return cout<<mp[x-c]<<" "<<-i<<endl,0;
        mp[c]=i;
    }
}

コンテスト中のACコード

E - This Message Will Self-Destruct in 5s

思考

$i\lt j$ とすると $A_i+A_j=j-i\Leftrightarrow A_i+i=j-A_j$ となっていればよい。よって連想配列に $j-A_j$ の個数を保存しながら、配列を右から舐めていって、数えていけばいい。~~D問題のが100倍むずいだろ~~D問題でちょっとめんどい解法使ってたからDのがむずい気がしたけど、そうでもないかも、でもEのがやっぱ簡単だとは思う。遅刻しなければFAが…って言おうとしたけど、まあ2分切れたかは怪しいな。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto&i:a) cin>>i;
    unordered_map<int,int> mp;
    ll ans{};
    ifr(i,n){
        ans+=mp[a[i]+i];
        mp[i-a[i]]++;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Three Variables Game

思考

まず $A+B+C\neq 2$ のとき、少ない方から多い方に、同じなら適当に移すことで達成できるなら達成できるし、失敗するようなら失敗する。これを示す。
$A+B+C=0$ のときはどうやっても無理。
$A+B+C=1$ のときは、全ての操作が、選択肢が1つ以下なので、OK。
$A+B+C\geq 3$ のとき。もし初期状態で0が2つあって、初手でその2つが選ばれた場合は無理。初手でその2つが選ばれなければ、0は1つになる。よって全て初期状態で0が1つ以下の場合に帰着される。定めた移し方では、~~0の数は増えることはない~~増えるとしたら0が0個のときだけなので、常に0は1つ以下となり、必ず失敗しない。
よって示された。
あとは $A+B+C=2$ のときを考えればいい。状態は(A,B,C)=(0,1,1),(1,0,1),(1,1,0),(2,0,0),(0,2,0),(0,0,2)の6つしかあり得ないので、どの状態に遷移可能かDPすればいい。実際の操作の復元は、可能な操作をDPの結果から遡っていけばいい。ところでいい感じの実装ありますか？？破滅しました。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,A,B,C;
    cin>>n>>A>>B>>C;
    string ans;
    ans.reserve(n);
    if(A+B+C==2){
        auto v=vector(n+1,vector(6,false));
        if(!A+!B+!C==1){
            if(!A) v[0][0]=true;
            if(!B) v[0][1]=true;
            if(!C) v[0][2]=true;
        }
        else{
            if(A) v[0][3]=true;
            if(B) v[0][4]=true;
            if(C) v[0][5]=true;
        }
        vector<string> s(n);
        for(int i{};i<n;++i){
            cin>>s[i];
            if(s[i]=="AB"){
                if(v[i][0]) v[i+1][1]=true;
                if(v[i][1]) v[i+1][0]=true;
                if(v[i][2]) v[i+1][3]=v[i+1][4]=true;
                if(v[i][3] or v[i][4]) v[i+1][2]=true;
            }
            if(s[i]=="AC"){
                if(v[i][0]) v[i+1][2]=true;
                if(v[i][2]) v[i+1][0]=true;
                if(v[i][1]) v[i+1][3]=v[i+1][5]=true;
                if(v[i][3] or v[i][5]) v[i+1][1]=true;
            }
            if(s[i]=="BC"){
                if(v[i][1]) v[i+1][2]=true;
                if(v[i][2]) v[i+1][1]=true;
                if(v[i][0]) v[i+1][4]=v[i+1][5]=true;
                if(v[i][4] or v[i][5]) v[i+1][0]=true;
            }
            bool F{};
            for(int j{};j<6;++j) F=F||v[i+1][j];
            if(!F) return puts("No"),0;
        }
        for(int j{};j<6;++j) if(v[n][j]){
            cout<<"Yes"<<'\n';
            int t=j;
            stack<char> ans;
            for(int i{n};i--;){
                if(s[i]=="AB"){
                    if(t==0) ans.push('B'),t=1;
                    else if(t==1) ans.push('A'),t=0;
                    else if(t==2){
                        if(v[i][3]) ans.push('B'),t=3;
                        else ans.push('A'),t=4;
                    }
                    else if(t==3) ans.push('A'),t=2;
                    else if(t==4) ans.push('B'),t=2;
                }
                if(s[i]=="AC"){
                    if(t==0) ans.push('C'),t=2;
                    else if(t==2) ans.push('A'),t=0;
                    else if(t==1){
                        if(v[i][3]) ans.push('C'),t=3;
                        else ans.push('A'),t=5;
                    }
                    else if(t==3) ans.push('A'),t=1;
                    else if(t==5) ans.push('C'),t=1;
                }
                if(s[i]=="BC"){
                    if(t==1) ans.push('C'),t=2;
                    else if(t==2) ans.push('B'),t=1;
                    else if(t==0){
                        if(v[i][4]) ans.push('C'),t=4;
                        else ans.push('B'),t=5;
                    }
                    else if(t==4) ans.push('B'),t=0;
                    else if(t==5) ans.push('C'),t=0;
                }
            }
            while(!ans.empty()) cout<<ans.top()<<'\n',ans.pop();
            return 0;
        }
        assert(false);
    }
    for(int i{};i<n;++i) {
        string s;
        cin>>s;
        if(s=="AB"){
            if(A<B){
                ++A;--B;
                ans+='A';
            }
            else{
                ++B;--A;
                ans+='B';
            }
        }
        if(s=="BC"){
            if(B<C){
                ++B;--C;
                ans+='B';
            }
            else{
                ++C;--B;
                ans+='C';
            }
        }
        if(s=="AC"){
            if(C<A){
                ++C;--A;
                ans+='C';
            }
            else{
                ++A;--C;
                ans+='A';
            }
        }
        if(A<0||B<0||C<0) return puts("No"),0;
    }
    cout<<"Yes"<<'\n';
    for(auto&c:ans) cout<<c<<'\n';
}

コンテスト中のACコード

終わりに

Fで適当こきすぎて、実装が破滅して終了しました。これどうやったらきれいに書けるの？？？