sort色々

昇順ソート

const int n=8;
int a[n]={1,3,6,7,4,2,5,8};
vector<int> vec{1,3,6,7,4,2,5,8};

// 昇順
sort(a,a+n);
sort(vec.begin(), vec.end());

// C++11以降
// g++なら-std=c++11オプションをつけてコンパイル
sort(begin(a), end(a));
sort(begin(vec), end(vec));

降順ソート

sort(vec.rbegin(), vec.rend());

// 負の数にしてソート
for(int i=0;i<n;i++) a[i]=-a[i];
sort(a,a+n);
for(int i=0;i<n;i++) a[i]=-a[i];

// ソート後に反転
sort(a,a+n);
reverse(a,a+n);

// greaterを使う
sort(a,a+n,greater<int>());

// ラムダ式 C++11以降
sort(vec.begin(), vec.end(),[](int l,int r){return l>r;});


// C++14以降
// g++なら-std=c++14オプションをつけてコンパイル
sort(rbegin(a), rend(a));
sort(rbegin(vec), rend(vec));

クラスのソート

struct Hoge {
    int a,b,c;
    Hoge(int a,int b,int c) : 
        a(a),b(b),c(c){}
    // operator を定義する
    bool operator<(const Hoge &rhs) const {
        return a<rhs.a;
    }

    // Strict Weak Orderというものがあって、うまく定義しないとダメ
    // http://d.hatena.ne.jp/Cryolite/20040529:embed:cite
    // 複数のものをソートするにはtuple使うのが便利
    bool operator<(const Hoge &rhs) const {
        return tie(a,b,c) < tie(rhs.a,rhs.b,rhs.c);
    }

    // rel_opsなるものがあるらしい(Mi_Sawaさんより)
    bool operator>(const Hoge &rhs) const {
        return rel_ops::operator>(*this,rhs);
    }

};

ICPC2015国内予選

チーム

同じ学科のB2の人とB3の人と出ました
方針はB2の人がA問題、B3の人がB問題、僕がC問題でそれ以降は全員で考えるみたいな感じでした

コンテスト

問題を印刷してA問題を読む(B2の人は競プロ慣れてない人だから一緒に考えるみたいなことにしてた)
去年のA問題ほど複雑ではないなあと思いながら問題概要を伝えて実装の方針を伝える

B問題読んでた先輩に声をかけるとすごい簡単だと言われる
問題概要と方針聞くけど間違ってなさそうだと思う

印刷しておいたC問題とD問題を読む
C問題は頑張って実装すればいいことがわかったけど、D問題は小銭をどう持つかわからないとなった
確実に解けそうなC問題をどう書こうか考えてたら、A問題のサンプルが合わないらしくソースコードを印刷してパソコン交代
先輩がB問題を書き始める
ソースコードを一緒に確認すると、点数が降順に与えられていることが伝わってなかったのと、ギャップが同じ時は人数を最大化できてないことに気付いて指摘する

気付いたら先輩がB問題を通しててA問題の修正も一瞬で終わって2完になる(ここで30分ぐらい)

C問題全然考えてないのにパソコン回ってきてつらくなる

バグる気しかしないなあと思いながら動くものを書いてサンプル食わせると案の定バグっていた
色んなところにprintf仕込みながら必死にバグを取る

1時間ぐらい溶かす

サンプル一致したから提出したらACをもらう

順位表を見ると3完がたくさんいて、残り半分の時間で4問目を通せるかだなあと思う

E問題の問題概要聞くけどよくわからないし、F問題は問題概要は簡単だけど解法わからないってなる

D問題でそれっぽいDP書くけどサンプル合わない
色々してるうちに時間が過ぎてコンテスト終了

コード

gist.github.com

結果

ギリギリ通過していました！

RUPC2015参加記

初参加でした

一日目

CODE THANKS FESTIVALの会場で会ったことのあるomu さんと再会する。
一緒にチームを組もうという話になって組むことになる。div1:div2を1:2で組みましょうみたいなことを運営の人に言われる。div1の人を募集した結果Mi_Sawaさんがチームに加わることになる。チーム名は全員のHNを合わせた omu_sawa_dan になる。

チーム方針をどうするか話してる時にMi_Sawaさんは普段US配列のキーボードを使用していることがわかる。その結果、Mi_Sawaさんが解法考える人になると宣言する。

コンテストが始まる。

僕がテンプレートを打ち込み、その間に2人が問題を読むという形に。打ち終わる。

omuさんがAを書き始める。

Bを読む。sortして累積和取って二分探索すればいいのがすぐわかる。Mi_Sawaさんに考えた解法を伝えると、もっと簡単な解法があることを教えてもらう。

