そーすにっき

なんかいろいろのせておくばしょ

ICPCにっき 2018国内予選

久々の更新

1週間経って、正式順位も出たし、書こうかなと
自分はチームWArabimochiで出場して12位（通過順位11位）でアジア地区予選へ出場が決まりました。

チームWArabimochi
* ねこさん：つよいひと
* はとさん：超絶優秀な人
* ばぐ：自分（バグ埋め担当）

JAG

問題はこちら

はとさんが用事の為ねこさんと二人で参加

A

if文で2通りなのは自明だったけどソースコードで入力を受け取るとこまで書いてもにょりかける
大丈夫か自分とか自問自答しながらねこさんと話してるうちにif文が完成してAC

B

なんだこいつと一瞬空目したけど入力の形見たらそういうことねと理解して書く
問題の条件通りに書いたところif文が汚くなったが、あとから別チームの人に入力列Aの最後に1を追加すると条件1，2がまとめられると聞いてひっくり返る

C

パーサー書きたくないなぁ…と思っていたらねこさんが書くということで交代
D、E、Fにざっと目を通すがE、Fの内容を覚えきれなかった
というかDのsample outputを見て頭がこんがらがってるうちにねこさんAC

D

多倍長が必要かなぁと思ってうんざりしていたら、ねこさんから上の桁から順に確定できそうと聞いて思考がすっきりしてくる
この辺のきっかけを得るにはどうしたらいいのだろう
最初の1桁の確定は比較的簡単だったが2桁目の確定で少し間違う
が、さほどかからないうちに条件分岐を整理してたらとりあえず桁が確定できた
ここでねこさんが2つの数字が確定すると残りがbit列に対応していることに気づく
はいプロとか思いながら実装してab...(a,b:0~9,a!=b & a!=0)のケースは全て終わる
残りはaa...のケースになったところで1個桁を減らして再帰したいと意見が一致するも、かなり実装が長くなっていて、うんざりしかける
が、桁確定のif文の前に変数の値を書き換えてgotoすればいいのでは？と気づきこれでどうでしょと書く
ねこさん「ほんまか？」ばぐ「いけると思うんですよ」
というわけでコンパイルを通してみると大体合ってそうになる
最初の一桁が抜けていたのでもにょりかけるもねこさんの指摘通りgotoをずらすとサンプル全部通ってしまう
二人「ほんまかあ？」と言いながらテストケースを通すとサクッと出力が終わっていよいよ面白い顔になりながらSubmit→AC
二人で2～3分ばかし大爆笑する
クソコードを日々生産している自分のクソコード芸が変なところで役に立った模様

E

最初見たとき？？？という気持ちだったんだが二部グラフと言われてあっ…となり実装を書く
スタイリッシュに（ただ書きなれているだけ）グラフとDFS実装し貪欲彩色を完成させて最後もにょりかけて出力のとこで交代
10分余りで実装が終わり、何事もなくAC 二人でE先にやればよかった…と少し反省する

その後

Fが全く見えなかったのでGを見る
すぐにO(M)解が見えて実装したがサンプルの出力が終わらない
もう一度入力制約を見ると M\lt{10}^{10}
O(M)無理じゃんってなって残り10分だったので撤退 結果が20位（ゲスト除き15位）だったので希望半分ほんまか？半分という気持ちになる

前夜

大学で卒研のことでひとしきり悩んでからバイトへ
バイト先に搬入されていた自販機でレッドブルを購入し自宅の冷蔵庫にストック 西友でわらび餅とBLACKBLACKを購入
cpprefjpからコンテナのメンバ関数を忘れないようにと印刷して就寝

当日本番前

朝

丸々8時間寝て8:00起床　素晴らしい目覚め＋風呂で軽く寝汗を流す
朝ごはんを食べてから、持ち物を確認し11:30大学へ出発
すぐにラボの冷蔵庫にわらび餅とレッドブルとBLACKBLACKを冷やしてからトレーニングルームで体を起こす
昼飯にカツサンドを購入し食して、リハーサルを1問通してラボへ戻る

昼～開催前

