GraphvizとかVimとか

基本的に物事をすぐに忘れるので簡単なことでもメモ．

Graphvizとか

Graphviz
基本的に，
Graghvizでグラフ構造からグラフを描画する
にめちゃ詳しく書いてある．
ただコマンドによっては使えない属性があるので
http://www.graphviz.org/doc/info/attrs.html
で確認．

ノードの形

ノードの形はデフォルトにしていたけど，pointがいい感じに思える．

1

node [ shape = point];

ノードにlabelが欲しい場合は，defaultに戻す．

閉路を書きたい

dotではなく，cicroがいいかも

細かい調整

rankでsame，max，min，source，sinkを指定出来る．

1

{rank = same; hoge; hogehoge;}

見えない辺で調整とか．グラフは同型なんだけど，そうじゃない，という時．
例えば，下のグラフの左下のノードを上に持って行きたい．

辺を作って，rankを合わせる．作った辺を消す．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

graph g {
    node [
        shape = point;
    ];

    a [fixedsize = true, width = 0.01, height = 0.01, shape = point,color="#00000000"];
    b [fixedsize = true, width = 0.01, height = 0.01, shape = point,color="#00000000"];
    c [fixedsize = true, width = 0.01, height = 0.01, shape = point,color="#00000000"];
    d [fixedsize = true, width = 0.01, height = 0.01, shape = point,color="#00000000"];

    a -- b -- c -- d [style = invis];

    1 -- 3;
    1 -- 4;
    2 -- 3 -- 5;
    2 -- 4 -- 5;
  3 -- 4;

    {rank = same; a; 1;}
    {rank = same; b; 2;}
    {rank = same; c; 3; 4;}
    {rank = same; d; 5;}
}

表

動的計画法とかの状態遷移をgraphvizで書きたい（DPの練習問題が本当にたまたま解けたので，メモを残すの必死）．patchworkとかいいと思ったけど，辺が書けないみたいなので，osageでshapeをsquareに

グラフ理論の講義ノートを綺麗に



Vimとか

毎回，毎回 dot -Tpng hoge.dot -o hoge.png するのは面倒．quirkrunの設定に書く．

1
2
3
4

let g:quickrun_config['dot'] = {
\ 'command': 'dot',
\ 'exec': ['%c -T png %s -o %s:r.png', 'display %s:r.png']
\}

この設定で満足と思っていたが，こんな記事を見つけた．
emacsのgraphviz用モードをインストールする
emacsでは，pngのviewが出来る．これをしたい．

そうだ Vim で画像を表示させようを読む．この記事通りに設定して，
無事描画できた．この記事には

本来であれば XPM を用いて画像ファイルの描画を行うと Vim がかなり重くなるんですが、今回は別に起動している Vim で描画を行なっているのでレスポンスの重さはあまり気になりません。

とある．Vimが重くなることを考慮しなければファイル描画が可能？ココロオドル
helpを読むと，gvimの起動オプションを指定出来るみたいなので，

1

let g:sugarpot_gvim_cmd_option = '--serverlist GVIM --remote-tab-silent .'

的なことをして無理やり，dotをいじっているgvimに突っ込んでみる．フリーズする．ごめんなさい．sourceを読んでも全くわからないので諦める．

次にafterimage.vimを見つける．画像を開いてみる．
いつものフォントサイズで描画されてしまうので，小さく指定する．
そうすると，dotを書いているほうまで小さくなる（そりゃそうだ）．頭を悩ます．バッファごとにフォントサイズを変更出来たりしないか調べるがよく分からず．

TweetVimとかvimfiler でファイルのアイコンを表示させてみた見て，iconの表示をやってる所を見たら参考になるかも，と思いコードを読むも何一つ分からず．

まとめ

  • Graphvizいい感じだ
  • Vimでquickrunの設定した
  • 画像表示をいい感じに出来ず

モウダメダ（完）

Oct 25th, 2015
graphviz, vim

ARC043-B 難易度

難易度の2倍以上の問題に対して選ぶことが出来る．
まずは，難易度でソート．
今見ている問題数をiとすると，i+1問目でその問題を選ぶことが出来る場所に足していく．


