yukicoder209

うわっ…私の更新頻度、低すぎ…?

初めてyukicoderで全完できたので久しぶりに更新します

A問題 野菜が苦手

解法

とっさに算数ができないので肉も野菜も枚数全探索します

B問題 UMG

解法

中心を固定して両端を広げます。

C問題 木を道に

解法

次数が3以上の頂点全てについて2になるようにしたいです。実はこれは次数が1の頂点にくっつけまくればいいです。

D問題 umg tours

解法

制約的にDijkstra一回とかで済ませたいです。1を始点にすれば良さそう。
コストを0にできるのは一回だけなので、持つべき状態を(距離, 場所, 0にした回数)にすればいいです。JOIによくあるやつ

E問題 Kaiten Sushi?

問題

No.808 Kaiten Sushi? - yukicoder
自分の席が回るんですね。めちゃくちゃ酔いそう

解法

だいたい貪欲っぽくいけば良さそうだけど、サンプル1の通り先に奥から取ったほうがよい事があるっぽい。
次の次に取るものが変わらないようにしながら、次に取るものを一番奥にすればよさそうである。
例えば

4  7 9
 56 8

で今4にいるとき、次に取るべきお茶は6になる。
もし8を取ると、7のためにもう一周する必要があるので、7より前のお茶を取りたい。
5を取るよりは6を取ったほうが最終周とかで得になることがある。

これは

  • now : 今いるところ
  • a : nowから取れる一番近いところ(反対サイド)
  • b : aから取れる一番近いところ(今いるサイド)
  • c : (now,b)のb寄りのところ(反対サイド)

を調べ、cを取る。
ということをN回繰り返せば良い。setと二分探索を使えばO(NlogN)で解ける。
二分探索でバグらないようにsetには一周後と二周後を入れておくと楽

JOI2018予選 解説

はじめに

第18回情報オリンピック予選のA~Eをどうやって解いたかを書いておきます
コンテスト中の感じは参加記を見てください

A問題 ソーシャルゲーム

概要

自分で調べてください

解法