Aが通らないらしく、印刷してパソコンを交代する。Bを書いて投げる。WAをもらう。印刷してパソコンを交代する。

今の解法だと配列の大きさが64bit分ないとダメだから、sortして累積和取って二分探索の方でいこうと言われる。パソコンを交代する。境界条件面倒って言いながら書く。投げる。通る。

Cを読む。DFSして最小値見つけて掛け算すれば良さそうとわかる。それをMi_Sawaさんに伝えるとUnion-Findを使うほうが楽だと教えてもらう。

Aが通る。Cを書き始める。O(N^2)を投げたけど通らない。次数の下げ方を教えてもらって下げる。投げる。通る。

Dの解法をMi_Sawaさんに解説してもらう。第一段階としてTLE解法をomuさんが実装することになる。その後オーダーを下げる方法を教えてもらいながら僕が実装する。投げる。通る。

EもDPで解けると言われる。解説を聞くが頭が足りないので理解できない。言われるがままに実装する。バグを取る。終了30秒前になってて慌てて提出する。一発で通る。

Mi_Sawaさんプロだった。何度も同じことを質問したけど毎回優しく答えてくれました。人間的にもプロだった。

二日目

この日は5時間セットでdiv1とdiv2は混合しないようにチームを組むことになった。

くじ引きの結果、YuZakuroさんとししゃもさんとチームを組むことになる。チーム名はhopping_heartsになった。両方面識のある人だったから気が楽になる。

チーム方針を話している時にある問題が浮上する。それぞれの普段のプログラミング環境が

僕 YuZakuroさん ししゃもさん
OS Windows Linux OS X
キーボード JIS配列 Dvorak配列 US配列

と全く異なることがわかる。つらい。

コンテストが始まる。

マクロを打ち込む。打ち終わったあとにYuZakuroさんがBはやるだけ宣言をしたのでパソコンを交代する。

Cを読む。ワープする順番は関係ないから、まとめて右に行ったあとにまとめて左に行けばいいと思い、DPで解ける気がする。

Aを投げるけどREする。印刷してししゃもさんにパソコンを交代。ししゃもさんがAを実装する。

Bのコードを読んで配列外参照してるところを見つける。ここ直したら通るだろうってことになる。

Aが難しいらしい。印刷してパソコンを交代する。YuZakuroさんがBを修正して提出する。通る。

YuZakuroさんとししゃもさんにAを任せてCをDPで実装する。投げる。通らない。

印刷してYuZakuroさんにパソコンを譲る。Aが通る。

Dは実験して周期性を見つけて周期ごとにまとめれば良いってことになる。愚直に1日ずつ進める関数を書く。400年周期であることがわかる。実装をししゃもさんに任せて、YuZakuroさんとCを考える。

YuZakuroさんが大きく左右にワープするパターンで落ちることを発見する。

似たような問題を幅優先で解いたことを思い出す。これも幅優先ではと思い始める。

Dがなんかバグっててサンプルが通らないのでパソコンを交代する。Cを幅優先で書く。サンプルが合わない。YuZakuroさんにバグを直してもらう。投げる。TLEする。dijkstraと同じでpriority_queueを使えばいい気がしてくる。queueをpriority_queueにして投げる。通る。

ここで残り1時間ぐらい。

Dのバグ取りに残りを使うことになる。

printfデバッグでバグを探す。曜日判定を行っている

365*y+y/4-y/100+y/400+153*(m+1)/5+d-428;

でオーバーフローしてることがわかる。元々経過日数を計算する式だけど、欲しいのは経過日数の剰余だから途中で剰余とっても問題ないよねってことで式をいじる。サンプルが合う。投げる。通る。

自分が担当したCに時間をかけすぎた...。Eはローリングハッシュ使うんだろうなと思ってたら案の定だったから本番でもっと考えたかった。

チームの人にコード見てもらってバグを修正してもらうのはチーム戦って感じで良かったです。

懇親会のあと会津大の人と信州大の人と一緒に銭湯に行きました。色々お話して勉強になりました。

三日目

一日目と同じくdiv1,div2混合チームにしましょうということになる。

くじ引きの結果、わにさんとぬまさんとでチームを組むことになった。僕以外の二人がMacだったため、チーム名はMacLoversになった。わにさんとは二日目の夜に銭湯に行った時からチーム組めたらいいなと思っていたので組めて良かった。

コンテストが始まる。

わにさんがA、僕がB、ぬまさんがCを読む。

わにさんがAを実装する。投げる。通る。

Bを誤読してて解法がわからない状態だった。わにさんに相談した結果誤読が判明する。Bを実装する。タイプミスしまくる。30分かかる。サンプル一致する。投げる。通る。

