ACPC2018-参加記-

今年も参加しました。

Day 0

 移動中にHaskellをやっていました。関数型言語をやりたい&楽しそうだったのですが意外とむずかしい。。。継続していやっていきたい。

景色は相変わらずど田舎。　晩御飯はマルモ食堂で食べました。美味しかった。

Day1

ジャッジをやりました。大悪魔さんの自己紹介が面白かったです。ヅの食堂がおしゃれで美味しかったのが印象的でした。

Day2

imulanさんとnadareさんとチームを組みました。

AとCを解いてEとFの考察を行いました。

・C問題は足してmodを取れば嬉しいなぁとすぐ気づいたんですが、バグを仕込みそうだったのでimulanさんに確認してもらいながらAC

・F問題は似たような問題を見たことがあったので、nadareさんと相談しながらDijkstraやるだけでは？みたいな気持ちになる。

・imulanさんに↑の概要を伝えると、辺のコストに単調性がないと指摘を受ける。自分の考察力の無さと詰めの甘さを思い知りました。imulanさんが通してAC

・E問題はnadareさんと一緒に数学をやりました。自分一人でやってると詰められないところもnadareさんがしっかり詰めてくださってAC。途中は苦しかったんですが結果オーライ。

Day2 懇親会

・c7c7さんやprdさん、nadareさん、北大*1さん、UTの方と一緒のテーブルになりました。

・お酒を飲む方が多くてびっくりしました。初めてお会いしたとは思えなぐらい喋りました。

・競プロの懇親会だけあって、プログラミングのことが好きな方が多かったので、競プロ以外のプログラミングのことについても話しました。自分より強い方の話を伺う機会は多くないので貴重な体験でした。

Day3

tomaさんとshotさんでチームを組みました。

AとDと戦犯を担当しました。

・A問題を通すまで55分4WAをしました。引退案件です。

・DはDPがDijkstraかなぁと思った。DPはバグらせた思い出しかないので、shotさんに方針を確認してもらって拡張Dijkstraを書くがWA。

・d[0][0]の初期化を忘れていることに気づいてAC。

・shotさんが虐殺としていたBとEをACしてプロ。コーディング力見習いたいです。

・TomaさんはFをこれはA~Fの中で一番簡単といってAC。想定解ではない方法らしいです。

・最後の一時間にD,E,Fがポンポン通ったのが印象的でした。

最後に

三度目の参加となりましたが、とても楽しかったです。２年前と比べると成長しているようなしていないような。。。

チームを組んでくれた皆様、会津大学・北海道大学の皆様、ありがとうございました。

後期もしっかり精進していきたいと思います。

*1:実はこのときまで同学年の北大競プロerを一人も知りませんでした。

Mujin Contest D - うほょじご

問題文

D - うほょじご

解く前に考えていたこと

・絶対これ考察するだけでしょｗと思ってたら違った。
・規則性を見出すことが全くできなかった。シュミレーションの選択肢を除外した。

正解

・解答を見ると閉路を探し出すような解答になっていたが、わからなかったのでメモ化再起で解いた。
・なので、2次元配列で状態を持てる。
・無限ループに突入する部分の判定が勉強になった。

if(visit[x][y] > 0) return true;
        if(visit[x][y] < 0) return false;
        int tx = x,ty = y;
        visit[x][y] = true;
        x < y ? x = rev(x) : y = rev(y);
        x < y ? y = y - x  : x = x - y;
        if(x <= 0 or y <= 0){
            visit[tx][ty] = -1;
            return false;
        }
        visit[tx][ty] = (dfs(x,y) ? 1 : -1);
        return visit[tx][ty] == 1;

まず、に対し、に1を一時的に格納する。
に対して操作を行った後、閉路に突入する（つまり、に戻ってくる）と、格納されている1が帰る。
そうでない場合は途中で-1に更新され、その組は解になりえない事がわかる。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll

