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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

segment_tree

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e16;
typedef LL A;
typedef LL B;
typedef LL C;
struct node{
    A a;
    int flag;
    B b;
    C c;
};
#define isB (1<<0)
#define isC (1<<1)
A mg(node& v,int l,int r){
    if(v.flag&isB)return v.b+v.c;
    else return v.a+v.c;
}
A mg(A l,A r){
    return max(l,r);
}
namespace ST{
    node mem[1][2123456];
    int cnt=0;
    node* get(){return mem[cnt++];}
}
struct seg_tree{
    int size;
    node *seg;
    void init(int l,int r,int k=0){
        auto &v=seg[k];
        //flag関連の処理
        v.flag=0;
        v.b=-INF;
        v.c=0;

        if(r-l==1){
            //葉の時の処理
            v.a=-INF;
        }
        else if(r-l>1){
            int m=(l+r)/2;
            init(l,m,k*2+1);init(m,r,k*2+2);
            v.a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        }
    }
    seg_tree(int n){
        size=1;
        while(size<n)size*=2;
        seg=ST::get();
        init(0,size);
    }
    inline void push(int k,int l,int r){
        if(r-l<=1)return;
        auto &v=seg[k];
        auto &lg=seg[2*k+1];
        auto &rg=seg[2*k+2];
        if(v.flag&isB){
            lg.flag=isB;lg.b=v.b;
            rg.flag=isB;rg.b=v.b;
        }
        if(v.flag&isC){
            lg.flag|=isC;lg.c+=v.c;
            rg.flag|=isC;rg.c+=v.c;
            v.c=0;
        }
        v.flag=0;
    }
#define LQ a,b,k*2+1,l,m
#define RQ a,b,k*2+2,m,r
    A get(int a,int b,int k,int l,int r){
        if(a<=l&&r<=b)return mg(seg[k],l,r);
        push(k,l,r);          
        int m=(l+r)/2;
        bool ll=!(m<=a||b<=l);
        bool rr=!(r<=a||b<=m);
        A ret;
        if(ll&&rr)ret=mg(get(LQ),get(RQ));
        else if(ll)ret=get(LQ);
        else ret=get(RQ);
        seg[k].a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        return ret;
    }
    A get(int a,int b){return get(a,b,0,0,size);}
    void update(int a,int b,int k,int l,int r,node v){
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            if(v.flag==isB){
                seg[k].flag=isB;
                seg[k].b=v.b;
                seg[k].c=0;
            }
            if(v.flag==isC){
                seg[k].flag|=isC;
                seg[k].c+=v.c;
            }
        }
        else{
            push(k,l,r);           
            int m=(l+r)/2;
            update(LQ,v);
            update(RQ,v);
            seg[k].a=mg(mg(seg[k*2+1],l,m),mg(seg[k*2+2],m,r));
        }
    }
    void set(int a,int b,B val){
        node q;
        q.flag=isB;q.b=val;
        update(a,b,0,0,size,q);
    }
    void add(int a,int b,C val){
        node q;
        q.flag=isC;q.c=val;
        update(a,b,0,0,size,q);
    }
};

AOJ2594 Reverse a Road Ⅱ

AOJ

この問題好き

問題文

Reverse a Road II | Aizu Online Judge

久々に訳書きます
有向辺グラフとスタート,ゴールが与えられる.
スタートからゴールまで,道が一つも被らないルートが最大でいくつあるか求めたい(頂点は被ってもよい)
ただし,一つの辺だけ向きを逆にすることができる.
実現できるルート数の最大値と,そのルート数を実現できる逆にする辺の選び方が何通りあるかをそれぞれ答えよ.
ただし逆向きにしてもルートが増えない場合は元のグラフでの最大値と0を出力すること.

解法

まあどう見ても最大流系の解法で解く問題なんですが,
とりあえず変更無しのグラフにフローをめいっぱい流してみます.

向きを変更するのではなく,新たに流量1の辺をどこかに追加することを考えると,グラフ全体の流量は最大でも1しか増えないことが分かります.
つまり,既に流れている辺の向きを逆にすることは全く意味がないことがこのことから分かります.(1減らして1増えるだけなので)

ではあとは流れていない辺を逆向きにしてチェックするだけです.
なのですが,いちいち入れ替えて流れるか試していると間に合いません.

