std::atomic使ったことなし。

std::atomicについて調べてみた…

• 排他処理をする場合にlock_guardを使うとコストが高い。そこでstd::atomicを使う。
• 複数のスレッドが同時に読み込んでもそれらの操作が順々に行われているように見えることを保証している、それがatomic変数
• 最適化がマルチスレッドでの動作に悪影響を与えてしまうのを防ぐために最適化を防ぐ。それがメモリバリアという考え方。
• メモリバリアには二種類あって、releaseバリア(先行する命令が後ろにリオーダーされるのを防ぐ)、aquireバリア(後述の命令がバリアを超えて前にリオーダーされるのを防ぐ)。- つまりstore_releaseとload_aquireがある。
• これによって正しく同期化できる
• サンプルコード
• 競合が起こる例

#include <atomic>
#include <iostream>
#include <thread>

int val = 0;

int main()
{
    std::thread th1([&]() {for(int i=0; i<10000000; i++) val++; });
    std::thread th2([&]() {for(int i=0; i<10000000; i++) val--; });
    th1.join();
    th2.join();
    std::cout << val << std::endl;
}

• std::atomicに最適化した書き方

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> val;

int main()
{
    std::thread th1([&]() {
            for(int i=0; i<10000000; i++) val++; //fetch_add(1)でもok
    });
    std::thread th2([&]() {
            for(int i=0; i<10000000; i++) val--; //fetch_sub(1)でもok
    });
    th1.join();
    th2.join();
    std::cout << val << std::endl;
}

• spin-lockできるね！mutex…

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<bool> bl(false);
int val = 0;
void spin_lock(void)
{
    //exchangeは引数を書き込んで、前の値を返す
    while (bl.exchange(true)) {  //exchange_aquire
    }
}

void spin_unlock(void)
{
    bl.store(false);  //store_release
}

int main()
{
    std::thread th1([&]() {
            for(int i=0; i<10000000; i++){
                spin_lock();
                val++;
                spin_unlock();
            }
    });
    std::thread th2([&]() {
            for(int i=0; i<10000000; i++){
                spin_lock();
                val--;
                spin_unlock();
            }
    });
    th1.join();
    th2.join();
    std::cout << val << std::endl;
}

• 汎用的な書き方

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> val(0);

/* bool atomic<T>::compare_exchange_weak(T& expected, T desired)
 * 現在の値が expected に等しければ desired を書いて true を返す
 * そうでなければ expected を現在の値に書き換えて false を返す
 * これはexchangeが失敗する可能性があるため、loopが必要となる。
 */

/* bool atomic<T>::compare_exchange_strong(T& expected, T desired)
 * 現在の値が expected に等しければ desired を書いて true を返す
 * そうでなければ expected を現在の値に書き換えて false を返す
 * exchangeは必ず成功するためloopを使わない場合に使ってね。
 */

int main()
{
    std::thread th1([&]() {
            for(int i=0; i<10000000; i++){
                int expected = val.load();
                int desired;
                do {
                    desired = expected + 1;
                } while ( !val.compare_exchange_weak(expected, desired));
            }
    });
    std::thread th2([&]() {
            for (int i = 0; i < 10000000; i++) {
                int expected = val.load();
                int desired;
                do {
                    desired = expected - 1;
                } while (!val.compare_exchange_weak(expected, desired));
            }
    });
    th1.join();
    th2.join();
    std::cout << val << std::endl;
}

rubyってどんなのだっけ1

最近使ってない言語って忘れますよね。1年ruby使ってなかったら完全に忘れました。ということでメモ。