ひとしきりやることが終わって14:30に会場の計算機室へ
なんかリハーサルがリセットされたと聞いて3問通してみようとする
1行読み込みを長いこと触っていなかったのでgetline(cin,str)を完全に忘れていて焦りに焦る
とりあえずstringstreamのparseと併せてサンプルコードを印刷しておく（完全に焦っている）
ギリギリで3問通したところで4問目が2015のD問題だなぁとか眺めてたらリハーサル時間が終了

国内予選中

今回は学内から６チーム参加ということで計算機室のプリンター割り当てを決める
うちは２部印刷するプリンターを引くことになった
とりあえずブラウザと時計をにらめっこして試合開始

A

すぐにmkdir a b c d e f g h みたいなのしてブラウザに目を向けるとすぐに２人から平均値以下という声と入力が整数という声が聞こえてすぐにemacsで入力開始
ガリガリ入力を書いてるうちにただ足してあとから割るだけと気づいてそのまま書き進めてコンパイル通してすぐにサンプルを通すと合ったのでそのままsubmitしたらAC 気づいたらFAが取れていたので順位表を見てきょどる

B~C

Bの入力を受け取ったところで冷える
とりあえず読んでいる２人に代わってもらうことにしてねこさんに交代
入力を受け取るところまで書いていることを伝えてCを読む
すぐにCは最悪O(b)で通そうという結論になりながらどうするか考える
はとさんが尺取りを考えたがやっぱりO(b)で辛そうとなる
自分は左端を決めると条件を満たす部分列の有無がO(1)であることが分かったが左端の分布が離散的なので二分探索できないとわかり悲しくなる
そうこうしているうちにねこさんがBをAC
CもねこさんがO(\sqrt{b})前後の解法をはやしていたのでコードを説明聞きながら書いてたら出来上がってAC

D~F

もにょってしまい入力受け取りコード生成機になってねこさんに交代
ねこさんが枝刈り全探索を再帰で書くことにしているのを見届けて後ろの問題を読むことにする
EはIEEE754だなぁと思いつつ微妙に違うし、と悲しい気持ちになってFを読む
Fは幾何にしか見えなかったのででかい三角形取って小さくしていく貪欲でいいんじゃないかと考える
G,Hは人間業で解ける問題に見えなかった
Dでねこさんが詰まりかけていたがすぐにはとさんのフォローが入りAC
よく見たら再帰関数の呼び出しが関数名が抜けて引数を返していた　-Wallオプションつけるかどうか、開始前にデバッグに付ければいいかなくらいの気持ちで同意してたけど付けたほうが無難かもしれないと思った
Eもねこさんが解法を生やしていてうそんとか思っていたらねこさんが「なにこれ！？」と声を上げる
ちらっとターミナルを見たら「浮動小数点例外」と出ていてバグ埋め界のtouristの面目躍如とばかりに「ゼロ除算じゃないですか？」と当てずっぽうに言ったところ思い当たる節があったらしくすぐにねこさんが修正してsubmit　ACしたところで突破しそうだねという空気になって一瞬気が抜ける
Fは幾何慣れしていないせいで実装が厳しすぎた
ライブラリを印刷していたがよく分からんライブラリを持つものじゃないなぁと思っているうちにタイムアップ
最後に去年同様HにWA Submitして気持ちよくなるも、HにWAしてるチームが別に居たので「全部やればよかったー！」と叫ぶ

大会後

終わってみるとなんか１２位で焦る
あとFAの結果企業賞が２つもらえるような空気でうれしくなる
お酒を３時まで飲み明かし帰宅
途中顔が赤黒いとか言われていたが顔色もまたバグっているので致し方なし
わらび餅はおいしく食べるはずだったのだが、まさかの切られていないわらび餅だったことが発覚
頑張って切ってきなこかけたがきなこが結構飛んだ（申し訳ない…）

感想（反省）

幾何はもう少し詰めないと話にならないという気持ちなのでAOJのLibrary of Geometryから埋めようかしら…（遠い目）
Fが難しいはそれはそうとして
あとAtcoder青が近いのでアジアまでには青にします（真顔）
大学の生協食堂のテレビにFA取った時の順位表の写真が上がるかもしれないって噂を聞いて戦慄してる

10-Year-Old Dynamic Programming

10-Year-Old Dynamic Programming | Aizu Online Judge

ICPC　600点問題