using namespace std;
int rev(int num){
    auto s = to_string(num);
    reverse(begin(s),end(s));
    return stol(s);
}
signed main(){
    int n,m;
    cin >> n >> m;
    int ans = 0;
    vector<vector<int>>visit(1000,vector<int>(1000,0));
    function<bool(int,int)> dfs = [&](int x, int y) -> bool{
        if(visit[x][y] > 0) return true;
        if(visit[x][y] < 0) return false;
        int tx = x,ty = y;
        visit[x][y] = true;
        x < y ? x = rev(x) : y = rev(y);
        x < y ? y = y - x  : x = x - y;
        if(x <= 0 or y <= 0){
            visit[tx][ty] = -1;
            return false;
        }
        visit[tx][ty] = (dfs(x,y) ? 1 : -1);
        return visit[tx][ty] == 1;
    };
    for(int i = n; i >= 1; --i){
        for(int j = m; j >=1;--j){
            ans += dfs(i,j);
        }
    }
    cout << ans << endl;
}

ABC106 AtCoder Express 2

問題

D - AtCoder Express 2

解く前に考えていたこと

区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。
実装の際に盛大にバグらせたので戒めとして書きました。

解法

+ クエリ先読みのオフラインアルゴリズムというらしい

#include<bits/stdc++.h>
using ll  = long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? 1e9:1e18)
using namespace std;
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using pii = pair<int,int>;
using piii = pair<int,pii>;