• printは改行なし
• "a"はString.new("a")と同じ
• ruby -Ku hoge.rbとかするとutf-8として実行できる($KCODEを変えている)
• windowsだと表示がshift-jisだったりするので, require "kconv"; print(kconv.tosjis("a"))とかしなければならない
• ""は\nとかが認識されるが、''はすべてタダの文字列として扱われる(\'と\\だけは別)
• %Q[あ"い"う]を使えば""を表せる("をいちいちエスケープしなくてよい)。%qは''を表す
• 下記のようにヒアドキュメントが書ける

str = <<"EOS" # <<と"EOS"の間にスペース要らない。
  hoge
  hoge
EOS 

• name = "Tokyo"; print("出身は#{name}です。1+2=#{1+2}") このように式展開できる
• print "a" + "b" で文字連結
• print "ok!"*3 で指定数連結
• print "Tokyo" << " Japan"というように<<でStringの連結ができる。"a".concat("b")も同じ
• 数字は下記のように表す

Numeric -- Integer -- Fixnum(整数)
         |          |
         |          - Bignum(大きな整数) --Fixnumから自動的に切り替わる
         - Float    --これらのクラスではnewメソッドは使えない

• 0b~, 0~, 0x~で2,8,16進数が表せる
• 2e3とか2e-3とかも使える
• 2_100_200とかで数値を見やすくできる
• &|^-<<>>などのbit演算子はすべて使える
• 変数には型はなく、ただのオブジェクトに対する名札(val=10; val="hello"もok)
• 変数は_と英数字しか使えない
• str1="Tokyo";str2=str1;str1="Osaka"ならstr1は"Osaka",str2は"Tokyo"。もしstr1 << "Hey!"だったらstr2は"TokyoHey!"になっている。前者はstr1が指すもの自体を張り替えただけ。後者はstr1が指し示すオブジェクトを変更している。
• num += 1なども使える
• 1/3.0は0.3333となる
• a,b,c=1,2とするなど、多重代入ができる(cはnilとなる). a,b,c=[1,2,3]もok
• PIなどのように大文字にすることでそれを定数とすることができる(変更できない)
• 下記のようにifが使える(もし条件式のあとに改行があるならばthenは省略できる(caseとかもみんなそう))

if a!=0 then
    print "hello"
end

• falseとnilは偽であり、それ以外はすべて真となる
• ! && || and or not が使える
• 以下のようにelsifが使える

if hoge then
    print "hoge"
elsif foo then
    print "foo"
else
    print "hey"
end

• 以下のようにunlessが使える(unlessにelsifはない)

unless hoge then
    print "hoge"
else
    print "foo"
end

• 以下のようにcaseが使える

case str
when "foo" then
    print "foo"
when "apple","banana","lemon" then #複数指定することが可能
    print "fruit"
else                               #elseで指定(なくても良い)
    print "hoge"
end

• result > 60 ? "super" : "zako"などの三項演算子も使える
• print "hello" if debug など、後ろにifが付けられる
• 以下のようにwhileが書ける

while num < 2 do #条件式のあとに改行があればdoは省略できるよ
    print num,"\n"
end

• until hoge >= 2 do print hoge end もあるよ
• 以下のようにforが書けるよ

for num in 1..3 do #1..3のところはeachメソッドを持ったオブジェクト(配列やHash,範囲オブジェクトなど)
    print num,"\n"
end

• "a".."z"などとしても範囲オブジェクトが作成できる(これはlastを含む)
• これらは実際にはRange.new(first, last)でも作成できる
• Range.new(first, last, true)とすればlastが抜ける
• Rangeオブジェクトはオブジェクト.succを使って更新している

"zz".succ -> "aaa"
"4:5:9".succ -> "4:6:0" #数字が入っていたらそいつらだけ更新される

• 以下のようにeachが使える

(5..10).each{ |n| # eachやtimesのような{}ブロックを持つメソッドをイテレータという
    print n       # {}はdo endにすることもできる
}
<||
>|ruby|
10.times{|n| print n} #0~オブジェクト-1まで走査

3.upto(7){|n| print n} #3,4,5,6,7まで走査(ちなみに|n|みたいなのは省略可能)

7.upto(3){|n| print n} #7,6,5,4,3まで走査

2.4.step(5.3, 0.8}{|n| print n} #2.4,3.2,4.0,4.8と走査

loop{ print "hello" } --無限ループ

• breakは一番内側の繰り返しだけ抜ける
• nextはいわゆるcontinueと同じ動作
• redoは現在の繰り返しをやりなおす
• num *= 2 while num < 1000 など、後ろからwhileとunitlを使うことができる
• a = ["山田", 1, 2]などと配列は違うオブジェクトを格納できる
• a[-1], a[-2]ができる。at(0)でも取得できる
• Array[1,2,3]と[1,2,3]は同じ
• Array.new(3)で[nil,nil,nil]が作れる
• Array.new(3, "hello")で["hello","hello","hello"]が作れる
• Array.new(3){|i| i*i} で[0,1,4]が作れる
• a = [1,2,3];b=a;c=Array.new(a)においてbとaは全く同じ場所をさすが、cは複製なのでa,bを変更しても影響はない
• a.length, a.sizeで配列の大きさが取れる
• 配列の要素がnilであるものを除いてカウントする場合はa.ntimesを使う
• a = [1,2,3]; a[5] = 3とするとa = [1,2,3,nil,nil,3]となる
• hash = {"a" => 1, "b" => 2, "c" => "3"} Hashクラス
• hash = Hash["a", 1, "b", 2]でも作れる(個数は偶数個でなければならない)
• hash["a"] or hash.fetch("a")でvalueが取り出せる(ただしfetchではミスったときにIndexErrorが起こる。前者ならnilとなる)
• hash.fetch("a", "none")でデフォルト値がnoneになる
• hash = Hash.new()で作れる
• h = Hash.new{|hash, key| hash[key] = "none"} においてこれはデフォルト値をnoneにしている
• hh = Hash[h] で複製ができる
• h = Hash.new("none")でデフォルト値がnoneとなる
• h.default = "none"でもよい
• h["a"] = 1で要素を追加
• h.store("a", 1)も同じ動作を示す
• h.size, h.lengthで大きさが取れる
• h.each{|k, v| print k,v,"\n"}, h.each_key, h.each_valueも存在する
• h.keys, h.valuesでそれらを配列として取り出せる
• h.to_aで[[key1, value1],[key2, value2],…]となるようなものを取り出せる
• hash.delete("b")
• hash.delete("a"){|key| print key} はkeyがなかった時にブロックの中が呼ばれる
• selfはそのメソッドを実行しているオブジェクトを示す
• print(self.to_s); print(self.class.to_s)でmain, Objectと返す
• def addString(str) str << ",Japan" end; a = "Tokyo"; addString(a); print a
• 関数の引数はすべて参照渡し
• デフォルト引数は普通に使える
• def printHello(msg, *names) とすることで余った引数を配列としてすべてnamesに入れることができる
• returnを関数の中では使える。これは省略可能であり、最後に評価した式の返り値が関数の返り値となる
• return a,bのように多重で返すこともできる
• 理解した。a=1は1というオブジェクトに対して名前を張り替えてるだけ
• b = a; a = 2;としてもaが指すオブジェクトが変わるだけだからbに変化はない
• それに対してa = "a";b = a;a << "c";とするとも変わってしまう。これはaが指すオブジェクトに対して何らかの操作を加えているから
• class名は大文字からはじめなけれなならない
• class Car ~~ end; car1 = Car.new() で作成
• メソッドを呼び出すのはCar.method()でもCar::method()でも同じ
• インスタンス変数は@を先頭につけることで使うことができる。@hogeに値を入れた時点から使えるようになる。
• initializeメソッドを定義することによってクラスのオブジェクトを作成したときに必ずそれが呼ばれるようになる。
• インスタンス変数はクラスの外から値を取ってきたりできないのでアクセスメソッドをいちいち定義しなければならない
• それを省略することができるのがアクセスメソッド

attr_reader :変数名　参照が可能
attr_writer :変数名　更新が可能
attr_accessor :変数名　参照と更新が可能

• ちなみに、attr_accessorを書くというのは

class Hoge
  def name  #reader
    return @name
  end
  def name=(val) #writer
    @name = val
  end
end

a = Hoge.new
a.name = 'Hello, world!'
puts a.name

• と書くことと一緒らしい
• classの中で生成した定数はclass::variableという形でアクセスできる
• @@を変数名の先頭につけることで暮らす変数を生成することができる
• これはメソッドの中ではないところで生成せよ。
• class A < Base で継承できる
• メソッドの中でsuperを呼ぶと、スーパークラスの同じ名前のメソッドを呼ぶことができる。つまりメソッドの中身の追加とかができる
• superは引数を入れても入れなくても良いが、入れなかった場合は今のメソッドに入ってきた引数をそのまま入れることになる
• public :メソッド名, private :メソッド名でpublic or privateにすることができる
• initializeメソッドは必ずprivateになる
• 単純にpublic, privateと書くだけならば、それ以降のメソッドがすべてpublic, privateになる
• initializeメソッドは普通のメソッドと同様に継承される
• module Hoge end でmoduleを宣言することができる。
• これはHoge.methodでメソッドにアクセスでき、インスタンス変数やらクラス変数はない
• classのなかではincludeでmoduleを読み込むことが可能
• moduleの関数を定義してもそれだけでは普通の関数としては使用できず、module_function :メソッド名というように中に書いてあげなければならない
• includeとして使う場合にはmodule_functionの宣言はいらないよ
• Float.induced_from(num) Integer.induced_fromを使って明示的にオブジェクトを作れるよ！
• to_i, to_fで変換できる(truncateはto_iと一緒)
• round, floor, ceilとかもあるよ
• to_sで文字列変換。引数で基数の指定ができる
• hoge.chrでasciiコードから文字列に変換できる
• "Hello"[1..2] = "pp"でHpploになる
• "Hello".insert(1, "oo")でHooelloになる
• "Hello".index("ll") => 2となる, rindexもある
• "Hello".include?("el") => true
• delete, chomo, chomp!(改行を削除)がある(!があると破壊的)
• strip(空白を取る)
• Array.flattenでネストした[[1,2],3]などを[1,2,3]にできる
• uniq, compact(nilを消す), delete, delete_at, delete_if, reverse, sort, transpose(行と列を入れ替える)
• rubyにoverloadはない
• これやろうな。

Rubyプログラミングが快適になるVim環境を0から構築する - Qiita

CodeFestival2015本戦 I問題 風船ツリー

んーなんかF,G,Hよりは本番中にできる可能性のある問題だったなぁ。
今回も解説スライドがわかりやすいのでみちくり。

• 座標が1e9までだが、高さの上下関係しか興味がないから1~Nに落とせる。
• 最終的にvの高さを超えるものは根本で切れ！
• つまり求めるのは0->vに行くまでの直接の子孫でvの高さを超えるものの数がほしいことに気づけ。
• それはBinaryIndexTreeをうまく使えば簡単に求まることに気づけ。

という感じ。
実装はそこまで難しくないし、F以降だと一番直感的で手をつければ良かったなぁと思った。

struct BinaryIndexedTree{
    int N;
    std::vector<int> bit; //1-indexed つまり1~Nを使う
    BinaryIndexedTree(int n): N(n), bit(n+1, 0){}
    void add(int a, int w){
        for(int x = a; x <=N; x+=x&(-x)) bit[x] += w;
    }
    int sum(int a){ //1~aまでsum
        int ret = 0;
        for(int x = a; x>0; x-=x&(-x)) ret += bit[x];
        return ret;
    }
};

const int MAXN = 100100;

int N;
int L[MAXN], P[MAXN];
int maxH[MAXN];
int H[MAXN];
int cut[MAXN];
vector<int> G[MAXN];
BinaryIndexedTree BIT(MAXN);
map<int, int> mp;
int ans[MAXN];

//風船それぞれの高さを求める
void dfs1(int v, int now)
{
    H[v] = now;
    for(auto u : G[v]){
        dfs1(u, now+L[u]);
    }
}

//風船それぞれから最大で行ける高さを求める
int dfs2(int v)
{
    int mx = H[v];
    for(auto u : G[v]){
        mx = max(mx, dfs2(u));
    }
    return maxH[v] = mx;
}

void dfs3(int v)
{
    for(auto u : G[v]){
        BIT.add(maxH[u], 1);
    }
    cut[v] = BIT.sum(MAXN) - BIT.sum(H[v]);
    for(auto u : G[v]){
        BIT.add(maxH[u], -1);
        dfs3(u);
        BIT.add(maxH[u], 1);
    }
    for(auto u : G[v]){
        BIT.add(maxH[u], -1);
    }
}


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

    cin >> N;
    rep(i, N) cin >> L[i];
    rep(i, N-1) cin >> P[i+1], P[i+1]--;

    for(int i=1; i<N; i++){
        G[P[i]].push_back(i);
    }

    dfs1(0, L[0]);

    //高さを圧縮
    rep(i, N) mp[H[i]] = 0;
    {int h=1; for(auto& m : mp) m.second = h, h++;}
    rep(i, N) H[i] = mp[H[i]];

    dfs2(0);

    dfs3(0);

    rep(i, MAXN) ans[i] = 1e9;
    rep(i, N){
        ans[H[i]] = min(ans[H[i]], cut[i]);
    }

    int Q;
    cin >> Q;
    rep(i, Q){
        int h;
        cin >> h;
        if(mp[h] == 0){
            cout << -1 << endl;
        }else{
            cout << ans[mp[h]] << endl;
        }
    }
}

gitのbareリポジトリ作成方法

これ毎回よくわからなくなるので備忘録

#ローカル環境で
git clone --bare git-test git-test.git
scp -r git-test.git hoge@foo:/opt/git
ssh hoge@foo
#リモート環境で
cd /opt/git/git-test
git init --bare --shared

CodeFestival2015本戦 H問題 焼肉の達人

なるほどーなるほどなるほど。
chokudaiさんがトークセッションで言ってたように、やっぱり必ずグラフというのは疑ったほうがいいですね。
これをdpで解こうとしていた自分が悲しくなります。

それにしてもCodeFestival解説がとてもわかりやすいのですべてそちらにお任せしよう…
ほんとうに書いてあるように辺を張ってダイクストラしたら終わりです。ひょえー

template<int MAX_V>
class Dijkstra{
public:
    typedef pair<ll, int> P;
    struct edge{
        int to;
        ll cost;
    };
    const ll INF = 1e18;
    vector<edge> G[MAX_V];
    ll d[MAX_V];
    int V;

    Dijkstra(int v): V(v){}
    Dijkstra(){} //ちゃんとV設定してね

    void add_edge(int from, int to, ll cost){
        G[from].push_back(edge{to, cost});
    }

    void exec(int s){
        priority_queue<P, vector<P>, greater<P> > que;
        fill(d, d+V, INF);
        d[s] = 0;
        que.push(P(0, s));
        while(!que.empty()){
            P p = que.top(); que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(int i=0; i<(int)G[v].size(); i++){
                edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }
};

Dijkstra<100010> Dj;

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

    int N, M;
    cin >> N >> M;
    P S[N];
    rep(i, N){
        cin >> S[i].first >> S[i].second;
        S[i].second += S[i].first;
    }
    Dj.V = M+1;
    rep(i, M){
        Dj.add_edge(i, i+1, 2);
        Dj.add_edge(i+1, i, 0);
    }
    rep(i, N){
        Dj.add_edge(S[i].first, S[i].second, S[i].second-S[i].first);
    }
    Dj.exec(0);
    cout << 2*M - Dj.d[M] << endl;
}

CodeFestival2015本戦 G問題 スタンプラリー

むーーーこれは難しい。
Euler Tourという考え方で、行きがけ順の配列で木を表すというもの。
まぁそれをもとに今度は木を構成しなおすという話だが、解説スライドでは木と森という考え方を使っている。
実際にはまぁ仮想的な根を考えることで木の考え方だけで解ける。
今回は解説にあった方法を愚直に実装してみた。
この考え方天才的だ。最高。

constexpr ll mod = (ll)1e9+7;
constexpr int MAXN = 256;
int N;
int C[MAXN];
ll dp_tree[MAXN+1][MAXN+1];
ll dp_forest[MAXN+1][MAXN+1];

ll dfs_forest(int l, int r);

ll dfs_tree(int l, int r) //[l, r)でいくつ木が作れるか？
{
    if(r-l == 1) return 1; //要素がひとつになったら一つの木
    if(dp_tree[l][r] > 0) return dp_tree[l][r];
    ll ans = dfs_forest(l+1, r); //[l+1, r)の森にlを根としてつけたしたら木
    return dp_tree[l][r] = ans;
}

ll dfs_forest(int l, int r) //[l, r)でいくつ森が作れるか？
{
    if(r-l == 1) return 1; //要素がひとつになったら一つの森
    if(dp_forest[l][r] > 0) return dp_forest[l][r];
    ll ans = dfs_tree(l, r); //木は森
    for(int i=l+1; i<r; i++){ //[l, i)の木に[i, r)の森をつけたしたら森
        if(C[l] < C[i]){
            ans += dfs_tree(l, i)*dfs_forest(i, r);
            ans %= mod;
        }
    }
    return dp_forest[l][r] = ans;
}

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

    cin >> N;
    rep(i, N) cin >> C[i], C[i]--;
    if(C[0] != 0){
        cout << 0 << endl;
        return 0;
    }

    cout << dfs_tree(0, N) << endl;
}

CodeFestival2015本戦 F問題 歩くピアニスト

CodeFestival本戦行ってきました…
んーなんというか、まぁ普通に本戦5問解いて、他も無難な感じで、実力相応という感じでした。
ただ、あんなにオタクたちが集まってる中で、みんな知り合いとしかしゃべろうとしませんよね。
"繋がる"とか言ってた割には知らない人との交流(強制)が少なかったので(Happy Hourとか言ってたけど、ん？という感じ)、もっと交流の場を設けて欲しかったなぁ。
そして何よりもスケジュールがパンパンでゆっくり出来ないのは残念だった。
Coderunnerだとお酒もあるし、テーブルごとにグループ分けて集まらせて懇親させ、人を変えてまたやったりなど、結構良かったなぁ。

なんてのはどうでもよくて、F解けませんでした。

解説を読めばわかります。
ただ気をつけるのは、NOのケースのときに辺を通る回数がマイナスになったりするので、それらを弾きましょう。
あと、自分はわざわざグラフ作ってdfsとかいうバカなことをしましたが、連結してるかどうかだけ知りたいんだったらUnionFindが頭良かったなーなんておもいました。

vector<int> G[7];
bool used[7];

int dfs(int v){
    used[v] = true;
    int sum = 1;
    for(int a : G[v]){
        if(!used[a]) sum+=dfs(a);
    }
    return sum;
}

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

    ll C[7];
    rep(i, 7) cin >> C[i];
    C[0]--;
    ll x = C[0]-C[6]+C[5]-C[4]+C[3]-C[2]+C[1];
    ll X[7];
    X[0] = x;
    for(int i=1; i<7; i++){
        X[i] = 2*C[i]-X[i-1];
    }
    bool ok = true;
    for(int i=0; i<7; i++){
        if(X[i] < 0) ok = false;
        if((X[i] + X[(i+1)%7])&1) ok = false;
    }
    for(int i=0; i<7; i++){
        if(X[(i+7-1)%7]) G[i].push_back((i+7-1)%7);
        if(X[(i+7)%7]) G[i].push_back((i+7+1)%7);
    }
    dfs(0);
    for(int i=0; i<7; i++){
        if(!used[i] && (X[(i+7-1)%7]+X[i])) ok = false;
    }
    cout << (ok ? "YES" : "NO") << endl;
}