問題概要
・(0,0)から(N,M)への移動方法の数を求める
・但し最短ではなく、K回左か下に移動する
・第一象限しか移動できない

制約
1<=N,M<=100000,0<=K<=10000

解法
とりあえず上下や左右はさておいてx,y軸の移動に分ける
K回の寄り道を縦と横に分配する
x軸方向にi回寄り道するとx軸方向にはN+i回移動しないといけないので合計でN+2i回移動することになる
y軸方向はK-i回寄り道となるのでM+K-i回y軸方向に移動する　よって合計でM+2(k-i)回の移動になる
この移動方法の場合の数はK=0の要領で求められて{}_{N+M+2K}C_{N+2i}
後は各軸方向の移動の順番を定める
この時負座標を各軸方向で取れないことに注意すると
x軸方向は{}_{N+2i}C_{i}-{}_{N+2i}C_{i-1}となる
（正直ここがあんまり良くわかってないが小ケースで手計算から推測した）
y軸方向も同様に求めて各iについての和をとれば解が求まる

…が実際は1000000007のmodを取る際にnCrをn/1 * (n-1)/2 *... の方法で求めると割り算の回数が増える関係で非常に効率が悪いという問題があり数回TLE
N+M+2K = 220000（実装は499999まで計算してある）までのfactorialのmod計算して割り算を1回にした方が速かった

#include <bits/stdc++.h>
 
using i64 = int64_t;
using namespace std;
const i64 MOD = 1000000007LL;
vector<i64> fact(500000);
 
inline i64 powermod(i64 a,i64 b){
  i64 r = 1LL;
  for(int i = 32 - __builtin_clz(b) - 1; i >= 0; i-- ){
    if((1 << i) & b) r = r * r % MOD * a % MOD;
    else r = r * r % MOD;
  }
  return r;
}
 
inline i64 divmod(i64 a,i64 b){
  return a * powermod(b,MOD-2) % MOD;
}
 
i64 nCr(i64 n,i64 r){
  if(r<0)return 0;
  i64 ne = fact[n];
  i64 di = fact[n-r] * fact[r] % MOD;
  return divmod(ne,di);
}
 
inline i64 A(i64 a,i64 b){
  return (nCr(a,b) + MOD - nCr(a,b-1)  ) % MOD;
}
 
int main() {
  i64 N,M,K;
  cin >> N >> M >> K;
   
  fact[0] = fact[1] = 1LL;
  for(int i = 2;i < 500000;i++){
    fact[i] = fact[i-1] * (i64)i % MOD;
  }
   
  i64 res = 0LL;
  for(i64 i = 0LL; i <= K; i++ ){
    res += nCr(N+M+K+K,N+i*2) * A(N+i*2,i) % MOD * A(M+(K-i)*2,K-i) % MOD;
    res %= MOD;
  }
   
  cout << res << endl;
}

グラフのライブラリづくり(2/2 Updated)

遅い

概要

  • Dijkstra法, Bellman-Ford法, SPFA, Kruscal法, Unionfindを実装
  • Dijkstra法, Bellman-Ford法, SPFAのverify
  • Bellman-Ford法, SPFAの速度比較

モチベーション

  • いつも空で書いてたけど明らかに時間＆労力の無駄で、バグも埋めるから作ってしまおうという気持ち
  • （Dijkstra法はそもそも書いたことがなかったが解けていない問題埋めに必要だった）

verify

とりあえず

ついでにSPFAとBellman-Ford法の速度比較も
雑に1回だけ実行してtimeで計測
入力はこれを拝借しました
もちろんのことながらいずれもTLEの範囲

Bellman-Ford法

real 0m53.746s
user 0m53.704s
sys 0m0.040s

SPFA

real 0m46.151s
user 0m45.996s
sys 0m0.044s

やはりSPFAに軍配が上がった模様
むしろ上がらなかったらどうしようかと

Todo

  • Unionfind
  • フロー周り（あんまり実装しているものがないのでどうしよう）

コード（需要あるのか）

