草体にぼ日記

だらだらと

2020年6月18日 日記

2020年 6月 18日

まえがき

今日の日付は ろくがつじゅうはち
そうです!今日はなんと!!

なかがき

このブログ投稿したら僕は大学の課題をやってきます。

健康管理

何した

ABC157 E-Simple String Queries この問題を一昨日写経ACしたのですが、もう一回通しました。
ぅゆ(一人称)はsetを全然使わなたぷにきあ君だったので、setの練習になるね。

ところで大学生ってなんだっけ

今日解いた問題

EDPC H- Grid 1

僕が解けるDPだ、ありがたいですね。
あるマスが通過可能なマスの時、其のマスへ行く方法は、左のマスから行くか、上のマス(まぁ、どこを上と見るかは人によると思うけど)から行くかの二通りしか無い。
この時、左のマスへ行く方法がL通り、上のマスへ行く方法がU通りあるなら、其のマスへ行く方法はL+U通りだなあ。ってやつ。
初期条件として、(1,1) へ行く方法が1通りだというのさえ知っていれば解ける。

EDPC I- Coins

  • [確率DP]

解けた〜!!(やった〜) 小数が出てくるから確率大っ嫌いなんですけど、doubleで通ったのでよしです。

僕は1次元dpで解きました。

vector<double> dp;
int main()
{
    ll n;
    cin >> n;
    vector<double> p(n);
    rep(i,n) cin >> p[i];
    dp.assign(n+1,0);
    dp[0] = 1;

    rep(i,n){
        for(int j = n; j >= 0; j--){
            if(j==0) dp[j] = dp[j] * (1-p[i]);
            else dp[j] = dp[j-1] * p[i] + dp[j] * (1-p[i]);
        }
    }
    double ans = 0;
    for(int i = n; i >= (n/2+1); i--){
        ans += dp[i];
    }
    cout << setprecision(15):
    cout << ans << endl;
}

表がN枚出る確率 -> 表がN-1枚出る確率 -> ... -> 表が0枚出る確率 という順番で後ろから更新しました。
i枚目のコインについて見ている時,表がK枚出る確率は、K-1枚表が出る確率 * i枚目が表 + K枚表 * i枚目が裏
事故らないようにDPしてるので事故りません.

 rep(i,n){
        for(int j = n; j >= 0; j--){
            dp[j] = dp[j-1] * p[i] + dp[j] * (1-p[i]);
        }
    }

これはなぜかACしてしまった不思議なコードです。

配列やベクターの-1番目の要素にアクセスしようとしたときってどんな事故が起こるんでしたっけ? こういうのをあまり勉強していないせいで今30分ネットサーフィンしたけど、答えを見つけられませんでした。

ちなみに手元で動かして見た限りだとvectorなら0,配列はよう分からんになってました。
(毎回vectorなら0かは知らない) 怖いですね。

EDPC J-Sushi

  • [期待値DP]

0枚の皿の数、1枚の皿の数の枚数、2枚の皿の枚数が重要そうだなっていうところまではなんとなく思いました。
漸化式の部分が完全な理解と遠いですね。

dp[i][j][k] = dp[i][j]k * (N-i-j-k) / N (皿の枚数の組み合わせが変化しない確率) + 1

と dp[i-1][j]k * i / N (残り1個の皿が一つ少なくなる確率) + 1
と dp[i+1][j-1]k * j / N (残り2個の皿が一つ少なくなる確率) + 1
dp[i][j-1]k+1 * k / N (残り3個の皿が一つ少なくなる確率) + 1

うーん…

ある状態Aのとき, 残り1枚の皿を引くと、操作を一回したことで、残り1枚の皿が一つ減るので、残り1枚の皿が一つ減った状態Bで終わらせるための操作回数に+1をしたものが Aから終わらせるための操作回数。

みたいなイメージと、
状態Aから状態Bへ状態がうつる確率というのがi/N … うーん 頭壊れる

CODE FESTIVAL 2016 qual C

  • [矛盾判定,何通り]

二人の証言から、山の高さが確定したタイミングというのをかんがえました。
まず、0番目の山の高さはt[0]であることは分かります。
t[0] := (0~0)番目までの山の中で最大の高さ。

同様に、n-1番目野山の高さはa[n-1]であることも分かります。
a[n-1] := (n-1 ~ n-1)番目までの山の中で最大の高さ

もう一度t(高橋くんの証言)に戻ってかんがえます。 今、t[0] = 2, t[1] = 2, t[2] = 3としておこう。
すると、山0の高さは2(確定),山1の高さは1か2です。
(t[1]は、山0と山1の大きい方が値として入っている)

次に、t[2] = 3 ここに注目です。
t[2] := 0,1,2番目の山の最大の高さ
0,1番目の山の最大の高さは2だったので、2番目の山の高さが今 3で確定したことが分かります。
このように、高橋くんの証言からまず、山の高さが確定したタイミングというのを取得します。

山iで高さがkで確定したとき、 青木君の証言で、a[i] := (n-1 ~ i番目)までの山の最大の高さが k より小さくなってはいけません。

というのも、山iの高さが k であるのに、 青木くんの証言が  山(n-1 ~ i)の高さは (k-1)以下だったよというのは矛盾が生じるからです。

これで大体終わりで、後は青木くんの証言からも山の高さが確定するタイミングというのを取ってやると矛盾の判定が出来る。

map<int,int> rock;
    rep(i,N){
        int l, r;
        if(t[i] > m){
            l = r = t[i];
            m = t[i];
            rock[i] = m;
        } else {
            l = 1;
            r = m;
        }
        left[i] = P(l,r);
    }
    m = 0;
    for(int i = N-1; i>=0; i--){
        int l, r;
        if(a[i] > m){
            l = r = a[i];
            m = a[i];
            rock[i] = m;
        } else {
            l = 1;
            r = m;
        }
        right[i] = P(l,r);
    }

僕は馬鹿なので、山の高さが確定するタイミングと其の高さをmapで管理しようとした結果、 確定 = 鍵がかかる なので変数名をロックにしよう。として間違えて岩(rock)にしてしまいました。

あとがき

いつか見た夕焼けはあんなに綺麗だったのに 恋なんて呼ぶには汚れすぎてしまったよ

にゃーーん

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)