CodeFestival2014 H問題 部屋割り

発想が思いついたのは良かった。ただ、実装が…

この問題って、単純に前から走査して最終的な部屋割り、また、各々が部屋に入るとき、何人部屋に入るかを知ることができる。
そうしたら最終的な部屋割りから最初の方に向かっていって走査していく。
そのときに、あとから期待値として何人上に入ってくるかを計算していけばよい。

kmjpさんの実装が素晴らしかった…。
自分の良くない癖でmapで部屋割りを作っていったんだが、it = mp.begin()とかしてmp[it->first+1]を触ったりするとitの位置が変化したりとかして本当に大変だった。
こういう連続して並び、かつ最初と最後しか触らないんだったら、配列とmin, maxの変数だけで構成すればいいというのは勉強になった。

const int MAXN = 200005;
int mp[MAXN];
int mi, ma;
int rn[MAXN];
double ans[MAXN];
double np[MAXN];

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

    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    mp[0] = K;
    rep(i, N){
        if(S[i] == '0'){
            rn[i] = mi;
            mp[mi]--;
            mp[mi+1]++;
            ma = max(ma, mi+1);
            if(mp[mi] == 0) mi++;
        }else{
            rn[i] = ma;
            mp[ma]--;
            mp[ma+1]++;
            while(mp[mi] == 0) mi++;
            ma++;
        }
    }

    for(int i=N-1; i>=0; i--){
        int n = rn[i];
        ans[i] = n+1+np[n+1];
        np[n] = (np[n]*mp[n] + (np[n+1]+1.0)*1.0)/(mp[n]+1.0);
        mp[n+1]--;
        mp[n]++;
    }

    rep(i, N){
        printf("%14.14lf\n", ans[i]);
    }
}

