うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ハーフパイプ(2) 解説?

今回、testerをさせていただきました。

問題はこちら
No.398 ハーフパイプ(2) - yukicoder

まずはwriterさんの解説をご覧ください
http://yukicoder.me/problems/no/398/editorial


この問題、想定解法は埋め込みです。testerで問題をもらった時 6*100*100*600*100 = 36億 から落ちないよぉふぇぇ... ってなって解説をカンニングして、は〜〜〜、ってなった記憶があります。


ただ、ちゃんと定数倍改善を行えばこのオーダーでも C++ で 250ms, C# で 900ms で通る(かつ埋め込みのための列挙がほぼ同じ時間でできる!)ようになります。まずはその解説から。


まず dp[index][min][max][sum] というDPを考えます。これの更新式は以下のようになります。

for m in {0..100}:
dp[i + 1][min(j, m)][max(k, m)][l + m] += dp[i][j][k][l]


初期化については、一番左に置く数について埋め込み、

dp[0][i][i][i] = 1

としてしまうのが楽だと思います。


このdpの場合、
sum = x * 4とし、

for i in {0..100}:
for j in {i..100}:
ans += dp[5][i][j][sum + i + j]

とした ans が求めるものです。


このままやるともちろんTLEしますが、端的に言うと dp[i][j][k][l] == 0 の場合に m のループに入らないようにすれば良いです。

