読者です 読者をやめる 読者になる 読者になる

迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

平方分割とみんプロ本選C

平方分割

蟻本を読んでいて、遅延セグ木や平方分割のところで止まっていたのでやった
平方分割の部分は枠組みとなる部分がちゃんと書かれていなくて読み解けなかったので別のサイトを読んだ。
ただ他人のコードを読む力がないだけなんですけどね

みんなのプロコン本選C問題

本番はオープンコンテストにでてたんですが、Bの貪欲部分がO(N2)になっててダメだった
Cもみましたがデータ構造で殴るやつだと察してBやってた
終了後にCは平方分割だとか†clangのベクトル化†みたいなのを見たので平方分割の練習としてときました

これはどうでもいいんですが、テンプレートとして色々なデータ構造をclassとして実装しようと思ってるので平方分割もしました
一応処理はみんプロC用に変えてます
他の人のコードみたら平方分割はこんなことしてる人がほぼいなくて悲しくなった
速度もめっちゃ遅かったです
範囲更新なので伝播必要だと思ってevalありますが、使いませんでした
セグメント木をあきらめた人のための平方分割を完全に参考にしました
ありがとうございます!
おりさの先輩に教えてもらった方法は範囲加算時ははみ出した部分lazyの更新が面倒くさくないか…と思い使わなかったのですが(すいません) 今回の問題では更新しないのでそっちの方が確実に楽だったことに気づきました
解いてからようやく分かるプロの技でしたね、すいませんでした

class Bucket{
private:
    int n, bs, bn; // 要素数、バケットサイズ、バケットの数
    int m;
    vector<ll> data;
    vector<ll> lazy;
    vector<bool> lazyFlag;
    vector<vector<int> > bucket;
public:
    Bucket(vector<ll> v, int sz, int M){
        data = v; m = M;
        n = v.size();
        bs = sz;
        bn = (n + bs - 1) / bs;
        data.resize(bn*bs, INF_LL);
        lazy.assign(bn, 0);
        lazyFlag.assign(bn, 0);
        bucket = vector< vector<int> >(bn, vector<int>(m, 0));
        REP(i, bn){
            REP(j, bs){
                bucket[i][data[i*bs+j]%m]++;
            }
        }
    }

    void eval(int k){
        if(lazyFlag[k]){
            lazyFlag[k] = false;
            FOR(i, bs*k, bs*(k+1)){
                data[i] = lazy[k];
            }
            lazy[k] = 0;
        }
    }

    void update(int s, int t, int x){
        REP(k, bn){
            int l = k*bs, r = (k+1)*bs;
            if(r <= s || t <= l) continue;
            if(s <= l && r <= t){
                lazyFlag[k] = true;
                lazy[k] = (lazy[k]+x)%m;
            }else{
                FOR(i, max(s, l), min(t, r)){
                    bucket[k][data[i]%m]--;
                    data[i] += x;
                    bucket[k][data[i]%m]++;
                }
            }
        }
    }

    ll query(int s, int t, int d){
        ll res = 0;
        REP(k, bn){
            int l = k*bs, r = (k+1)*bs;
            if(r <= s || t <= l) continue;
            if(s <= l && r <= t){
                res += bucket[k][(m-(lazy[k]%m))%m];
            }else{
                FOR(i, max(s, l), min(t, r)){
                    if((data[i]+lazy[k])%m == 0)
                        res++;
                }
            }
        }
        return res;
    }

};

それぞれのバケットごとに、Mで割った余りがある数である要素がいくつあるかそれぞれ持っておきます。
バケット全体にたされたらlazyに、中途半端なら要素だけに加算
要素に加算した場合はそのバケットでの加算前%Mを1引いて加算後%Mを1足してます。
そしたらなんかやるだけ(終了)

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, Q;
    vector<ll> a;
    cin >> N >> M >> Q;
    REP(i, N){
        int A;
        cin >> A; a.push_back(A);
    }
    Bucket bc(a, sqrt(N), M);
    REP(i, Q){
        int l, r, d;
        cin >> l >> r >> d;
        bc.update(l-1, r, d);
        cout << bc.query(l-1, r, d) << endl;
    }
}

こんな感じです
精進の結果NieR:Automata1周目終わったので2周目も精進していきます。
投稿時にはEエンドまで終わりました。データは消さなかったのでエミール頑張ります

Codeforces #402 (Div.2)

Codeforces Round #402 (Div. 2)