縦を問題，横を問題数と見て，遷移出来る場所を見つけたい．これを愚直に探すと，探索にかかってしまう．しかし，難易度でソートされているので，lower_boundでで見つけることが出来る．最初に見つけた場所に足していって，累積和を取った．全体でで間に合う．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    ll vmax = 0;
    vector<ll> v(n);
    rep(i,n) {
        cin >> v[i];
        vmax = max(vmax, v[i]);
    }

    sort(v.begin(), v.end());

    ll cnt[100005][4];
    memset(cnt, 0, sizeof(cnt)) ;

    rep(i,n) {
        cnt[i][0]++;
    }

    rep(i,3) {
        rep(j,n) {
            if(v[j]*2 > vmax) continue;
            int id = lower_bound(v.begin(), v.end(), v[j]*2) - v.begin();

            cnt[id][i+1] += cnt[j][i];
            cnt[id][i+1] %= MOD;
        }

        REP(j,1,n) {
            cnt[j][i+1] += cnt[j-1][i+1];
            cnt[j][i+1] %= MOD;
        }
    }

    ll ans = 0;
    rep(i,n) {
        ans += cnt[i][3];
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

2倍するので，オーバーフローしてWA．llに直した時に，cntの初期化を消してしまったらしく，それに気づかずWAを連発してしまった．．．

Oct 25th, 2015
atcoder, 動的計画法

Codeforces322-div2D Three Logos

http://codeforces.com/contest/581/problem/D

3つのブロックが与えられる．これらのブロックを上手く配置して正方形が出来るかを調べる．出来る場合はABCで実際に並べて，出来ない場合は-1を出力する．

考察

この3つのブロックの中で最大の辺が必ず，求めたい正方形の1辺となる．よって3つを横に並べるパターンと，縦横に分けて並べるパターンに分けて，出来るかどうかの判断をした．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    vector<pair< pair<int,int>,int > > v(3);
    int len = 0;

    rep(i,3) {
        cin >> v[i].first.first >> v[i].first.second;
        v[i].second = i;

        if(v[i].first.first < v[i].first.second) {
            swap(v[i].first.first, v[i].first.second);
        }

        len = max(len , v[i].first.first);
    }

    sort(v.begin(), v.end(),greater<pair<P,int> >());

    int a = v[0].first.first, b = v[0].first.second;
    int c = v[1].first.first, d = v[1].first.second;
    int e = v[2].first.first, f = v[2].first.second;

    char A = char('A' + v[0].second);
    char B = char('A' + v[1].second);
    char C = char('A' + v[2].second);

    if(a == len && c == len && e == len) {
        if(b + d + f == len) {
            cout << len << endl;
            rep(i,b) {
                rep(j,a) cout << A;
                cout << endl;
            }

            rep(i,d) {
                rep(j,c) cout << B;
                cout << endl;
            }

            rep(i,f) {
                rep(j,e) cout << C;
                cout << endl;
            }
        } else {
            cout << -1 << endl;
        }
    } else {
        if(b + c == len && b + e == len && d + f == len) {
            cout << len << endl;
            rep(i,b) {
                rep(j,a) cout << A;
                cout << endl;
            }

            rep(i,c) {
                rep(j,d) cout << B;
                rep(j,f) cout << C;
                cout << endl;
            }
        }
        else if(b + d == len && b + e == len && c + f == len) {
            cout << len << endl;
            rep(i,b) {
                rep(j,a) cout << A;
                cout << endl;
            }

            rep(i,d) {
                rep(j,c) cout << B;
                rep(j,f) cout << C;
                cout << endl;
            }
        } else if(b + c == len && b + f == len && d + e == len) {
            cout << len << endl;
            rep(i,b) {
                rep(j,a) cout << A;
                cout << endl;
            }

            rep(i,c) {
                rep(j,d) cout << B;
                rep(j,e) cout << C;
                cout << endl;
            }
        } else if(b + d == len && b + f == len && c + e == len) {
            cout << len << endl;
            rep(i,b) {
                rep(j,a) cout << A;
                cout << endl;
            }

            rep(i,d) {
                rep(j,c) cout << B;
                rep(j,e) cout << C;
                cout << endl;
            }
        } else {
            cout << -1 << endl;
        }
    }

    return 0;
}
Oct 1st, 2015
codeforces