CodeThanksFestival2014 H問題 しりとりゲーム

もとにある文字列でしりとりしていくゲーム。足りない単語数は？というのが問題(適当)

今回、単語の最初と最後を使ってグラフを作るというのはすぐに気づいた。
問題はこれを一筆書きするのだが、オイラー閉路なんてもの知らなかった…これめっちゃ有名なやつじゃん…

グラフを一筆書きできる条件は、グラフの頂点の次数がすべて偶数 or 次数が奇数の頂点が2つだけ。

ということですべての頂点が連結になり、かつオイラー閉路の条件を満たせば良い。
連結ではない頂点群を連結するためには、スライドにあるような処理をすれば良い。
これは結構まとめられて、すごいスッキリしたコードになるので実際の処理は簡単♪
うまくまとめることって大事だ…

struct UnionFind
{
    std::vector<int> data;
    UnionFind(int size) : data(size, -1){}
    void initialize(void){
        for(int i=0; i<(int)data.size(); i++) data[i] = i;
    }
    bool merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        else{ data[x] = y; return true; }
    }
    int find(int x){ //根っこを見つける関数
        if(data[x] == x) return x;
        else return data[x] = find(data[x]); //経路圧縮
    }
    bool isSame(int x, int y){
        return find(x) == find(y);
    }
};