流量が増える条件について考えてみると,残余グラフ上でスタートからゴールまでの流量1以上のパスがあればよいです.
フローをめいっぱい流した状態だと増加パスが存在しないので,

  • スタートから流量1以上の辺をたどっていける頂点(A)
  • ゴールまで流量1以上の辺をたどっていける頂点(B)
  • どっちにもたどり着けない頂点

の3種類に分かれます.

ある辺について

  • (A)->(B)である
  • まだフローが流れていない

であれば向きを逆にすることでグラフ全体の流量を増加させることができます.


というわけで残余グラフ上でスタートとゴールからBFSをして各辺を調べてやればACできます.

JAG夏合宿 2016 day4

ICPC

夏合宿の4日目のアレです.
この日はKlab様に会場提供していただき,六本木ヒルズの中でコンテストに参加するという貴重な体験をさせていただきました.

六本木ヒルズで綺麗な恰好のOLやキチっとしたサラリーマンの集団の中に大人数の競技プログラマーが突っ込んでいくのは色々思うところがありました.


さて,コンテストです.
この日はゆらふなさんとマヨ子さんとチームを組みました.

開始前

またしても誰のPCを使う問題に悩まされましたがこの日もマヨ子さんのPCを使うことに
Klabドリンクを補給して準備万端

コンテストの時間

かなり前なのでよく覚えていない()
ゆらふなさんから解けた問題を奪ったり,トイレの場所が分からなくてチームメイトに案内してもらったりしていました.

F問題が全ての頂点に対して,その頂点を含む最小の長さの閉路の長さを答えよという問題で面白かったです.
ダイクストラで最短経路木張ってグループ分けしてごにょるとできました.
あとはJ問題のDPをするときに使ったbitの保存(100bit)をLL二つかbitsetを使うかで悩んだのですが,マヨマヨも私もbitsetあまり使えないという理由でLLを採用したりしてました.

I問題は残りの時間がなかったのでマーチンゲール法(負けたら倍,勝ったら1に戻す)でやってて,
マヨマヨが「こんなん通ったら理不尽すぎる」とか嘆いてたのが印象的でした.(結局通らなかった(それはそう))

なんだかんだでかなりACを重ねることができて,最終的には全体7位ぐらいでかなりよかったです.

JAG夏合宿 2016 day3

ICPC

夏合宿の3日目のコンテストの時のアレです.
この日は模擬予選も兼ねていて,LINE様に提供していただいた会場でコンテストを行いました.
色々オフィスがすごかった.(こなみかん)

まよバタ+紺青さん(@konjo_p)の即席チームで参加しました.
実は紺青さんとは去年の夏合宿でもチームを組んだ(splas_boomelangのとき)
この3人は全員TCのレートが黄色で,日頃競い合っている人とチームを組めたのは私にとって大きな勉強となりました.

コンテスト開始前

この日はマヨ子さんのPCでやることになる.
...と思ったのですがAtomsublimeなどのエディタが色々vim仕様になってるらしく,デフォルトに戻すためバタバタする.

vimvimょい.

コンテスト開始

順位表を見ながらできるだけ問題を開けていく方針.
というわけで英文の短いDを譲ってもらう.
問題文は理解したけど解法は分からない...
ので問題文の短いEを読む.
プロ達はA,Bを通していく.

A,B AC

プロプロ
とりあえずDの内容だけ伝えてEを考えることにする.
木の同じ高さの頂点同士のマージ回数ならO(N)になるから愚直にやっていけると勘違いしてコードを書き始める.

E TLE

はい戦犯
原因が分からないのでDをやってもらいながら考え込む.
マヨ子さんはCを凄く書きたくなさそうにしていた.

D AC

はいプロ
紺青さんの手が空いたのでEの解法を相談する.
O(N^2)になっていることを指摘され,悲しい気持ちになる.
ロリハ解を提案され,やり方を確認しながら実装することにする.

E AC