Codeforces322-div2C Developing Skills

http://codeforces.com/contest/581/problem/C

主人公は， 個のskillを持っている．が価値になる．killの値をだけ上げることが出来る時に，最大の価値の合計を求めよ．

考察

10刻みで1上がることが分かるので，次に価値が上がるまでいくら上げればいいかをpriority_queueに突っ込む．そしてこの値が小さい順にkを使って最大を計算する．それぞれのskillが100を超えてはいけないことに注意する（落ちた）．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n,k;
    cin >> n >> k;

    vector<int> v(n);
    rep(i,n) {
        cin >> v[i];
    }


    priority_queue<P, vector<P>, greater<P> > que;

    rep(i,n) {
        int d = v[i] % 10;
        que.push(P(10 - d,v[i]));
    }

    int ans = 0;
    while(k > 0 && que.size()) {
        P p = que.top();
        que.pop();

        if(p.second == 100) {
            ans += 10;
            continue;
        }

        if(k >= p.first) {
            que.push(P(10,p.second + p.first));
            k -= p.first;
        } else {
            p.first -= k;
            que.push(P(p.first, p.second+k));
            k = 0;
        }
    }

    while(que.size()) {
        P p = que.top();
        que.pop();

        ans += p.second / 10;
    }

    cout << ans << endl;

    return 0;
}
Sep 30th, 2015
codeforces, gready

Codeforces322-div2B Luxurious Houses

http://codeforces.com/contest/581/problem/B

建物の高さが与えられる．自分から見て，右側の建物より高くなるために必要な高さを答えよ．

考察

CodeFestival予選練習会で
http://code-festival-2014-qualb.contest.atcoder.jp/tasks/code_festival_qualB_d
を解いたばかりである．これはRMQだ，と思って実装した．
しかし，そんなことをする必要は無く，右から見ていき，現在見た所までの最大の高さを持っているだけで出来た．この方法は思いつかなかった．

Code

RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct RMQ {
    int n;
    vector<int> dat;

    RMQ(int n_) {
        n = 1;
        while(n < n_) n *= 2;

        dat.resize(n*4);
        rep(i,n*4) dat[i] = -INF;
    }

    void update(int k,int a) {
        int i = k+n-1;
        dat[i] = a;

        while(i > 0) {
            i = (i-1) / 2;
            dat[i] = max(dat[i*2+1],dat[i*2+2]);
        }
    }

    //[a,b)
    //query(a,b,0,0,n)
    int _query(int a,int b,int k,int l,int r)
    {
        if(r <= a || b <= l) return -INF;

        if(a <= l && r <= b) return dat[k];
        else {
            int vl = _query(a,b,k*2+1,l,(l+r)/2);
            int vr = _query(a,b,k*2+2,(l+r)/2,r);
            return max(vl,vr);
        }
    }

    //[a,b)
    int query(int a,int b) {
        return _query(a,b,0,0,n);
    }

};

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    RMQ rmq(n);
    rep(i,n) {
        cin >> v[i];
        rmq.update(i,v[i]);
    }

    rep(i,n) {
        int d = rmq.query(i,n+1);
        int d2 = rmq.query(i+1,n+1);

        if(d == v[i] && v[i] != d2) cout << 0;
        else cout << d+1 - v[i];

        if(i == n-1) cout << endl;
        else cout << " ";
    }

    return 0;
}

右から見て行く．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    rep(i,n) cin >> v[i];

    int vmax = 0;
    vector<int> ans(n);
    for(int i=n-1; i>=0; i--) {
        if(vmax < v[i]) ans[i] = 0;
        else ans[i] = vmax+1 - v[i];

        vmax = max(vmax,v[i]);
    }

    rep(i,n) {
        cout << ans[i];

        if(i ==n -1) cout << endl;
        else cout << " ";
    }

    return 0;
}