Codeforces#402に出たので、なんとなく眠気もないしつける
最近レートが下がってばっかで悲しみ界のtouristになってたんですが、またさがったのでもうダメ
とりあえず前回のコドフォでYESとYesを間違えたり、JOI本選でllにし忘れたりとかそういうの多いのだめ

ちゃんと精進して地力付けていこうな👊

A問題

なんか2つの数列が与えられるからスワップして各数字が含まれる数を等しくしなさいみたいな
スワップ回数の最小値を求めなさい、等しく出来なければ-1を出力
等しく出来ないのは自明で全体である数字が奇数個しかなかったとき
等しくできるときは、その数字がある個数/2-数列Aにある個数の絶対値をそれぞれの数字でやる
そして半分にすればOK

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    int a[114], b[114], numA[5] = {}, numB[5] = {}, num[5] = {};
    int res = 0;
    cin >> N;
    REP(i, N){
        cin >> a[i];
        numA[a[i]-1]++;
        num[a[i]-1]++;
    }
    REP(i, N){
        cin >> b[i];
        numB[b[i]-1]++;
        num[b[i]-1]++;
    }
    REP(i, 5){
        if(num[i] % 2 != 0){
            cout << -1 << endl;
            return 0;
        }
    }
    REP(i, 5){
        res += abs(num[i]/2-numA[i]);
    }
    cout << res/2 << endl;
}

B問題

正の整数Nから好きなだけ桁を取り除いて10kで割り切れるようにしなさい
下から貪欲
もしも0の個数が足りなければ0にするためにNの桁数-1が答えになる
絶対に0は存在するからね(答えが必ず存在するため)

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string num;
    int k;
    cin >> num >> k;
    int zero = 0;
    reverse(all(num));
    REP(i, num.size()){
        if(num[i] == '0')
            zero++;
        if(zero >= k){
            cout << i+1-zero << endl;
            return 0;
        }
    }
    if(zero < k){
        cout << num.size()-1 << endl;
    }
    return 0;
}

C問題

セールしてるよ、セール中にk個は少なくとも買ってね
セール後の方がやすくなってる商品もあるからそっちで買ってもいいよ
できるだけ総額を安くしてくれ

セール中とセール後の差でソートして貪欲
a[i]-b[i]をfirstにしたpairでやるとうまくいくはず
実装は汚い

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    int a[214514], b[214514], dif[214514];
    PII pd[214514];
    ll res = 0;
    cin >> n >> k;
    REP(i, n){
        cin >> a[i];
    }
    REP(i, n){
        cin >> b[i];
        dif[i] = a[i]-b[i];
        pd[i] = {dif[i], i};
    }
    int buy = 0;
    sort(pd, pd+n);
    while(pd[buy].first <= 0 && buy < n){
        res += a[pd[buy].second];
        buy++;
    }
    while(buy < k){
        res += a[pd[buy].second];
        buy++;
    }
    FOR(i, buy, n){
        res += b[pd[i].second];
        
    }
    cout << res << endl;
}

D問題

C問題を解くまでにかかったのが21分でそこから空白の1時間40分を過ごし死んだ
ここまで最高の流れでC問題解き終わった時点では2桁位だったのにな…

f:id:pazzle1230:20170226215213p:plain

文字列TとPがあります。Tから与えられる順番で文字を消していくけど、いくつまでなら消してもPを部分列として含んでいるでしょう

ずっと部分列として含むか判定の高速化を考えてたけど実際はいくつとるかの試行を減らす方向だった
もっと頭を柔軟にできるようにしたい…
にぶたんだった
あたまをなーやわらかくなーできたらなー
部分列として含むかがO(|T|)でできるから全体でO(|T| log |T|)かな?
これからは最大化最小化を見たらすぐにぶたんに結びつけてやるぞ(死亡の音)

実装では消すのではなく逆順にして使える文字を増やしていった(なんか楽そうに見えたから)

string t, p;
vector<int> a;
bool canuse[214514] = {};

bool ok(int tm){
    memset(canuse, 0, sizeof canuse);
    REP(i, tm){
        canuse[a[i]] = true;
    }
    int in = 0;
    REP(i, p.size()){
        while(in < t.size() && (!canuse[in] || t[in] != p[i])) in++;
        if(in == t.size()){
            return false;
        }
        in++;
    }
    return true;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t >> p;
    REP(i, t.size()){
        int A; cin >> A; A--;
        a.push_back(A);
    }
    reverse(all(a));
    int l = 0, r = t.size();
    while(r-l > 1){
        int m = (l+r)/2;
        if(ok(m)){
            r = m;
        }else{
            l = m;
        }
    }
    cout << t.size()-(l+r)/2-1 << endl;
}