本当にすみませんでした.
マヨ子さんがCを本当に辛そうにしていたのでデバッグを手伝いつつFを考える.
Fがひらめきそうでひらめかなくて本当につらい.
Gをちらっと読むと動的凸包で解けることが分かったけどそんなものは持ってきていないので捨てる
(実は動的無しでも解ける自明な解法があったので捨てたのは本当にミス

C AC

はいプロ.
なんとかFを閃いたので時間少ないけど頑張って実装することにする.

最小値RMQが必要になり,持参したsparse tableを実装する.
ライブラリを確認しながら実装していると,明らかにライブラリの間違っている部分を見つける 悲しい

F WA

デバッグタイム
怪しいところを修正して終了20秒前にラストサブミットをする

F WA

つらい.
落ちたケースを見てみると,sample3だけ落ちている.発狂した.

というわけでABCDEの5完で13位でした.
宿に帰ってからFをデバッグすると,RMQの取得区間が1間違っていただけなので本当に悲しい.

初めてのローリングハッシュなど,学ぶことの多いコンテストでした.

夏合宿は3日間とも効率化のため進捗表を上のように作っていたのですが,この日の私の仕事して無さがひどい

JAG夏合宿 2016 day2

ICPC

夏合宿2日目のコンテストのときの日記的なアレです

Japan Alumni Group Summer Camp 2016 Day 2 - Japan Alumni Group Summer Camp 2016 Day 2 | AtCoder

解説のときに聞いた話なのですが,このセットは欧州の結構やばい地区の過去問らしいです.

まよバター(@btk15049 + @mayoko_)+たわしさん(@nCk_cv)の3人で出場しました.

コンテスト前

即席チームを組むときは必ず直面するであろう誰のPCを使うか問題.
たわしさんがJava使いということでたわしさんのMacでやることになる.
エディタは確かSublimeを使ったような気がします(違うかもしれない)

普段英字配列を使っている上win機しか使わないのでタイピングにかなり苦しみました.

コンテスト開始

とりあえず適当にABCから一人一問ずつ読む.
私はC問題担当で,結構短い文を引いてラッキーだと思っていたが結構重要そうな単語が読めず苦しむ.
マヨ子さんが辞書を持っていたので借りたが,載っていなかったのでやむなくエスパーする.

とりあえずエスパーした結果C問題が簡単そうということが分かったので実装を始める.
その間に他の問題文を他の人に読んでもらうという割と理想の展開

C問題 TLE

ここから地獄が始まる.

このセットは全てのテストが複数テストケースとなっていたのですが,割と入力サイズに対してタイトにやらないといけないようにTLが設定されてるっぽいです.
で,私の提出したソースコードは毎ケース10^5回のループを回していて,TLEになっているようでした(このへんは流石にアレなので考慮してほしかった)

当時は原因が分からなかったので,D問題の考察を終えていたたわしさんに実装をパス.

D問題 TLE

D問題は少し実装が辛そうでした
マヨ子さんとたわしさんの二人で解いていたので私は詳細をあまり知らず.

D問題 AC

プロ
結局C問題を計6回TLEさせてしまいFXで有り金を溶かしてしまったような顔をしていました.
もしかしたら書く人を変えたら通るかもしれないとの予想の元マヨ子さんに一から書いてもらうことに.

C問題 AC

プロ.本当にすみませんでした.
H,I問題が解けていたので両方私が実装することに.

H問題 AC

Good Morning

I問題 WA

頭を抱える
冷静になるとブロックの個数が最小元の整数倍になってる必要があるので,それを実装する.

I問題 AC

この時点で
F わかったけど実装が無限に面倒くさそう
L なんか頑張ったら分かりそう
という感じでした.
PCが空いてしまったので,少し実装の方針を相談してFをマヨ子さんに実装してもらうことに.

ここから確か提出はしてないです.
ずっとFのデバッグをしながら他の問題を考えるなどをしていました.
L問題が辛くてA問題をちょっと考えた結果解法が分かったのですが実装時間が足り無さそうということで断念.
F問題は終了直前にバグの箇所が分かったけれど間に合わずという感じでした.


時間があればFが通せてたはずなのでCで戦犯をしてしまって本当に申し訳なかったです.

JAG夏合宿2016 参加記

ICPC

JAGの夏合宿に参加してきました!

今回は何故かICPCのチームメイトが参加できずぼっち参加になってしまったので,マヨ子プロにコンテスト一緒に参加する約束をして寄生する.

1日目

所用があって自己紹介フェーズには参加できなかったので懇親会から参加する.
肉やegg fireを食べて楽しい気分になったが,旅疲れが激しくあまりいろんな人と話す気力がなく一部の人としか交流できなかったので残念.

部屋割りは@shora_kujiraさんと@megumishさんとあと一人横国の方と一緒でした.
しょラーさんから色々闇の話を聞いて大爆笑していました.

2日目

朝食はオリセン名物のゼリーを食べました.
ブルーベリー味?だったんですが結構くどくて気持ち悪くなりました.

たわしさん(@nCk_cv)とマヨ子さん(@mayoko_)とチーム「マヨばたわし」として参加しました.
結果はCDHIの4完で15位.

コンテストの詳細はそのうち公開.

この回は主に私が戦犯(なんだけれどできればTLの設定が厳しすぎるせいにしたい)

3日目

朝食はオリセン名物のゼリーを食べました.
この日はパイン&シークワァーサー味だったのですが,さっぱりしていてとてもおいしかったです.

この日はLINE様に提供していただいた会場でアジア地区模擬予選を行いました.
紺青さん(@konjo_p)とマヨ子さん(@mayoko_)とチーム「マヨばた紺青」として参加しました.
結果はABCDEの5完で13位

コンテストの詳細はそのうち公開.

この回もFを通せなかったので私が戦犯みたいな感じです.

夜はAGCが行われたのですが,サブマリン戦術を見事成功させて4完しました.
ここでいうサブマリンは他の人を油断させる意味のサブマリンではなく,C問題が解けなかったら撤退するという意味のサブマリンです.

1分以内に0完->4完にできて非常に愉快な気分になりました.
f:id:NitCoder000:20160905220346p:plain

4日目

朝食はオリセン名物のゼリーを食べました.
この日も多分パイン&シークワァーサー味だったのですが,やっぱりおいしかったです.

この日はKLab様に提供していただいた会場で過去問セットをやりました.
ゆらふなさん(@yurahuna)とマヨ子(@mayoko_)と出ました(チーム名はない)
結果はACDFHJLの7完で7位か8位ぐらい.

解くべき問題をキチンと解いたという感じなので及第点かなといった感じ.
できればI問題も解きたかったけど多分思いつくのは無理そうでした.

ゆらふなさんのACを1問奪ってしまったのは少し反省しています.
詳しい詳細は後日書きます.

コンテスト終了後,合宿自体は解散ということになったので,Twitter等で関わりのあった人で集まって,築地観光に出かけました.
といっても築地が稼働するのは朝なので夕方に行って施設を眺めるだけみたいになってしまった.

築地周辺なら美味い魚食えるやろということで海鮮丼を食べに行きました.
f:id:NitCoder000:20160905215137j:plain
とてもおいしく,楽しい会話もできたので,滅茶苦茶楽しかったです.


というわけで超適当な参加記は終了です.
合宿参加した選手の方々,スタッフの皆さんお疲れ様でした.

memo

(custom-set-variables
 ;; custom-set-variables was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 '(ansi-color-faces-vector
   [default default default italic underline success warning error])
 '(custom-enabled-themes (quote (tango-dark))))
(custom-set-faces
 ;; custom-set-faces was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 '(default ((t (:family "Verdana" :foundry "outline" :slant normal :weight normal :height 120 :width normal)))))

(global-linum-mode t)
(setq linum-format "%3d ")

(setq c-basic-offset 4)

(setq make-backup-files nil)

(require 'flymake)

(defun flymake-cc-init ()
  (let* ((temp-file   (flymake-init-create-temp-buffer-copy
                       'flymake-create-temp-inplace))
         (local-file  (file-relative-name
                       temp-file
                       (file-name-directory buffer-file-name))))
    (list "g++" (list  "-std=c++11" "-fsyntax-only" local-file))))

(push '("\\.cpp$" flymake-cc-init) flymake-allowed-file-name-masks)

(add-hook 'c++-mode-hook
          '(lambda ()
             (flymake-mode t)))

(setq ring-bell-function 'ignore)

(if window-system (progn
    (set-background-color "Black")
    (set-foreground-color "LightGray")
    (set-cursor-color "Gray")
    (set-frame-parameter nil 'alpha 80) ;透明度
    ))

(setq inhibit-startup-message t)
(setq-default indent-tabs-mode nil)