const int AL = 26;
int N;
UnionFind uf(AL);
int edge[AL];
vector<int> G[AL];

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

    uf.initialize();
    cin >> N;
    rep(i, N){
        string s; cin >> s;
        int f = s.front()-'a';
        int b = s.back()-'a';
        uf.merge(b, f);
        edge[f]++; edge[b]++;
    }

    rep(i, AL) G[uf.find(i)].push_back(edge[i]);

    int res = 0;
    rep(i, AL){
        if(len(G[i]) == 0 || edge[i] == 0) continue;
        int n_odd = 0; //奇点の数
        for(int a : G[i]) if(a&1) n_odd++;
        res += max(n_odd/2-1, 0)+1;
    }


    cout << res-1 << endl;
}

ARC039 D問題 旅行会社高橋君

考え方は簡単。というより一瞬で気づいた。
ただ、この問題、二重辺連結成分分解、まぁつまり橋の検出と、LowestCommonAncesterの実装をしないといけないのでライブラリとか持ってないと地獄…つらかった…。
まず、a,b,cという始点,中継点,終点が与えられたときa,b またはb,cが同じ二重辺連結成分に入っていればどう考えてもおｋ
入っていないときは、二重辺連結成分分解でただの木にしたあと、a,cの間にbが存在すればよいということになる。つまり、aからbの距離とbからcの距離の和がaからcの距離の和になっていればいいのである。これをするにはLCAを使うのじゃ〜〜
二重辺連結成分分解はlowlink理解してれば簡単。LCAもまぁそこまで難しい話じゃないので、理解してスパゲッティコードと蟻本からとってきた。