実装量がかなり違うので，出来るだけ実装が軽い方法を思いつけるようになりたい．

Sep 30th, 2015
codeforces, rmq

燻製をした

燻製をしたかったので，した．

まずは木炭に火をつける．

これがなかなかつかない．最近はこういうものがあるらしい．

ついた

今回使うチップはこれ

セット

燻製するもの

セット

待つ

待った

出来た

完成

美味かった

Sep 27th, 2015
料理

CodeFestival2015 予選a

振り返り

2分探索をバグらせる以前に，左に行って折り返すより，右に行ってから左に行く方がより効率がいいということに気づいていなかった．また2分探索の範囲も最初はrをn+1にしていたが，答えがnを超える時に対応できず，またでも足りず．
考察が十分に出来てないし，実装も出来ずでダメダメだった．結果として，166位．予選Bを頑張るのみ．

A - CODE FESTIVAL 2015

http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    string s;
    cin >> s;

    int len = s.size();
    rep(i,len-4) {
        cout << s[i];
    }

    cout << "2015" << endl;

    return 0;
}

B - とても長い文字列

http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n;
    cin >> n;

    ll ans = 0;
    rep(i,n) {
        int x;
        cin >> x;

        ans = ans * 2 + x;
    }

    cout << ans << endl;

    return 0;
}

C - 8月31日

http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n,t;
    cin >> n >> t;

    vector<int> a(n), b(n);
    vector<int> v(n);
    ll sum = 0;
    rep(i,n) {
        cin >> a[i] >> b[i];
        sum += a[i];
        v[i] = a[i] - b[i];
    }

    sort(v.begin(), v.end(), greater<int>());

    if(sum <= t){
        cout << 0 << endl;
        return 0;
    }

    bool flag = false;
    rep(i,n) {
        sum -= v[i];

        if(sum <= t) {
            flag = true;
            cout << i+1 << endl;
            break;
        }
    }

    if(!flag) cout << -1 << endl;
    return 0;
}

D - 壊れた電車

http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    ll n, m;
    cin >> n >> m;

    vector<ll> v;
    rep(i,m) {
        ll x;
        cin >> x;

        v.push_back(x);
    }

    if(n == m) {
        cout << 0 << endl;
        return 0;
    }

    ll l = 0, r = 5000000000;
    while(r-l > 1) {
        ll mid = (l+r) / 2;

        bool flag = true;

        ll now = 0;
        ll id = 0;

        while(id != m) {
            ll cnt = mid;

            if(now >= v[id]) {
                now = max(now, v[id] + cnt);
                id++;
                continue;
            }

            ll d = v[id] - now - 1;

            if(cnt >= d) {
                now = v[id] + max( cnt - d*2 , (cnt-d) / 2);
            } else {
                flag = false;
                break;
            }

            id++;
        }

        ll cur = n + 1;
        id = m-1;
        bool ch = true;

        while(id != -1) {
            ll cnt = mid;

            if(cur <= v[id]) {
                cur = min(cur, v[id] - cnt);
                id--;
                continue;
            }

            ll d = cur - v[id] - 1;

            if(cnt >= d*2) {
                cur = v[id] - min(cnt - d*2, (cnt-d) / 2);
            } else {
                ch = false;
                break;
            }

            id--;
        }

        if(flag && now >= n) {
            r = mid;
        } else if(ch && cur <= 1) {
            r = mid;
        }else {
            l = mid;
        }
    }

    cout << r << endl;
    return 0;
}
Sep 27th, 2015
codefestival2015

Yukicoder No.120 傾向と対策:門松列(その1)

http://yukicoder.me/problems/291

考察

自由に並び替えて良いため，関係あるのは長さの竹が何個あるか．sortして小さい順にとるような貪欲では例えば