(2/2 流石に何も書いてないのは雑だなと思い）

  • edge
    • 辺データ（雑）
    • idは便利変数としてとりあえず設置 今後フローとか色々に使えるかなと
  • graph
    • add_edgeとsize()を持っただけのただのvector>
    • 2次元にしている理由は隣接リストの方が気持ちがよいから
    • size()を設置した理由はg.data.size()をg.size()と誤射するパターンが多い為（文字数も減るし）
  • dijkstra
    • バグ埋まってそう（もし見つけたら教えてください）
    • これ書く直前にspfaのqueueをpriority_queueにすればいいだけで実装できることに気づきげんなりした
  • spfa
    • みんな大好きSPFA（嘘）
    • いつもSPSP問題はこれにしていたけども、Dijkstra法じゃないとTLEする制約が厳しい問題が解けなくて困っていた…が、上記の理由によりこれからDijkstra法に逃げそう
  • bellmanford
    • みんな大好きBellman-Ford法（きっとこれは本当）
    • 負辺見つけられるよやったね！でもSPFAより遅いね！という気持ち
template<typename T>
struct edge{
    int f,t;
    T c;
    int id;
    edge(){};
    edge(int f,int t,T c,int id = 0):f(f),t(t),c(c),id(id){};
    bool operator< (const edge &s){
        return c < s.c;
    }
};

template<typename T>
struct graph{
    std::vector<std::vector<edge<T> > > data;
    graph(int v):data(v){};
    void add_edge(edge<T> &e){
        data[e.f].push_back(e);
    }
    void add_edge(int f,int t,T c){
        data[f].emplace_back(f,t,c);
    }
    size_t size(){
        return data.size();
    }
    std::vector<edge<T>> make_edges(){
        std::vector<edge<T>> r;
        for(auto &i:data)std::copy(i.begin(),i.end(),std::back_inserter(r));
        return r;
    }
};

template<typename T>
std::vector<T> dijkstra(graph<T> &g,int s){
    using state = std::pair<T,int>;
    //priority_queue
    std::priority_queue<state,std::vector<state>,std::greater<state>> q;
    q.emplace((T)0,s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max());
    data[s] = (T)0;
    //solve
    while(!q.empty()){
        state cur = q.top();q.pop();
        T c = cur.first; int pos = cur.second;
        if(data[pos] < c)continue;
        for(auto &e : g.data[pos]){
            if(c + e.c < data[e.t]){
                data[e.t] = c + e.c;
                q.emplace(c + e.c, e.t);
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> spfa(graph<T> &g,int s){
    //queue
    std::queue<int> q;
    q.emplace(s);
    //data init
    std::vector<T> data(g.size(),std::numeric_limits<T>::max()/4);
    std::vector<bool> isq(g.size(),false);
    std::vector<int> count(g.size(),0);
    data[s] = (T)0;isq[s] = true;++count[s];
    //solve
    while(!q.empty()){
        int cur = q.front();q.pop();
        isq[cur] = false;
        for(auto &e:g.data[cur]){
            if(data[e.f] + e.c < data[e.t]){
                data[e.t] = data[e.f] + e.c;
                if(++count[e.t]>=g.size()){
                    fill(data.begin(),data.end(),std::numeric_limits<T>::min());
                    return data;
                }
                if(!isq[e.t]){
                    q.push(e.t);
                    isq[e.t] = true;
                }
            }
        }
    }
    return data;
}

template<typename T>
std::vector<T> bellmanford(graph<T> &g, int s){
    const T INF = std::numeric_limits<T>::max()/4;
    std::vector<T> data(g.size(),INF);
    data[s] = 0;
    for(int i=0;i<g.size()-1;i++){
        for(auto &v:g.data)for(auto &e:v){
            if(data[e.f]==INF)continue;
            data[e.t] = std::min(data[e.f] + e.c,data[e.t]);
        }
    }
    for(auto &v:g.data)for(auto &e:v){
        if(data[e.f]==INF)continue;        
        if(data[e.f] + e.c < data[e.t]){
            fill(data.begin(),data.end(),std::numeric_limits<T>::min());
            break;
        }
    }
    return data;
}

POJ 1990 - MooFest

久々のソースコード投稿になりますん

問題：

一次元直線上に一列に並んだ牛に座標x_i,値v_iが与えられる

\sum_{i \in N, j \in N} max(v_i,v_j) | x_i - x_j |

の値を求めよ.

問題の難しい点：

簡単に見えて制約が厳しい.

|N| = 20000,x \ in {1,2,\cdots,20000}(\Leftrightarrow |x| = 20000 = |N|), time = 1000ms

この制約上＋POJでは O(|N|^2)が許されない.

そこでどうにかしてやる必要がある.

解法：

色々方法はあると思うけどとりあえずセグ木でRange Sum Queryをすることにした.

\sum_{i \in N, j \in N} max(v_i,v_j) | x_i - x_j |

はv_i < v_jの下で

\sum_{i \in N, j \in N,v_i < v_j} v_j | x_i - x_j |

であるからとりあえずvで昇順ソートして以下 i < j とする.

次にx_i < x_j であるiの集合を L_j , 補集合をR_j とおく.すると

\sum_{j \in N} \left( v_j \left( |L_j| x_j - \sum_{i \in N, j \in N, i \in L_j} x_i \right) + v_j \left( \sum_{i \in N, j \in N, i \in R_j} x_i - (|R_j|) x_j \right) \right)

|L_j|,\sum_{i \in N, j \in N, i \in L_j} x_i はそれぞれRSQにデータを保持すると更新、算出共にO(log |x|)で計算できる(R_j側についても同様).

これを j \in Nについてfor文を回すということで全体O(|N|log|x|)で計算可能.制約より |N| = |x|なのでこれなら定数が重くない限り制限時間内に間に合う.

若干添字周りに\pm 1が入るかもしれないが気にしない

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
class segtree_sum
{
  public:
    vector<T> data;
    int size;
    segtree_sum<T>(int size_) : size(1)
    {
        while (size < size_)
            size <<= 1;
        data.assign(size * 2, 0);
    }
    segtree_sum<T>(vector<T> &src) : size(1)
    {
        while (size < src.size())
            size <<= 1;
        data.assign(size * 2, 0);
        for (int i = 0; i < src.size(); i++)
        {
            update(i, src[i]);
        }
    };
    void update(int idx, int v)
    {
        int f = idx + size - 1;
        data[f] = v;
        while (f)
        {
            --f /= 2;
            data[f] = data[2 * f + 1] + data[2 * f + 2];
        }
    }
    T rsum(int l, int r)
    { //return sum[l,r)
        int f = l + size - 1;
        int k = 1;
        while (f % 2 && l + k * 2 <= r)
        {
            f /= 2;
            k *= 2;
        }
        if (l + k > r)
            return 0;
        else if (l + k == r)
            return data[f];
        else
            return data[f] + rsum(l + k, r);
    }
};

/////////////////////////////////////////////////////////////////////////

bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

#define i64 long long int

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > moo(n);
    for (int i = 0; i < n; i++)
    {
        cin >> moo[i].first >> moo[i].second;
    }
    sort(moo.begin(), moo.end(), compare);
    segtree_sum<int> l_cows(20010);
    segtree_sum<int> l_x(20010);
    i64 res = 0LL;
    for (int i = 0; i < n; i++)
    {
        int moot = moo[i].first;
        int moox = moo[i].second;
        i64 lcows = (i64)l_cows.rsum(1, moox);
        i64 lx = (i64)l_x.rsum(1, moox);
        i64 rx = (i64)l_x.rsum(moox + 1, 20001);
        res += (i64)(lcows * moox - lx) * moot;
        res += (i64)(rx - (i - lcows) * moox) * moot;
        l_cows.update(moox, 1);
        l_x.update(moox, moox);
    }
    cout << res << endl;
}

久々に記事書いた気がする

あけましておめでとうございます（遅）

あけましておめでとうございます（6日遅れ）

1月7日だけどあけましておめでとうございます

今年の目標を暢気に載せておきます

  • ちゃんと大学を卒業する（卒研が心配でたまらない人）
  • Atcoder青になる（出来ればICPCの前に！）
  • ICPCつくば予選50位以内を目指す（要はDをACしたい）
  • DDCC、CODE (THANKS) FESTIVALに出る（優遇年次を外れたので難易度UP）
  • Ruby、Pythonをちゃんと読み書きできる人間になる（特にPython）

後は記事にならないネタとして

  • 独検4級以上を取得する（一度ドイツにビールではなくワインを飲みに行きたい）
  • C++refを全部読む（予約語全部覚えて使える程度にはなりたい）

なんてのも一応