struct Edge {
    int src, dst;
    Edge(int src, int dst) : src(src), dst(dst) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void visit(const Graph & g, int v, int u,
        Edges& brdg, vector< vector<int> >& tecomp,
        stack<int>& roots, stack<int>& S, vector<bool>& inS,
        vector<int>& num, int& time) {
    num[v] = ++time;
    S.push(v); inS[v] = true;
    roots.push(v);
    for (auto e : g[v]) {
        int w = e.dst;
        if (num[w] == 0) //non-used
            visit(g, w, v, brdg, tecomp, roots, S, inS, num, time);
        else if (u != w && inS[w])
            while (num[roots.top()] > num[w]) roots.pop();
    }
    if (v == roots.top()) {
        brdg.push_back(Edge(u, v));
        tecomp.push_back(vector<int>());
        while (true) {
            int w = S.top(); S.pop(); inS[w] = false;
            tecomp.back().push_back(w);
            if (v == w) break;
        }
        roots.pop();
    }
}

void bridge(const Graph& g, Edges& brdg, vector< vector<int> >& tecomp) {
    const int n = (int)g.size();
    vector<int> num(n);
    vector<bool> inS(n);
    stack<int> roots, S;
    int time = 0;
    for (int u = 0; u < n; u++) if (num[u] == 0) {
        visit(g, u, n, brdg, tecomp, roots, S, inS, num, time);
        brdg.pop_back();
    }
}

template<int V>
struct LowestCommonAncestor {
    const static int LG = 25; //頂点の数のlogだけどVが2^25を超えることないしこれでよさ気
    int ro[LG][V]; //ro[i][j]で、頂点jの2^i親にあたる頂点を指す
    int dps[V]; //根からの深さ
    vector<int> g[V];
    /// i-jに有向辺を張る
    void add(int i, int j) {
        g[i].push_back(j);
        g[j].push_back(i);
    }
    //initで呼ばれるので無視して
    void dfs(int p, int b) {
        assert(ro[0][p] == -1);
        ro[0][p] = b;
        dps[p] = (b == -1) ? 0 : dps[b]+1;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs(d, p);
        }
    }
    /// 事前処理を行う rはroot頂点のid
    void init(int r) {
        memset(ro, -1, sizeof(ro));
        dfs(r, -1);
        for (int i = 0; i < LG-1; i++) {
            for (int j = 0; j < V; j++) {
                ro[i+1][j] = (ro[i][j] == -1) ? -1 : ro[i][ro[i][j]];
            }
        }
    }
    /// lとrの頂点のLCAを求める
    int query(int l, int r) const {
        if (dps[l] < dps[r]) swap(l, r);
        int dd = dps[l]-dps[r];
        for (int i = LG-1; i >= 0; i--) {
            if (dd < (1<<i)) continue;
            dd -= 1<<i;
            l = ro[i][l];
        }
        if (l == r) return l;
        for (int i = LG-1; i >= 0; i--) {
            if (ro[i][l] == ro[i][r]) continue;
            l = ro[i][l]; r = ro[i][r];
        }
        return ro[0][l];
    }
    int dist(int u, int v) const {
        int p = query(u, v);
        return (dps[u]-dps[p]) + (dps[v]-dps[p]);
    }
};

const int MAXN = 100010;
int A[MAXN];
LowestCommonAncestor<MAXN> LCA;

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

    int N,M;
    cin >> N >> M;
    Graph g(N);
    for(int i=0; i<M; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(Edge(x, y));
        g[y].push_back(Edge(y, x));
    }
    Edges brdg;
    vector< vector<int> > tecomp;
    bridge(g, brdg, tecomp);
    for(int i=0; i<len(tecomp); i++){
        for(auto el : tecomp[i]){
            A[el] = i;
        }
    }
    for(int i=0; i<len(brdg); i++){
        LCA.add(A[brdg[i].src], A[brdg[i].dst]);
    }
    LCA.init(0);
    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--; c--;
        if(A[a] == A[b] || A[b] == A[c]){
            cout << "OK" << endl;
            continue;
        }
        if(LCA.dist(A[a], A[b]) + LCA.dist(A[b], A[c]) == LCA.dist(A[a], A[c])){
            cout << "OK" << endl;
            continue;
        }
        cout << "NG" << endl;
    }
}