3月20日

今日は、とても嫌な気分になりました。いとこの家に行こうとAM9:00に家族で車に乗り埼玉に向かいました。
姉が17:00に飛行機で羽田から飛び立たなきゃいけないのですが、渋滞のせいでいとこの家に行くの無理だなってなって。途中で引き返しました。
いとこの家では、9歳の子供にプログラミングの話してやれ、みたいな感じな無茶振りをされていて、少し乗り気だったのですがそれがなくなりました。
さらに、買い物にも2,3店舗付き合わされて疲れました。

話を昨日までに戻そう。僕はここ一週間エンカばかりしていました。それでやっと競プロの精進ができると思っていたのに、昨夜、急に「明日出かけるぞ」と言われる。
これだけでも少しストレスですね。
で、まぁ、母親姉僕父親の4人で行くから（まぁ姉がいるから許すか）って感じでした。
でまあ、結局埼玉行けず時間たくさん使わされてって感じで、結構イライラするわ。

こっちは競プロするかアーロンチェア買うための金稼ぐことしか考えてないのに...
具体的には8:00~17:00ぐらいまでの時間が潰れました。

あはｗｗｗ

今日解いた問題

時間がないのはもうどうしようもねえから極度精進がんばります。
アルゴリズムの勉強から問題を解く精進に切り替えます。

ABC038 C-単調増加

[尺取り法]diff試験管900
愚直は通らない。通さない。
0<=i<=n-1に対してi+1から一個ずつ見ていくよ。といったO(N²)の実装は制約 N <= 10⁵なので通りませんね。
WAは出していないのですが、やらかしたミスとして,

a[i] < a[i+1]

を

a[i] <= a[i+1]

としていました。（サンプルに入っていたので気がつくことができた)

おまけ~別解法と知見

まずはこちらのコードをご覧ください

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    ll prev = INF, cur = 0;
    ll res = 0;
    rep(i,n){
        int x = a[i];
        if(prev < x){
            ++cur;
        } else {
            res += (cur*(cur+1))>>1; // ここすごい!! 2で割る処理ができる！！
            // res += (cur*(cur+1)) / 2; と同じ
            cur = 1;
        }
        prev = x;
    }
    res += (cur*(cur+1))>>1;
    cout << res << endl;
}

res += (cur*(cur+1))>>1; // ここすごい!! 2で割る処理ができる！！

ここの処理すごいです。
皆さん（少なくとも僕は）

1って言う処理は右シフトbit演算だったっけ？みたいな名前がついているって言うことはご存知ですよね（僕は曖昧) つまり、二進数で表した数 100は010になるってことです。右に一個ずれました。（一番左の0はどっから出てきたんだ！！って話ですが、足りない分は0を入れるのが一般常識です）（たぶん）
嘘言ってたらごめん。正直自信ないよ で、実際に100は十進数で4,010は十進数で2なので >>1で２で割るという処理ができています！すご〜い！
(そういえば何かの勉強してたときに、シフトbit演算は2の掛け算なり割り算ができるって言ってた気がするな〜) で、まぁ、このコードを尺取りっていうのかどうかわからないけど、賢いですよね！！
人に伝えるのが目的ではないのでこの辺でいいや！（説明できるようになりて〜〜)

ABC115 D-Christmas

[再起関数,ムズカシイ]
むずくね？写経AC 良うわからん

ABC075 C-Bridge

[橋、連結無向グラフ]
橋の問題です。他人の記事からうばってAC

草体にぼ日記

だらだらと

2020年3月20日　日記