もっと精進して解法レパートリー増やそうな

JOI2016/2017本選参加したよ

JOI2016/2017本選

JOIの予選をうまく通れてしまったので、ボーダーぎりぎりで怖いながらも本選に参加してきました。
なんか参加記的なやつです。

1日目

秋葉原で合流してお昼食べよ♥
みたいな感じの流れができあがってたのでプロの提案のもとロイホに向かった
なんかすでに4人ぐらいいたけど✝プロの風格✝みたいなものを出していたので怖かった
座席をUnionFindさせる一般的なテクを使えるプロ店員がいた

TXにのるよ

プロたちが精進してて怖い中テスト勉強してました
おそらくここがコーナーであり、差をつけられたんだと思います

のりました

なんか会場がガラス張りですごかった
プラクティスは全部JOI過去問に合った気がして全完できてうれしかった
もやし先輩がアレでアレだったのでアレだったけどACできててすごーい!

講演会的なものがありました、ちなみに僕は一番前の席に座ってたのですがほぼ寝てました
機械学習とかに興味があったはずなのにおかしいですね

立食パーティーは微妙なコミュ障を発揮することで話にあまり参加しないテクを使った
あっ、これは自己紹介でも言ったんですが最近Twitterをはじめました!
IDはぱずる1230で作ろうとしたのですがすでに存在したのでエルを大文字のアイにしました!
よろしくおねがいします!スペルとかまちがえないようにしてください!

宿舎は独房だった
部屋にはいると光もなくただ闇に包まれていた
スイッチを押し、明かりをつけるとだいたい(ここにはN畳みたいな言葉が入りますが常識がないためわかりません)ぐらいの広さで
ベッドはなんかアレで机はなんかもうアレだった
TsuzuさんとAzさんとあなたのコンビニに買い出しに行った
よっちゃんイカを買ったけど僕はタラタラしてんじゃねーよのつもりで買ったので酸っぱさに耐えてた

ABC全完レース的なのが始まり、こたまねぎさんと丼土さんが普通に全完していってプロみを感じた
僕はわからずひるどだったけどDPって聴いて本選死亡の雰囲気が出始める
この時裏ではけものフレンズが上映されてましたが、あまり集中できず、プロたちがふれんずー!って合唱していたのしか覚えてません

2日目

朝起きてエントランスに向かうと、数人が精進していた
僕はスマホしか持ってなかったのでDeemoでEntranceのフルコンを頑張ったけど無理だった、キレそう

朝ごはんですが、なんとか全問挑戦して全完できたのでよかった、鮭は水で殴った

適当に片付けをして下に降りると着物フレンズが上映されてた
一般にIQを溶かすと言われているけものフレンズだけど、真剣に見ていた人は基本的に本選通過しているっぽそうなので、おそらくIQを上げるアニメ

本選会場
なぜか緊張しない、この時は割りと緊張しないことがうれしかったけど、今思うと眠くて現状を把握できてないだけだった

本選開始
一問目を読む、どう考えてもDPじゃない
imosか?→いや違う→区間加算で殴るか?→どっちにしろ毎回O(N)かかりそう→適当にdiffとっとこw(ハム太郎だからね)
ここまで来るのに1時間かかった
この時点である程度絶望してたけどとりあえず実装する
この後も、一回diffが0になるように温度を変更した後に正しいdiffに直せば更新できることに気づくのに時間がかかる
実装する→WA
3分の1ぐらいはACしているように見えたので、絶望の夜明けって感じだった
ここでデバッグしまくるがどう考えても間違ってない
2時間経過ぐらいで愚直で部分点取ろうとする→WA

>愚直で間違ってるはずがない<

ここまで考えてもわからないってことは更新の式が間違ってるんだなと思って2問目を見る(もし間違ってたら3分の1ぐらいがACするわけがない)
どうせDPだろ!wって思いながら読む
それぞれの急行停車駅ごとに分けてDPすれば行けそう→なんか試行錯誤しまくってサンプルは通るようになるが残りは通らないバグが発生
諦める
この時点で絶望しまくってるので諦めて3問目を読む→解けない

お疲れ様でした!迷路先生の次回作にご期待下さい!!

0点でした、最高ですね、1問目のバグのコナンズヒントは32bit整数です。泣きたくなりました
自分の真の実力を示すことが出来たと思うのでよかった

この後に蒙古タンメンにizryt氏と行っておいしー!ってなって帰宅しました
来年もこの記事を使いまわせるような事態にならないようにしたいです
がんばります

AOJ520 最軽量のモビール

最軽量のモビール