Cをぬまさんが実装する。その間にわにさんとD,Eのについて話し合う。

ぬまさんがCを通す。

Dは拡張ダイクストラで解けると思い、実装する。サンプル一致しない(今思うと始点をデクリメントしてなかったせい)。

ぬまさんに、郵便物に関係する頂点について普通のダイクストラして、その後に配る順番を総当りすればいいと言われる。総当りパートをぬまさんが実装する。わにさんのEの解法を聞く。難しそうと感じる。

ぬまさんが総当りパートを実装し終えたので、ダイクストラパートとくっ付ける。投げる。通らない。

INFを10回以上足していることに気付く。intをlong longに変更する。投げる。通る。

コンテストが終わる。

Cは実装重たいって言いながらスッと通したり、Dの総当りパートを実装したぬまさん強いなあと思った。

わにさんがFについて正しい解法を思いついていて、時間があったら解けてた気がする。悲しい。

終わりに

立命館合宿とても楽しかったです。運営側、作問側の方々ありがとうございました。

ローリングハッシュ

ちょっと勉強したのでメモ

Bを定数、長さnの文字列をsとすると\displaystyle \sum_{i=0}^{n-1} s_i \times B^{n-i-1} \mod M で計算される値をローリングハッシュと言うらしい
[l,r)での部分文字列のローリングハッシュの値は (H_{0,r} - B^{r-l} \times H_{0,l}) \mod M で計算できる
また、長さmの文字列を後ろにくっつけた時のローリングハッシュの値は、(H_{0,n} \times B^{m} + H_{0,m}) \mod Mで計算できる

ハッシュ値の衝突についてはハッシュを衝突させる話

ソースコード

衝突を起こらないようにするには、複数のmodで計算するのがいいらしい

ローリングハッシュ

例題

AOJ2444
Codeforces Round0291 Div2 C

参考にしたサイト

http://d.hatena.ne.jp/say_hello_to_okaoka/20140204/1391484891

http://algoogle.hadrori.jp/algorithm/rolling-hash.html

http://kmjp.hatenablog.jp/entry/2015/02/15/0900

あり本第二版には載ってるらしい。購入しないとなあ

CODE THANKS FESTIVAL 2014 A日程に参加しました

来年は予選通らねば...

結果

6完+部分点で630点7位

コンテスト

A問題

開始から5秒ぐらい問題が閲覧できなかったけどあれは何だったんだろう

int A,B;
int main() {
    cin>>A>>B;
    cout<<A*4+2*B<<endl;
    return 0;
}
B問題

A→B→Cの順に固定だと思ってた
マイナスにしてソートするの便利

int N;
int A[3];
int main() {
    cin>>N;
    cin>>A[0]>>A[1]>>A[2];
    int sum =0;
    int ans =0;
    int count=0;
    rep(i,3) A[i]=-A[i];
    sort(A,A+3);
    rep(i,3) A[i]=-A[i];

    while(1) {
        sum+=A[count];
        ans++;
        count++;
        count%=3;
        if(sum >= N) break;
    }
    cout<<ans<<endl;
    return 0;
}
C問題
int N,M;
int P[102];
int S[102];
int main() {
    cin>>N>>M;
    rep(i,N) cin>>P[i];
    rep(i,M) cin>>S[i];
    int ans = 0;
    rep(i,M) ans+=P[S[i]-1];
    cout<<ans<<endl;
    return 0;
}
D問題

if書いてる途中でmax,min使えば出来そうなことに気付いたけどそのままifで提出した

int N,Q;
int a[100005];
int b[100005];
int s[100005];
int t[100005];
int main() {
    cin>>N>>Q;
    rep(i,Q) cin>>a[i]>>b[i]>>s[i]>>t[i];
    rep(i,Q) {
        int ans = 0;


        if(b[i]<=s[i]) ans=t[i]-s[i];
        else if(t[i]<=a[i]) ans=t[i]-s[i];
        else if(a[i]<=s[i]&&t[i]<=b[i]) ans=0;
        else {
            if(a[i]-s[i]>=0) ans=a[i]-s[i];
            if(t[i]-b[i]>=0) ans+=t[i]-b[i];
        }
        cout<<ans*100<<endl;

    }
    return 0;
}
F問題

Eと比べて問題文短いし簡単そうだったのでこっちから解いた 初めはUnionFindかな？とか考えていたけど、上がって下がるパターンも数えることになってダメだと途中で気付く 辺貼って舐めた