一日ずつシミュレートします.数式でえいしたらWAだったので

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int ans=0;
    while(c>0){
        c-=a;
        if(ans%7==6){
            c-=b;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B問題 すごろくと駒

解法

シミュレーションします.駒の座標をsetで持つと面倒なことを考える必要がなくなる

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    vi a(n);
    set<int> se;
    REP(i,n){
        cin>>a[i];
        se.insert(a[i]);
    }
    int m;
    cin>>m;
    REP(i,m){
        int k;
        cin>>k;
        k--;
        if(a[k]!=2019&&!se.count(a[k]+1)){
            se.erase(a[k]);
            a[k]++;
            se.insert(a[k]);
        }
    }
    REP(i,n){
        cout<<a[i]<<endl;
    }

    return 0;
}

C問題 マルバツスタンプ

解法

前から順番にそれがマルバツだったら答えを1増やす貪欲をします.
一応それでいい証明をしておくと,もしx個目を無視してx+1個目を代わりに使っても良くなることはないです(悪くなることはあります)
なぜなら,xを使うと次はx+2から見ますが代わりにx+1を使うと次はx+3から見ることになり,x+2から見たときのmaxがx+3から見たときのmaxより大きくなることはないからです.
以上より前から貪欲でOKです

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    string st;
    cin>>st;
    int ans=0;
    REP(i,n-1){
        if(st[i]!=st[i+1]){
            ans++;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

D問題 日本沈没

問題について

Q. いつもJOI王国みたいな感じで固有名詞を出さないのにいきなり日本を沈めるのな~ぜだ

解法

各状態を独立に与えられて島の個数を数えるのは明らかに間に合わないので,少しずつ動かしていって差分を数えていきたいです.
というわけで日本を少しずつ浮上させていきます.
土地が浮かび上がってくるとき,島の状態には次の変化の内1つが起こります

  • 土地の左右に島があるとき,2つがつながる.個数は1つ減る
  • 土地の左のみに島があるとき,島の右端が変化する
  • 土地の右のみに島があるとき,島の左端が変化する
  • 土地の左右に島がないとき,独立した島となる.個数は1つ増える

さて,区間を扱っていきたいんですが,区間の座標をいじったり調べたりするときによくあるパターンとして,右端と左端をそれぞれsetで持つという方法があります.
これをするといろいろな操作がしやすくて,この問題で必要な操作は

  • 左右に島があるか:x-1に右端があるか,x+1に左端があるか
  • 左右を繋げる:右端のx-1と左端のx+1を消す
  • 独立した島を増やす:右端と左端にxを入れる
  • 島の個数を数える:右端(または左端)のsizeを求める

というふうに実現できます.そしてこの問題はこれを知っているとやるだけに落ちます.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    priority_queue<P> que;
    REP(i,n){
        int x;
        cin>>x;
        if(!x){
            continue;
        }
        que.push({x,i});
    }
    set<int> l;
    set<int> r;
    int ans=0;
    while(que.size()){
        int t=que.top().fi;
        while(que.size()&&que.top().fi==t){
            P p=que.top();que.pop();
            int v=p.se;
            if(r.count(v-1)&&l.count(v+1)){//左右が存在して連結できる場合
                r.erase(v-1);
                l.erase(v+1);
            }else if(r.count(v-1)){//左だけ存在する場合
                r.erase(v-1);
                r.insert(v);
            }else if(l.count(v+1)){//右だけ存在する場合
                l.erase(v+1);
                l.insert(v);
            }else{//左右ともに存在しない場合
                l.insert(v);
                r.insert(v);
            }
        }
        chmax(ans,(int)l.size());
    }
    cout<<ans<<endl;
    return 0;
}

E問題 イルミネーション

解法

まずDPを知っていればO(N^2M)(40点)は瞬殺で,dp_{i}=(iを使ったときの最大値)としてそれ以前に遷移できるかをO(M)で調べればよいです.
これを最終的にO((N+M) log M)とかまで落としたいわけです.
まず,自分と同時に選んでは行けない場所がどこまでかということがもっと早くわかれば良くて,これは区間更新区間minの遅延セグメントツリーを書くとできます.
これを行うと,始点からその直前まではすべて遷移ができるので累積maxをとっておくことで高速に更新できます.
境界取得がO(log M)で,それをO(N)回,また前処理で[tex;O(M log M)]かかるので全体O((N+M) log M)でこの問題が解けました.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename Monoid,typename OperatorMonoid=Monoid>
struct LazySegTree{
    //0-indexed 閉区間
    using F=function<Monoid(Monoid,Monoid)>;    //要素同士の演算
    using G=function<Monoid(Monoid,OperatorMonoid)>;    //要素と作用素のマージ
    using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>;    //作用素同士のマージ
    using P=function<OperatorMonoid(OperatorMonoid,int)>;   //作用素を下に降ろす

    int size;
    vector<Monoid> data;
    vector<OperatorMonoid> lazy;
    const F f;  //要素同士の演算
    const G g;  //要素と作用素のマージ
    const H h;  //作用素同士のマージ
    const P p;  //作用素を下に降ろす
    const Monoid M1;    //単位元
    const OperatorMonoid OM0;   //作用素の単位元

    LazySegTree(int n,const F f,const G g,const H h,const P p,const Monoid &M1,const OperatorMonoid OM0)
        :f(f),g(g),h(h),p(p),M1(M1),OM0(OM0){
        size=1;
        while(size<n)size<<=1;
        data.assign(size*2,M1);
        lazy.assign(size*2,OM0);
    }

    void set(int k,const Monoid &x){
        //kをxに初期化
        //buildを忘れずに行うこと
        data[k+size-1]=x;
    }
    void build(){
        //構築 O(N)
        for(int k=size-2;k>=0;k--){
            data[k]=f(data[2*k+1],data[2*k+2]);
        }
    }
    void propagate(int k,int len){
        //長さlenのkから下へ伝播
        if(lazy[k]!=OM0){
            if(k<size-1){
                lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
                lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
            }
            data[k]=g(data[k],p(lazy[k],len));
            lazy[k]=OM0;
        }
    }

    Monoid update(int a,int b,const OperatorMonoid &x,int k,int l,int r){
        propagate(k,r-l+1);
        if(r<a||b<l){ //範囲外
            return data[k];
        }else if(a<=l&&b>=r){   //内部
            lazy[k]=h(lazy[k],x);
            propagate(k,r-l+1);
            return data[k];
        }else{
            return f(update(a,b,x,2*k+1,l,(l+r)/2),
                    update(a,b,x,2*k+2,(l+r)/2+1,r));
        }
    }
    Monoid update(int a,int b,const OperatorMonoid &x){
        //[a,b]をxに変更
        return update(a,b,x,0,0,size-1);
    }

    Monoid query(int a,int b,int k,int l,int r){
        propagate(k,r-l+1);
        if(r<a||b<l){
            return M1;
        }else if(a<=l&&r<=b){
            return data[k];
        }else{
            return f(query(a,b,2*k+1,l,(l+r)/2),
                    query(a,b,2*k+2,(l+r)/2+1,r));
        }
    }
    Monoid query(int a,int b){
        return query(a,b,0,0,size-1);
    }

    Monoid operator[](const int &k){
        return query(k,k);
    }
    void debug(){
        REP(i,size){
            cerr<<query(i,i)<<" ";
        }cerr<<endl;
    }
};
int main(){
    int n,m;
    cin>>n>>m;
    vl vec(n);
    REP(i,n){
        cin>>vec[i];
    }
    auto f=[](int a,int b){return min(a,b);};
    auto g=[](int a,int b){return min(a,b);};
    auto p=[](int a,int b){return a;};
    LazySegTree<int> ruq(n,f,g,g,p,INT_MAX,INT_MAX);
    REP(i,n){
        ruq.set(i,i-1);
    }
    ruq.build();
    REP(i,m){
        int l,r;
        cin>>l>>r;
        l--;r--;
        ruq.update(l,r,l-1);
    }
    vl dp(vec);
    REP(i,n){
        int k=ruq[i];
        if(k>=0){
            dp[i]+=dp[k];
        }
        if(i){
            chmax(dp[i],dp[i-1]);
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

JOI2018予選 参加記

はじめに

第18回情報オリンピックに参加しました.JOI自体には中1から出てるはずなので4回目です
これは参加記なので詳しい解法については解説を読んでください

準備

前日まで期末試験だったので無です.PCK本選以降コンテスト以外で何も解いていません.
前日のABCは9位だったので嬉しかったです

当日

コンテスト前

遊んでたら1時間切ってて,急いで昼食を取りました.
緊張する体質なので最近は大事そうなコンテストの前にラジオ体操をすることで緊張をほぐすようにしているんですが,時間がないのとそんなに緊張してなかったのでしませんでした.

本番

  • tweetdeckを閉じて問題を開きました.
  • A問題を読みました
  • 簡単なので一行書いて提出しました
  • †WA† (13:01:09)
  • なんかよくわからないのでループを回します
  • そういえばボーナスが入るのは日曜のあとだね~みたいなこと考えながら提出しました
  • AC (13:03:57)
  • B問題を読みました
  • またすごろくをしてて悲しい気持ちになりました(去年Bに10分くらい苦戦した人
  • 問題を読み終わったので提出しました
  • AC (13:07:57)
  • C問題を読みました
  • 問題は読み終わってませんが実装が終わったので提出しました
  • AC (13:10:02)
  • D問題を読みました
  • どう見てもDPじゃなくて笑いました
  • 絵を書いたらわかったので実装して提出しました
  • †WA† (13:20:46)
  • コーナーっぽい落ち方をしているなぁって考えてたら高さ0の存在に気づきました
  • 直して提出
  • AC (13:25:02)
  • 30分経ってないのに4完してしまったので休憩をしました.妹が焼いたクッキーが美味しかった
  • E問題を読みました
  • 問題文にDPをしてくださいと書いてあるので読み終わると同時に自然な2乗DPが見えます
  • これで70点もくれるのかと思いながら考えていると貰うDPにすればセグ木で取れると思ったので書きます
  • どこから取ってくればいいのか考える必要がある気がしたんですが,これもセグ木で解決できるような気がするのではい
  • 数週間前にPCをリフレッシュしてからスニペットが消滅していることに気づきました
  • 遅延セグ木を空で書けないのでうだうだ言いながら平方分割を書いて投げました
  • 卍TLE卍 (14:05:54)
  • 落ち着いて考えるとDPの部分はセグ木じゃなくて累積maxでいいことがわかりました
  • 卍TLE卍 (14:13:16)
  • 諦めて遅延セグ木を書くことに(575)
  • 書かなくてもAOJの自分のソースをパクってくればいいことに気づきペタリ
  • AC (14:22:39)
  • ボーダーが400超えになることを確信してFを読みます
  • 何もわからない
  • とりあえずnext_permutationだけで取れる6点を取る
  • RE(6点) (14:37:00)
  • 20点は面倒なbitDPでできそうとは思ったけど,満点は何も見えないしボーダー520も考えづらいので20点を目指すモチベが生まれず撤退

結果

5完506点
得点単調増加は守れた(前年434点)が,Eまでは明らかに易化してるのでなんとも言えない感じ.通ったらがんばります

ARC103 参加記

C問題 /\/\/\/

問題文

C - /\/\/\/

解法

偶数番目と奇数番目について何に統一するか決めればよくて,かぶってはいけないことに気をつけるとできる.
実装が難しいがmapを配列にしてソートしてforで回した.一致判定はifよりforのほうが書きやすいと思う.添字ミスって1ペナ(Cでペナ出すの何週連続だ

E問題 Tr/ee

D問題が読解大変そう&&ひらきちさんが既に解いてたのでとりあえず問題を読むとシンプルだったのでこっちから解いた

問題文

E - Tr/ee

解法

実験してみる.
まず,n個の連結成分が作れなくて1個は必ず作れるのは明らか.
また,n個の木からk個が作れるとき,n-k個も作れる.また作れないときも同様に対称性があることがわかる.
よって,最後の一要素を覗いたn-1個は回文になっていないと作れないということがわかる.回文ならすべて作れるのかを考えたい.

競プロで出される構築問題は,基本的に何らかのアルゴリズムに沿って解けるので,実験するときもそのことを意識してやる.
木なので前の要素にくっつけていくようにして生み出す方針にすると,次のことがわかる
f:id:SugarDragon5:20180929235752p:plain
これを繰り返していくといい感じにできそうでは?ってなって,実際できる(図書くのだるいので省略
結構バグるがAC.

D問題 Robot Arms

問題文

D - Robot Arms

解法

部分点はdを1だけでできそうなのでやるがWA.そのままコンテスト終了.
バグはしょうもなかったのではい.
満点は2べきにするんだと思う(まだ解いてない

結果

f:id:SugarDragon5:20180930000148p:plain
パフォーマンスは1861,レートは1668->1689(+21 highest)

PCK2018予選 参加記

JOI本もSuperConも書くぞって言って後回しにしてたら忘れたので早いところ書いてしまおう.
ぼく(@Sugar_Dragon5)と弊部会長の二人でチーム「こんぺいとう」として参加.

事前準備

  • 相方に「出ようぜ」ってお願いする
  • 「隣でスマブラしててもいいなら出るよ」と言われたので申し込む(もちろんさせるつもりはない
  • 3日前くらいに初めて二人でバチャをするがボーダー寸前でバグらせて予選落ち.なえる
  • 前日にライブラリを印刷

当日

  • 朝起きる
  • 飯食べる
  • 電車に乗る
  • 1限を聞き流す
  • 2限を真面目に聞く
  • 3,4限は真面目に聞くも何言ってるかよくわかんなくてつらい
  • 飯は時間がないのでコンビニ
  • 辛いラーメン買ったら辛くて辛い
  • 部室のデスクトップPCで出る予定だったが開始3分前くらいにPCが不調に
  • 急遽僕のPCで出ることに
  • 準備してたら始まったのでそのまま1問目を解く
  • 慎重に確認してから提出してAC
  • 問題を印刷
  • 相方に続きを解いてもらいながら5問目くらいを読む
  • 何もわからん
  • 相方が2問目3問目をAC
  • 5問目何もわからんので相方を手伝う
  • 4問目相方が読んでる途中に見えるので書く
  • WA
  • なにかに気づいて出し直す
  • WA(大戦犯)
  • 片方固定とかアホくさくなったので愚直に100回くらい回す
  • AC
  • 気を取り直して5問目へ
  • やるをやればできそうだがスマートな解法がないか模索
  • 相方が愚直でいいっていうので実装したら確かに実装めっちゃ軽かった
  • AC
  • 相方から6問目の概要を聞く
  • ちょっと難しそうなので真面目に考察する
  • どうせswapするところだけ確認したいので,sortedとの差が何個あるか数えておけば良さそう
  • 書いたら通る
  • 7問目を読む
  • 読み終わったので実装を始める(6よりやるだけ
  • バグる
  • 直ったので提出
  • 通る
  • 8問目の概要とそれっぽい貪欲らしきものを聞く
  • あー後ろからpriority_queueねってなる
  • 書く
  • WA
  • オーバーフローやんけ(unsignedなら通りますよって何なんだこちとら桁数しか数えとらんわ
  • AC
  • 9問目の概要を聞く
  • 幾何やったことないので飛ばす
  • 10問目を聞く
  • どーせ木dp
  • これ全方位木dpってやつだろ書いたことないわ
  • 11問目を聞く
  • よくわからないので幾何をする決意をした
  • 9問目のお絵かきをすると1点固定傾き全探索をmapでえいが思いつく
  • 誤差こえ~~
  • 分数かくか~~ってなる
  • pairをgcdで割る関数書くだけでいいので楽ちん
  • 書けたので投げる
  • AC
  • この時点でなんか順位表のめちゃくちゃいい位置に居た
  • 4のペナが痛いな~~って話をしながら次を考える
  • 10は多分知らないやつなので11を頑張ることにする
  • そのへんに落ちてる丸いものを回してみると相方がなんか思いついた
  • 遅延セグ木でえいえいってすると良さそうな気がする
  • 具体的に何すればいいかよくわからんから詰めていくが集中が切れてきてて頭がまわらない
  • 気づいたら順位表が凍結された.6位タイ
  • 半ばお祈りフェーズに入る
  • とりあえずセグ木を写して,相方に考察を続けてもらう
  • セグ木ライブラリ,コピペ用だから写すのだるい(短いやつ作っとこう)
  • これ間に合わないなって確信してギブアップ
  • 持ち込み資料であるところの邪神ちゃんドロップキックを読んでいたらコンテスト終了

結果

9完3WAで凍結時点6位タイ(時間考慮で8位)
某氏のツイートによると判明しているだけでも2チームに抜かれているので,あと1チーム抜かれてたら負け
4問目の2ペナがあまりにも大きかった.反省
ただ青と緑のペアにしては善戦できたんじゃないでしょうか

追記(2018/09/23)

10位で順位枠で予選通過してました.本選よろしくおねがいします

AtCoder Beginner Contest 109 参加記

宣言されてたとおりの簡単回

A問題 ABC333

問題

A - ABC333

解法

やる

B問題 Shiritori

問題

B - Shiritori

解法

やる.被りがあるかどうか調べるのに無思考でsetを書いたが二次元forを回したほうが僕のタイピング速度だと明らかに実装早いので反省(まあ誤差だが
追記:setのコンストラクタにvectorイテレータ渡すやつ使うともっとシンプルにかける。

C問題 Skip

問題

C - Skip

解法

距離の約数じゃなきゃいけないのでgcd

D問題 Make Them Even

解法

操作列を求められてる時点で最大値はめっちゃ簡単に求まりそうで,実際いい感じにやると奇数は1つ以下にできそうだとわかる.
どうすればいいかを考えるととりあえずその場しのぎで偶数にしていく感じの操作が思いつき,実際これを書くとうまくできてるのでおわり

結果

f:id:SugarDragon5:20180908225708p:plain
15分14秒全完12位.タイムも順位も自己ベストだし,初めての1ページ目なので嬉しい.
Dを最初に解く遊びをしたが,Dが解けた頃には皆ABCは解き終わってるし,1位に至ってはすでに全完してたりするので精神的にとっても良くない.だめ

AtCoder Regular Contest 102 参加記

今回僕が解けたCとDは解法を言われるとそれはそうとなるので,ACまでの試行錯誤を書いておく

C問題 Triangular Relationship

考察

  • よくわからんけど愚直はもちろんTLE.O(N\log N)までしかだめ
  • 1つ決めると他2つが決まるとか?
  • そういう訳ではなさそう…?
  • 数えたいものの特徴は?
  • \bmod kが同じやつ同士っぽい
  • ただ何でもいいわけじゃなくて,2倍してmod k取ると0になるやつだけ
  • mod決めちゃえばそれの個数は求まるし,重複OKなので3乗するだけ
  • 実装(こんがらがってて1WAした)

むずかしかった

解法

2x\equiv 0\pmod Kとなるすべてのxについて,[1,N]に何個存在するか求めその3乗を答えに足す.

D問題 All Your Paths are Different Lengths

考察

  • とりあえず実験
  • 適当に辺を足していってもある程度作れそうだけど,頂点と辺の制約的に賢いことしないとダメそう
  • 無駄な枝分かれは意味がないので基本は1本道にしたい.
  • 多重辺
  • 2進数とか良くね????
  • 実験するとL=2^nn+1頂点と2(N-1)辺で表現できる

f:id:SugarDragon5:20180901234759j:plain

  • このままだと2の累乗しか表現できないし最大で21頂点必要になってダメそう
  • n頂点でL=2^nできないの?
  • できた

f:id:SugarDragon5:20180901235151j:plain

  • 1つ頂点が減らせた.2進数で考える+αのこの方針で20頂点に収めることは可能そうだし,もう少し考察してみよう
  • 2の累乗以外を表現できるように辺を足す方法を考える
  • とりあえず2個目のやつよくわからんし1個目のやついじろう
  • Lを2進数で見たときに1の桁に対して操作が必要
  • 辺の制約的に追加できるのは各桁1本
  • それぞれの操作で増やしたいパスの個数を満たすところはどこだ
  • 桁の回数行ったところから辺を引くと欲しい数だけ増えそう
  • 他に影響してほしくないのでゴールに直接つなごう
  • 重みはいい感じの数が出るようにしてみる
  • できた

f:id:SugarDragon5:20180902000514j:plain

  • 頂点数[\log_{2}L]+1で表現できた
  • 2^{20}未満なので20個でできそう
  • うまくいきそうなので実装する(きびしい)
  • AC

解法

[\log_{2}L]+1点の2進グラフ(画像1枚目のやつ)に適切な辺を適切な数値で足していく

結果

f:id:SugarDragon5:20180902001054p:plain
71分2完1ペナで201位
f:id:SugarDragon5:20180902001156p:plain
まあまず水色に落ちないところ(パフォ663で水)まで上がったので嬉しい.
2回連続で700を通せたのが良かった.