int bit [1000] = {},n;
int sum(int i){
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add (int i,int x){
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}
signed main(){
    int m,q; cin >> n >> m >> q;
    vector<piii>v( m + q);
    rep(i,m+q) {
        int a,b; cin >> a >> b;
        piii temp;
        temp.first = a, temp.second.first = b;
        temp.second.second = i;
        v[i] = temp;
    }
    sort (all(v),[](auto const x,auto const y) {
        return (
                x.second.first < y.second.first  or
                (x.second.first == y.second.first and x.second.second < y.second.second)
                );
    });
    int ans[100000] = {};
    erep(e,v){
        int left = e.first;
        int right = e.second.first;
        bool isQuery = e.second.second >= m;
        int index = e.second.second - m;
        if (isQuery){
            ans[index] =  sum(right) - sum (left - 1);
        } else {
            add(left, 1);
        }
    }
    rep(i,q) cout << ans[i] << endl;
}

9/6　追記
一応segtreeの解答も載せておこうかな
https://beta.atcoder.jp/contests/abc106/submissions/3096327

ABC038 D - プレゼント

問題概要

D - プレゼント

解く前に考えていたこと

・AOJのマトリョーシカと非常に似ている。
・ただし、この問題は制約がで解は部分点しか取れない。
・LISであることは間違えないので、比較関数を書き換えて蟻本にあるのLISを書くがWA
・途中でpair型dpを更新していた。

正解

まず前提として、プレゼントがプレゼントの中に梱包される条件とは、
> > 　が成立することである。
プレゼントの順番は自由に並びかえることができるので、ソートして考えるのが良い。
を昇順にソートして に関してLISを考えればうまくいきそう。
以下,二分探索で、番目の要素の更新位置を探す解法を考える。

・番目の要素でLISの配列を上書きする場合を考える。ただし、上書きされる要素は番目()とする。
・このとき、が成り立っていると、となっているため、上書きできない。（直感的に説明すると、番目の要素の方が番目の要素より条件が厳しい）

逆に言えば、のときとなっていれば、通常通り更新することができる。

追記

6/10 別解で解いたので、その解法を載せる.
通常のLISと同じく、lower_boundを用いて更新していく(ただし、今回はpair型のdp)。
更新する位置は、以上の要素がある部分である。
さて、この問題でより真に大きいとは、 && が成り立つことである。
さらに, 以上とは、 or となる。なので、適当に二分探索して置き換える位置を探す。
この定義を採用すると、同値のまたはの更新時に厄介なことになる。よって最初の同じく、比較関数をよしなにしてソートすること。

lower_boundといっておきながら普通の二分探索の理由は、また比較関数を書き換えないと行けないので。(比較関数を書き換えたver)

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr Int inf =1e18;
template<class F, class T>
auto  minimize(T imin,T imax,F &f){
    while(imax - imin > 1){
        T mid = imin + (imax - imin)/2;
        if(f(mid)) imax = mid;
        else imin = mid;
    }
    return imax;
}
int main(){
    int N; cin >> N;
    vector<pair<Int,Int>>v(N);
    for(auto& p : v)
        cin >> p.first >> p.second;
    sort(v.begin(),v.end(),[&](const auto& l, const auto& r){
        if(l.first == r.first) return l.second > r.second;
        return l.first < r.first;
    });
    pair<Int,Int>p;
    vector<pair<Int,Int>>dp(N,make_pair(inf,inf));
    auto f = [&](int mid){
        return dp[mid].first >= p.first or dp[mid].second >= p.second;
    };
    for(int i = 0; i < N; ++i){
        p = v[i];
        int id = minimize(-1,N - 1,f);
        dp[id] = p;
    }
    cout << count_if(dp.begin(), dp.end(), [&](auto p){
        return p != make_pair(inf,inf);
    }) <<  endl;
}
 

VimでIndentlineが動かなかった話

VimでIndentlineが動かなったのでメモ。
調べてみると、githubのIssueで報告されていました。
github.com
以下日本語でもメモを残しておきます。
まずターミナルで

vim --version

を実行します。すると、以下のような画面が現れるはずです。

ここで、-conceal となっているのが問題です*1。vimを入れ直しましょう。(画像では+になっています。)

brew install  vim

を実行して新しいVimを入れ直します。後は.bashrcにaliasを貼ると完成です。
以下の記事を参考にしていただけるとわかりやすいと思います。
qiita.com
qiita.com

*1:おそらくOS Xにもとから入ってるVimをお使いの方はほとんど-になっているハズです。

ICPC 2018国内予選

国内予選に後輩(わたあめくん)と先輩とともに参加しました。

開始１時間前

大雨の影響で大学までの電車がなかったので、大阪の別キャンパスで参加することになる。

yebiが到着　→　アナウンス「全館4時半で閉館です☆」（は？）

わたあめくんと合流して、帰宅難民向けに開放された食堂か近くのイ○ンの中にあるカフェのどちらかで参加しようとする。

先輩と合流してカフェのほうがおしゃれなのでカフェですることになる。このとき16:20。なんだこれは。

コンテスト

・開始してC問題を見る。累積和見るだけでしょとなる。

・気がつくと後輩がAを通す。プロ

・後輩にCを説明すると、累積を見るだけではヤバイことがわかる。bの制約的にしゃくとり法も間に合わなさそうで考察が振り出しに戻る。

・後輩がトイレに行ってる間に、bがN個に分割できるかどうか判定できることに気づく。後輩に伝えて実験してみると行けそうとなったので方針が固まる。

・Bが虚無そうだった。途中でBと交代してCを書く。５分ぐらいで書いてAC。

・先輩にBを任せてDを二人で考える。

・なんやこの制約、どうせ全探索やろ。

・いいえ、後輩くんに実装を任せてサンプルを試すも、実行時間が長すぎる。でもDPできなさそうなので迷う。

・よく考えると、勝利数は(N-1)/2の場合しかないことに気づく。枝刈りする。

・それでも間に合わない。

・先輩がBを通す。プロ

・Dをいろいろ考えてるうちにコンテストが終わった。

感想

後輩、先輩と自分のレートが大きく離れているので、自分の考察力や実装力で劣るのではないかと考えることが多々ありました（実際その場面はあった。）

ただ、自分の考察の甘いところをすぐに指摘してくれたり、ペアプロする上で、後輩・先輩のコーディングを見ることはとても勉強になりました。チームを組んでくれた先輩・後輩にとても感謝しています。

vectorsのテンプレートを詳しく見る

はじめに

競プロやってると、多次元のvectorをよく使うことがあります。非常に便利なんだけど、宣言がめんどくさい。
例えば、3次元のvectorを宣言しようとすると、

    vector<vector<vector<int>>>v(10,vector<vector<int>>(10,vector<int>(10,1000)));

こうなります。
4次元はもう書く気すらなくなってしまいます。しかしvectorsのテンプレートを用いると、

 auto v = vectors(10,10,10,3);

このように簡単に書くことができます。
個の引数に対して、最後の数値を初期値として次元のvectorを生成できます。
今回はこのテンプレートを詳しく見ていくことにします（勉強を兼ねて）

vectorsテンプレート

template<typename Head, typename Value>
 auto vectors(const Head &head, const Value &v) {
            return vector<Value>(head, v);
 }

template<typename Head, typename... Tail>
 auto vectors(Head x, Tail... tail) { 
       auto inner = vectors(tail...);
   return vector<decltype(inner)>(x, inner); }

vectorsのテンプレートは2つのvectorsという関数から成り立っています。
これを詳しく見ていきます。

可変引数テンプレート

任意のNについてvectorを生成するので、引数は毎度変化します。
これに対応するために、可変引数テンプレート*1が用いられています。
サンプルコードを見て見ましょう。

#include<bits/stdc++.h>
using namespace std;
template<class ...Args>
void func(Args... arg){
   //argの数を表示
    cout << sizeof...(arg) << endl;
}
template<class Head, class ...args> void func2 (Head a,args... b){
    cout << a  << endl;
    cout << sizeof...(b) << endl;
}
signed main(){
    func(1,2,3,4,5,6,7,8);
    func2(1,2.2,"3",'4');
   /* output:
      8
      1
      3
   */
}

可変引数テンプレートでは、任意の型と任意の引数をテンプレートとして利用することができます。
上記のfunc関数では
・Argsがテンプレートパラメータパック
・argsをが関数パラメータパック
となっています。それぞれ、推論された型、引数が格納されています。
関数内でパラメータパックを用いる際は ... を用いて展開します。
func2に注目してみると、引数として渡された引数が、Head 型の a　と　args型のbに分割されています。

この関数を繰り返し用いると、やがてargs...の引数は一つになります。
勘がいい方はすでに気づいているかもしれませんが、これは繰り返し処理に用いることができます。
具体例を示します。

#include<bits/stdc++.h>
using namespace std;
template<class Head, class args>    void func2 (Head a,args b){
    cout << a << endl;
    cout << b << endl;
}
template<class Head, class... args> void func2 (Head a,args... b){
    func2(b...);

}signed main(){;
    func2(1,2.2,"3",'4');
   /*output
    3
    4
   */

}

複数の引数が渡された関数は、再帰的にfunc2関数を呼び、最後に引数の引数の数は2つになります。
このように、関数をオーバーロードすることで、タグディスパッチによって最適な関数が呼び出されます。

decltypeについて

上記の知識とautoがsyntax sugarであることがわかれば、ほとんど中身が理解できる…かもしれませんが、最後にdecltypeだけ説明しておきます。
decltypeとは、指定した式から型取得する機能です。

#include<bits/stdc++.h>
using namespace std;
signed main(){
    cout << sizeof(decltype(2.2+ 3.4)) << endl; // decltypeはdouble型
    cout << sizeof(decltype('a' )) << endl;  //decltypeはchar 型
    cout << sizeof(decltype(2+1))<<endl; //decltypeはint型
    /* output
     8
     1
     4
     */
}

vectorsテンプレートでは、decltypeで取得した型とするvectorを返すことで、入れ子構造を達成しています。

参考

qiita.com
qiita.com
decltype(auto) - cpprefjp C++日本語リファレンス
SBクリエイティブ:C++テンプレートテクニック 第2版

*1:任意の数でテンプレートを引数をとれるテンプレートを宣言できる機能