本日2つ目のACなんですが、とくのに時間がかかった自分にキレそうなためブログにします。


コレなんですが、問題の概要としては

木が与えられます。
それぞれの節点には重さw、2つの整数a,bが含まれています。
2つの子の重さをそれぞれw_1, w_2としたときw_1 \times a = w_2 \times bとなるようにします。
w = w_1 + w_2
根の重さを求めましょう

まともにまとめられていませんが、まあ問題を自分で読めって感じです(は?)
最初は、 w_1 \times a = w_2 \times bを満たすにはwはa+bの倍数であるはずということがわかったため,wをa+bの倍数とする
そしたらw_1w_2もわかります。そしたらw_1,w_2の子の重さもわかります。...とすすめていき
どこかで整数では無くなったらそのwでは成り立たない。
もしすべてが整数で成り立った場合はそのwが最小ということになるのでうぇいってやったらTLEでした。
そもそもなぜか途中から答えが合わなくなってたので今度は方針を変えます

w1とw2を仮に定めていた場合、wも仮で定まるのでは無いか?となってもちろん定まります。
なので下から決めていけば根の重さも決められることがわかりますね
ほんとか?って今書きながら思ってますが通ってたのでそうなのでしょう
ここで、葉は重さ1とします。

\displaystyle w_1 = \frac{LCM(w_1 \times a, w_2 \times b)}{a}
\displaystyle w_2 = \frac{LCM(w_1 \times a, w_2 \times b)}{b}
\displaystyle w = w_1 + w_2

これで更新していくことが出来ます。
なんで思いついたんでしょうね
今の僕は正当性がよくわからないです
他の人の解説見てきたいと思います

struct stick{
    int l_d, r_d;
    int par, l, r;
};

stick s[101];

ll gcd(ll x, ll y){
    if(y == 0) return x;
    return gcd(y, x%y);
}

ll dfs(ll st){
    if(st == 0) return 1;
    ll l_w = dfs(s[st].l);
    ll r_w = dfs(s[st].r);
    ll res = (l_w*r_w*s[st].l_d*s[st].r_d)/gcd(l_w*s[st].l_d, r_w*s[st].r_d);
    res = res/s[st].l_d + res/s[st].r_d;
    return res;
}

int main(void){
    int n;

    while(cin >> n && n){
        memset(s, 0, sizeof s);
        FOR(i, 1, n+1){
            s[i].par = i;
        }
        FOR(i, 1, n+1){
            int a;
            cin >> s[i].l_d >> s[i].r_d >> s[i].l >> s[i].r;
            a = gcd(s[i].l_d, s[i].r_d);
            s[i].l_d /= a; s[s[i].l].par = i;
            s[i].r_d /= a; s[s[i].r].par = i;
        }
        int start = 1;
        while(s[start].par != start){
            start = s[start].par;
        }
        cout << dfs(start) << endl;
    }
}

最悪の記者

JOI本選にでることになったので非公式難易度表を埋めてるのですが、難易度7以降は考察してもなかなか解けなくてつらいです
最悪の記者解いたし、トポロジカルソート詳しく知らなかったのでせっかくだしブログ書きます。

最悪の記者

僕の考察:めんどくさい系っぽい→適当なアレでソートすればいけるのでは?→勝ちから負けに有向辺繋げばワンチャン→やっぱソートか→>無理<

解法:トポロジカルソート!!!!!!

なんか惜しいところまでいってた感あって悔しいですが、よく知らなかったので学びですね。
問題としてはトポロジカルソートして、解の一意性があるか判定すればいいっぽい。
判定は、1位→2位、2位→3位、...、n−1位→n位に辺が通ってれば解は一つらしいのでそれで判定
ソート部分はDFSがわかりやすかったのでDFSで書きました。
ヴィジュアライズされてるサイトが合ってそれで理解が深まった
「topological sort」をGoogleで検索したら出てくるけど色々なのがヴィジュアライズされてて良さそう

vector<int> G[5005];
vector<int> standings;
bool used[5005] = {};
int kind = 0;

void visit(int v){
    if(used[v]) return;
    used[v] = 1;
    int cnt = 0;
    REP(i, G[v].size()){
        visit(G[v][i]);
        cnt++;
    }
    if(cnt > 1)
        kind++;
    standings.push_back(v);
}