というのも、dp[i][j][k][l] == 0 となる場合が(定数倍の範囲内ですが)そこそこあり、その時に内側のループに入らないようにしてあげればループ回数がおよそ1億回ほどになり、C++等で通ります。C#でも1300msほどで通りましたが、Python等の言語では厳しいと思います。
(参考 : http://yukicoder.me/submissions/103388,
   : http://yukicoder.me/submissions/103389,
   : http://yukicoder.me/submissions/103496)
また、dp[i][j][k][l] > 0 となる l の範囲は連続なので、そこだけループを回すようにしてあげればもう少し早くなります。
(参考 : http://yukicoder.me/submissions/103467,
   : http://yukicoder.me/submissions/103495)

dp[i][min][max][sum] > 0 なる sum の 範囲は、
最小値が min + max + max + ... + max = min + max * i,
最大値が min + ... + min + min + max = min * i + max となるので、そこだけ回すとC++で250ms, C#で900msほどになります。


まぁ詳しくはソースコードを読んでください。



さて、そして問題のなんか場合分けして速いの(http://yukicoder.me/submissions/103511)についてですが、オーダーとしては 100^3 です。


やってることとしては単純で、

a + b + c + d + sum && a <= b <= c <= d

なる (a,b,c,d) を全探索し、一つ一つに対して min <= a なる min と d <= max なる max を追加した時の並べ方の場合の数を数え上げています。


min と max については、
・min == a && d == max
・min < a && d == max
・min == a && d < max
・min < a && d < max

の 4通りだけ調べればOK。


並べ方の場合の数については、

{a,a,a,a,a,a} : 1
{a,a,a,a,a,b} : 6C1 = 6
{a,a,a,a,b,b} : 6C2 = 15
{a,a,a,b,b,b} : 6C3 = 20
{a,a,a,a,b,c} : 6P2 = 30
{a,a,a,b,b,c} : 6C1 * 5C2 = 60
{a,a,b,b,c,c} : 6C2 * 4C2 = 90
{a,a,a,b,c,d} : 6P3 = 120
{a,a,b,b,c,d} : 6P2 * 4C2 = 180
{a,a,b,c,d,e} : 6P4 = 360
{a,b,c,d,e,f} : 6P5 = 720

となります(実際に解いた時に用いたメモを紛失したので間違ってるかも...、変なとこあったら教えてください><)


あとはこれを落ち着いてコードに起こすと、以下のコードになります。

#include <iostream>
using namespace std;

int main() {
    int a, b;
    scanf("%d.%d", &a, &b);
    int sum = (a * 100 + b) / 25;
    long long ans = 0;
    
    for (int i = 0; i < 101; ++i) {
        for (int j = i; j < 101; ++j) {
            for (int k = j; k < 101; ++k) {
                int l = sum - i - j - k;
                if (l < k) break;
                if (l > 100) continue;
                
                int m = 100 - l;
                if      (i < j && j < k && k < l)
                    ans += 180 + (i + m) * 360 + i * m * 720;
                else if (i == j && j < k && k < l)
                    ans += 60 + i * 180 + m * 120 + i * m * 360;
                else if (i < j && j == k && k < l)
                    ans += 90 + (i + m) * 180 + i * m * 360;
                else if (i < j && j < k && k == l)
                    ans += 60 + i * 120 + m * 180 + i * m * 360;
                else if (i == j && j < k && k == l)
                    ans += 20 + (i + m) * 60 + i * m * 180;
                else if (i == j && j == k && k < l)
                    ans += 15 + i * 60 + m * 30 + i * m * 120;
                else if (i < j && j == k && k == l)
                    ans += 15 + i * 30 + m * 60 + i * m * 120;
                else if (i == j && j == k && k == l)
                    ans += 1 + (i + m) * 6 + i * m * 30;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

もしこれが想定解法として提示されたら窓からMacBookAirを投げ出すレベルの解法ですが...
まぁこんな面倒くさい場合分け、競プロerだとあんまりしないですけど、そこまで競プロになれてない人だと逆にこっちで頑張るのが自然かも、とも思いました。

Segment treeを整備したという日記

(2019/10 追記:自分のライブラリを GitHub で管理するようにし始めたので、最新版が以下から参照できます)
github.com




最近Sumsegtreeを使う問題を解いたら、持ってたSumsegtreeがバグってたので、ついでにもっと色々使えるように手直ししたのでその備忘録みたいなものを書きます。
c#でのsegtreeのコード載せてるページ少ないし、ね。


なお、基本的に秋葉大先生のスライドをとても参考にさせていただいて作っているので俺の記事は読まなくていいのでこちらをお読みください
プログラミングコンテストでのデータ構造


以下コードです。

using System;

class Segtree<T>
{
    int n;
    T[] tree;
    Func<T, T, T> f;
    T exnum;
    public Segtree(int m, Func<T, T, T> f, T ex)
    {
        this.f = f;
        this.exnum = ex;
        n = 1;
        while (n < m) n <<= 1;

        tree = new T[(n << 1) - 1];
        for (int i = 0; i < tree.Length; i++) tree[i] = ex;
    }
    public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex)
    {
        for (int i = 0; i < m; ++i) tree[i + n - 1] = ini;
        all_update();
    }
    public void assign_without_update(int j, T x)
    {
        tree[j + n - 1] = x;
    }
    public void update(int j, T x)
    {
        int i = j + n - 1;
        tree[i] = x;
        while (i > 0)
        {
            i = (i - 1) >> 1;
            tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]);
        }
    }
    public void all_update()
    {
        for (int i = n - 2; i >= 0; i--)
            tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]);
    }
    public T look(int i) { return tree[i + n - 1]; }

    // [s, t)
    public T run(int s, int t) { return query(s, t, 0, 0, n); }
    T query(int s, int t, int k, int l, int r)
    {
        if (r <= s || t <= l) return exnum;
        if (s <= l && r <= t) return tree[k];

        return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r));
    }
}

(2016/04/19 : iniが指定されていない時にexnumで初期化するように設定しました)
(2016/10/03 : 色々細かいところを修正したのと、全体の初期化を {O(N \log N)} でなく {O(N)} で実現するための関数を追加、あと半開区間にしました!)

まず、型を自由に指定できるようにしてあります、これは基本的にはlongにしとけばどうにかなるのであんま意味ない気もしますが、doubleにしたい時とか
D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
とかだとまぁ楽かなぁという気がします。


それでは、変数の解説をしていくと、