int N,M;
int a[55],b[55];
vector<int> G[55];
int dfs(int s,int t) {
    queue<P> que;
    que.push(P(s,0));
    bool flag[55] = {};

    while(que.size()) {
        P p = que.front();
        que.pop();
        int v = p.fr;
        if(flag[v]) continue;
        flag[v] = true;
        if(p.fr==t) return 1;
        rep(i,G[v].size()) {
            int e = G[v][i];
            que.push(P(e,p.sc+1));
        }

    }

    return 0;
}
int main() {
    cin>>N>>M;
    rep(i,M) {
        cin>>a[i]>>b[i];
        G[a[i]].pb(b[i]);
    }
    int ans = 0;
    rep(i,N+1) {
        if(i==0) continue;
        if(dfs(i,1)==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}
E問題

シミュレーションするだけではと思い込んでO(N2 RC)を投げてしまう
TLEする
累積和の部分をいもす法して投げたら通る
コンテスト後に1位の方が言っていたけど、ちゃんと計算量の見積もりしてからコード書かねば

int R,C,M;
int N;
int r[2][5050];
int c[2][5050];

int grid[55][55];


void init() {
    rep(i,55) rep(j,55) grid[i][j]=0;
}
void rote(int a) {
    grid[r[0][a]][c[0][a]]++;
    grid[r[0][a]][c[1][a]+1]--;
    grid[r[1][a]+1][c[0][a]]--;
    grid[r[1][a]+1][c[1][a]+1]++;
}
void imos() {
    rep(i,R+1) {
        rep(j,C+1) {
            if(j!=0) grid[i][j]+=grid[i][j-1];
        }
    }
    rep(i,R+1) {
        if(i==0) continue;
        rep(j,C+1) {
            grid[i][j]+=grid[i-1][j];
        }
    }
}
int count() {
    int res = 0;
    rep(i,R) rep(j,C) if(grid[i][j]%4==0) res++;
    return res;
}
int main() {
    cin>>R>>C>>M;
    cin>>N;
    rep(i,N) cin>>r[0][i]>>r[1][i]>>c[0][i]>>c[1][i];
    rep(i,N) r[0][i]--,r[1][i]--,c[0][i]--,c[1][i]--;

    init();
    rep(i,N) {
        rep(j,N) {
            if(i==j) continue;
            rote(j);
        }
        imos();
        int c = count();
        if(M==c) {
            cout<<i+1<<endl;
        }
        init();
    }
    return 0;
}
G問題

1つ前の席の状態を持ってDPかな？と思って書いたけど、サンプル段階でダメと気付く
よく考えて実装に移らないとダメ 部分点だけ取りにいった

H問題

この時点で4位で、この問題の部分点取れば5位以上にはなるかなとか思ってた
結果部分点すらバグった

感想

計算量の見積もりとか、よく考えてから実装に移るとか、色々出来てないことがわかった
あと、普段のコンテストでは上位陣の正解状況を見て次の問題を選ぶってことができるけど、今回はそうは出来なくて精神的につらいなあと感じました

最後に

スタッフの方々本当にありがとうございました！

ICPC国内予選2014参加記

当日

始まるまで

お昼休みにカントリーマアムを買ったり、図書館でC++の本を借りたりで気合十分でした
4限目が16:30に終了するため競技開始ギリギリに会場に到着することに

競技開始

役割分担としては、2回生の先輩がA、3回生の先輩がB、僕がCを担当すると模擬予選の時に決まっていたので、国内予選もその形に

A問題AC

ここで15分ぐらい
2回生の先輩がA問題をAC
C問題を読んだ僕は二分探索すれば良いだろうと考えていました

B問題AC

ここで60分ぐらい
3回生の先輩がB問題をAC
C問題の方針を2回生の先輩に説明したり、D問題の方針を軽く聞いていたりしました

C問題

ARCで似たような問題を解いた事があり、紙コーディングも済ませていたので10分もあればACできるだろうと思っていました
しかしコーディングしてみるもののサンプルすらあわず、頭を抱えていたら図形と円の判定が間違っていると指摘を受ける
判定を色々いじっていたら、2時間が過ぎて競技が終了していました...

反省点

C問題は二分探索が必要ないらしく、完全に間違った方針を示した僕の責任でした
後から聞くとD問題は全列挙するだけらしく、C問題を捨てる判断も必要でした
そのためにも誰かがリーダーになって役割を分担するといいねーと終了後別の先輩から指摘されました
他の方の参加記をみると、PCを専有する人、専有する人にツッコミを入れる人、問題の方針を考える人に分担すると良い(？)
チームメンバーそれぞれが互いの得意不得意とするアルゴリズムを把握していなかったことも問題だったかも

チームの先輩方にグラフを勉強すると宣言したので夏休みはグラフを勉強します！！