int main(void){
    int n, m;
    cin >> n >> m;
    REP(i, m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
    }
    REP(i, n){
        visit(i);
    }
    reverse(all(standings));
    REP(i, n){
        cout << standings[i]+1 << endl;
    }
    REP(i, n-1){
        bool there = true;
        REP(j, G[standings[i]].size()){
            if(G[standings[i]][j] == standings[i+1])
                there = false;
        }
        if(there){
            cout << 1 << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}

JOI2016/2017予選参加しました

JOI予選参加しました

心にとてつもないダメージを負ったため、一日遅れての投稿です。
おそらく380点取れてると思われます。
提出ミスしている可能性は考えていません。
してたら即死ですし、してなくてもおそらく死んでます。
私的な感想としては、JOI予選過去問の問題4まで解ければあとは部分点でいけると思っていて、
JOI非公式難易度表で難易度5を1,2週間前から埋め始めたんですがあれは何だったんだと、
どう考えても難易度5の問題が一つもなかったぞと

とりあえず一問ずつ適当にどうやったかです。

1問目

やるだけ

って言いたかったんですが、b<0のパターンを考えてしまったり、
0℃のときは凍ってる場合と凍ってない場合がある、の意味も悩んでしまったり
1問目の出力まで終わって提出するだけになったときに予選用につくったディレクトリをrmしてしまったり
そんなこんなで10分ぐらいかかってました
2問目より難しかったです

2問目

やるだけ

ソートしてうぇいでうぇい

3問目

ほぼやるだけ

縦に設置する場合と横に設置する場合を考えて、始点を(0, 0)〜(H-1, W-1)で数え上げただけ
だけどここまでで30分ぐらいかかってました
他のプロたちが10分とか15分とかで終わらせてる中でこれは辛かった

4問目

ここでキレかけた
てかキレました
完全にDPという決めつけで問題文読んだので、普通に最初は意味がわかりませんでした
そして焦ってDP以外を考えて、でも無理だってなって
つらい

それから一応bitDPでありそうだなって気づき
dp[M][1 << M]としてがんばったけどテストケース5は間に合いませんでした。

累積和をDPに活用するという発想があれば変わったかもしれないけど、
遅い原因がそこの数える部分とは思ってなかったのでダメだと思います
普通にコードも汚い

int main(void){
    int N, M;
    vector<int> shelf;
    int num[20];
    fill(num, num+20, 0);
    cin >> N >> M;
    vector< vector<int> > dp(M, vector<int>(1 << M, INF));
    REP(i, N){
        int a;
        cin >> a;
        num[a-1]++;
        shelf.push_back(a);
    }
    REP(i, M){
        dp[0][1 << i] = diff(shelf, 0, num[i], i+1);
    }
    FOR(i, 1, M){
        REP(j, 1 << M){
            bool used[20];
            int use_num = 0;
            int sum = 0;
            fill(used, used+20, false);
            REP(k, M){
                if(((1 << k) & j) == (1 << k)){
                    used[k] = true;
                    use_num++;
                    sum += num[k];
                }
            }
            if(use_num != i+1) continue;

            REP(k, M){
                if(!used[k]) continue;

                dp[i][j] = min(dp[i][j], dp[i-1][j ^ (1 << k)] + diff(shelf, sum-num[k], num[k], k+1));
            }
        }
    }
    cout << dp[M-1][(1 << M) - 1] << endl;
    return 0;
}

5問目

全マスからBFSでmapに入れてsize()が2以上ってやったらテストケース1が間に合ったにも関わらずWAった
死にそう
小さい方から数えて工夫してれば行けたらしくて辛い

6問目

すでに時間が30分ぐらいしか残ってない
とりあえず観るだけと思ってみて、誤読して唯のダイクストラ書いて無理で終了
必要な情報をどうにか持てばいけそうだとは思ったけどどう持つべきかわからなかった

来年があるので滅入らずにやっていきたいと思います

板チョコ分割

テスト勉強始めようと思ったら競プロ問題の案が浮かんだので作ってみました

w * h個のマス目になっている板チョコがあります。
口小非力君は、この板チョコを食べようと思ったのですが、彼は一マスずつに板チョコが分かれていないと食べられません。
さらに、力が弱いので長い方の辺が短くなるようにしか割ることが出来ません。
正方形の場合は一列だけ切り離すように折ることが出来ます。
できるだけ少ない回数で板チョコを分けたとき、何回割る必要があるかを求めてください。

例えば3×2の板チョコのとき、3×1の板チョコ2つに分けることは出来ず、
この場合には1×2と2×2の板チョコに分けることしか出来ません。
こう続けていくと、結果的に5回の分ける作業で1マスずつにすることが出来ます。

考えてください(案を思いついたときはワンチャンある気がしたけど何もなかった)
唯の失敗です。
問題作成の大変さを思い知らされた