の時に，{1,2,3}とペアを作ってしまうとペアが2つしか作れない．長さが違えばよいで，個数が多い順にとっていく貪欲で上手くいった．多い順に取るのはpriority_queueを使った．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int t;
    cin >> t;

    rep(q,t) {
        int n;
        cin >> n;

        vector<int> v(n);
        map<int,int> m;
        rep(i,n) {
            cin >> v[i];
            m[v[i]]++;
        }

        priority_queue<int> que;
        map<int,int>::iterator ite;
        for(ite = m.begin(); ite != m.end(); ite++) {
            que.push(ite->second);
        }

        int cnt = 0;
        while(que.size() > 2) {
            cnt++;
            vector<int> t(3);

            rep(i,3) {
                t[i] = que.top();
                que.pop();
            }

            rep(i,3) {
                if(t[i] == 1) continue;
                que.push(t[i]-1);
            }
        }

        cout << cnt << endl;

    }
    return 0;
}
Sep 3rd, 2015
yukicoder, 星2

Yukicoder No.118 門松列(2)

http://yukicoder.me/problems/221

考察

今回は与えられるA_{i}が100と小さいので，門松の要素の列挙が出来る．何組の選び方があるあを求めたいので，それぞれの長さが何本あるかを持っておき，一番小さいもの，真ん中，一番大きいものの個数をかける．探す範囲はN本与えられた長さの最小値から最大値までで行った．mod 109 + 7を忘れない．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define MOD 1000000007

using namespace std;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  
  vector<int> v(n);
    map<int,ll> m;
    int vmin = INF, vmax = 0;
    rep(i,n) {
        cin >> v[i];
        m[v[i]]++;

        vmin = min(vmin,v[i]);
        vmax = max(vmax,v[i]);
    }

    ll ans = 0;
    REP(i,vmin,vmax+1) {
        REP(j,i+1,vmax+1) {
            REP(k,j+1,vmax+1) {
                ans += m[i] * m[j] * m[k];
                ans %= MOD;
            }
        }
    }

    cout << ans << endl;


  return 0;
}
Sep 3rd, 2015
yukicoder, 星2

Yukicoder No.115 遠足のおやつ

http://yukicoder.me/problems/205

考察

買うK個の最小値と最大値を出す．

としてこの中に収まるようにする．辞書順最小にしたいので，左側からdownに近づけていき，その分を右側に持っていく．この操作を可能な限り行い，変化がなくなったら終了．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <cassert>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
    int n,d,k;
    cin >> n >> d >> k;

    int sum = 0, t = n;
    rep(i,k) {
        sum += t;
        t--;
    }

    if(d < (k*(k+1))/2 || d > sum) cout << -1 << endl;
    else {
        vector<int> v;
        rep(i,k) v.push_back(d/k);

        int cnt = d % k;
        rep(i,cnt) {
            v[i]++;
        }

        sort(v.begin(),v.end());

        vector<int> down(n), up(n);
        rep(i,n) {
            down[i] = i+1;
            up[i] = n-k+1+i;
        }

        while(true) {
            vector<int> temp(v.begin(),v.end());
            int s = 0, t = v.size()-1;

            while(true) {
                if(s == t) break;

                if(v[s] == down[s] || v[s] == up[s]) {
                    s++;
                    continue;
                }

                if(v[t] == up[t]) {
                    t--;
                    continue;
                }


                int diff;
                if(v[s] >= up[s]) {
                    diff = v[s] - up[s];
                } else {
                    diff = v[s] - down[s];
                }

                while(diff) {
                    if(v[t] + diff <= up[t]) {
                        v[s] -= diff;
                        v[t] += diff;
                        diff = 0;
                    }
                    else {
                        v[s] -= up[t] - v[t];
                        diff -= up[t] - v[t];
                        v[t] = up[t];
                        t--;
                    }

                    if(s == t) break;
                }

            }

            sort(v.begin(),v.end());

            bool flag = true;
            rep(i,k) {
                if(v[i] != temp[i]) flag = false;
            }

            if(flag) break;
        }

        rep(i,v.size()) {
            cout << v[i];

            if(i == v.size()-1) cout << endl;
            else cout << " ";
        }
    }

    return 0;
}
Sep 3rd, 2015
yukicoder, 星2