・Func f
Func f は更新操作で用いる関数です。例えば、Sumsegtreeにしたい時は、ラムダ式で (i, j) => i + j などと与えてあげれば良いです。
また、MaxとかMinだと Math.Max とか Math.Min を渡してあげるだけで動きます、嬉しい。
その他でも、f(x1, f(x2, x3)) = f(f(x1, x2), x3) を満たす関数なら動くのかな...? 理学部じゃないのでわからん。

・T exnum
exnum は、区間が範囲外の時に返す値を入れる変数で、とても弱い値を入れておけばokです。例えば、Sumの時は0, Maxの時は-∞, Minの時は+∞, といったように。

・T ini
ini は、初期化用変数です。別にいらないような気もするかもですが、Tがclassだったりすると馬鹿みたいにランタイムエラーを起こすのであったほうが良いです。


あとは前述したスライドとほぼ同じなので、これで使えます。
一番の肝はコンストラクタで初期化する時で、そこがちゃんと出来てしまえばあとは毎回同じように使えます。めっちゃ嬉しい。


こちらが使用例になります。
Submission #694898 - AtCoder Regular Contest 033 | AtCoder
Submission #694924 - AtCoder Regular Contest 008 | AtCoder
#118362 No.426 往復漸化式 - yukicoder
(2016/10/03 : 使用例を追加しました)


最小費用流とか平衡二分探索木とかも持っとかなきゃなぁという気はしてる(書く気は起きない)。

No.335 門松宝くじ, No.336 門松列列

奇跡的に全完できたけど、普通にクソ苦手なセットだった
門松列の流行早く終わってくれ

No.335 門松宝くじ - yukicoder
No.336 門松列列 - yukicoder



門松宝くじは、当確率である2つの数字が選ばれたとき、3つの数字が門松列かつ3つの数字のmaxが最大になるようにもう1つの数字を選ぶようにして、そのときのmaxの期待値を出す問題(自分でも何を言っているのかわからない…)

普通に全部の選ばれる数字の組({_nC_2}通り)に対して ({n-2})通り全探索すると {O(n^3)} となりダメ(最初、800^3 = 2400万だと勘違いしてこれで出した)


そこで、選ばれた2つの数字について具体的に考えていきます

  • 選ばれた2数a, b(a < b)について、元の順列におけるindexが index[a] < index[b] のとき

下図(横軸 : index, 縦軸 : 数値)で適当に赤く塗られたところの数をあと一つの数として選べば、3数は門松列になります
f:id:riantkb:20160118132310p:plain

ここから、実は区間のMaxとminさえ持っていれば良いことがわかります

max[i][j]を区間[i, j]におけるMax、min[i][j]を区間[i, j]におけるminとすると、

max[0][index[b] - 1] > b のとき ...... 得点は max[0][index[b] - 1]
max[0][index[a] - 1] > a のとき ...... 得点は b
min[index[b] + 1][n - 1] < b のとき ...... 得点は b
min[index[a] + 1][n - 1] < a のとき ...... 得点は b
上のいずれにも適さないとき ...... 門松列を作れないので得点は 0

max[i][j], min[i][j] を前もって {O(n^2)} で求めておけば、各組に対して定数時間で求めることができ、結果 {O(m n^2)} となります

index[b] < index[a] のときも同じような感じで求めることができます



門松列列は、順列の並び替えの中でジグザグな列は何通りあるか、という問題
(どっかで見たことある気がするけど、題意は {a_i < a_{i + 1} < a_{i + 2}} または {a_i > a_{i + 1} > a_{i + 2}} となる i が存在しないことと同義)


まぁ、DPを考えます。


i - 1番目の数がi番目の数より大きかったかどうかで、i + 1番目にどのような数を置けるかが決まります
(例えば ......, 6, 4 というところまで数列を作っていたら、次の数は5以上でなければならない)


使える数字は決まっていて、一度使った数字は使えないので、次に置ける数字がm個、次に置けない数字がn個だとすると下図のようになります
f:id:riantkb:20160118135420p:plain

このとき、次のような漸化式が成り立ちます

dp[m + n][m] = dp[m + n - 1][n] + dp[m + n - 1][n + 1] + ... + dp[m + n - 1][m + n - 1] (dp[0][0] = 1)
(dp[m + n - 1][k] は、次に置ける数の中でk - n + 1番目に小さい数を選んだときの場合の数)


これをこのままループを回すと {O(N^3)} となりますが、
sum[i][j] = {\sum_{k = 0}^{j - 1}} dp[i][k]
を順次求めておけば {O(N^2)} となり、間に合います


求めるものは、sum[N - 1][N] * 2 です


なんかすごい変なDPをしている自覚はあります......


それぞれ、提出はこんな感じです
#71404 No.335 門松宝くじ - yukicoder
#71459 No.336 門松列列 - yukicoder

(P,Q)-サンタと街の子供たち 解説(?)

なんかめっちゃ面白い問題だなぁ、と思いかつ上手くハマって解けたので、つたないですが解説記事を書かせていただきます。
(お昼に間違ってフライング投稿しちゃってて慌てて非公開にしましたごめんなさい><)


問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder


ナイトはチェス盤のすべてのマスに到達できるが、それ以外の距離の移動のみではどうなるか? というもの


まずは、例外処理から(以下、{p \leq q} とし、各座標はすでに絶対値を取ってあることとします)

  • (p, q) = (0, 0) のとき

自明に動けないので、 {(x_i, y_i) = (0, 0)} となる点がいくつあるか探します( {i \neq j \Rightarrow (x_i, y_i) \neq (x_j, y_j)} が書いてなかったように思うのですが、できればどちらか明記していただけるとありがたかったかも、書いてあったらごめんなさい>< )。

  • p = 0 のとき

{gcd(x_i, y_i) \% q = 0} ならばいけるので探します。

  • gcd(p, q) > 1 のとき

必要条件として、{gcd(x_i, y_i) \% gcd(p, q) = 0} が挙げられます。かつ、p, q が互いに素となる状態にして後述の条件を満たすか判別すればよいです。

  • p, q が互いに素のとき

とりあえず、チェス盤を考えます。
f:id:riantkb:20151214140311p:plain

まず、ナイトと同じな (p, q) = (1, 2) のときを考えると、最初は (0, 0) の白マスにいて、移動した先は必ず黒マスになっています。
次に、(p, q) = (1, 3) を考えると、白マスにしか到達することができず、絶対に黒マスに到達することができません。


ここで、次のような仮定をすることができます。

「すべてのマスに到達できる ⇔ gcd(p, q) == 1 かつ (p + q) % 2 == 1」
 かつ、
「gcd(p, q) == 1 かつ (p + q) % 2 == 0 ⇔ すべての白マス( (x + y) % 2 == 0 ) に到達できる」

本番では、私はこれを証明せずに投げて通してしまいました。


ここに証明を書いてもいいのですが、writerさんが解説ページで証明っぽいのをなされているのでここでは割愛させていただきます(めんどいし)。
http://yukicoder.me/problems/849/editorial


23分ほどでACし、7番目くらいでした。あんまこじらせないでさっと行けてよかった……。

自分の提出
http://yukicoder.me/submissions/65503

happy b1rthday 2 me 解説

Advent Calender Contest 12日目の問題を担当しました、はい。

コンテストページ
順位表- yukicoder

問題
No.319 happy b1rthday 2 me - yukicoder


解説はこちら

www.slideshare.net
めっちゃ頑張って作ったしみんなみちくり~


最初のほう全然解かれなくて☆4の機運が高まってたけど、23時時点で24人の方々に解かれたので、まぁよかったかなぁ、という感じです

24時間で1問とか激ヤバ、かつペナルティなしなコンテストなので、多少実装がめんどくても、多少WA狙いなサンプルケースでもゆるしてちょ、って感じ><

一応、想定解のコードっぽい何かです
http://yukicoder.me/submissions/62385


このような拙い問題を皆さま解いていただき、本当にありがとうございました


なんかそのうちもうちょい追記するかも