2020年3月28日

健康記録

睡眠時間　5時間30分ぐらい（4:18〜9:30ぐらい）睡眠時間たりてないけど、家族に無理やり起こされたから仕方ない。（姉が引っ越すのでその手伝い）今も羽田に向かう車に乗りながらこの部分のブログを書いているよ。

まぁ、無理やり7時間以上寝たってことにするとなると、昨日は3時間ぐらい昼寝してたから足して8時間ということにできます。

精神状態は0 可もなく不可もなくって感じ。別に特に思うところはない。

何した

今日は姉が引っ越す日なので、16時ぐらいまでずっと外に行っていました。
その後家系図を少しだけ作って、19時に飯を食べ終わりました
そして、20時まで昼寝するぞ〜って思って目覚めたら21時。
…は？？？？？？？？？？？？？？？？？？？？？？ 21時justです。
みなさん、3/28日が何曜日かしっていますか？
私は知っています。

外出自粛の日です。いやまぁ、それもそうなんだけどAtCoder Beginner Contest 160ですよ。
やばいやばいと思って、急いでPCを立ち上げ、Cまで早ときの回じゃなかったら参加しよう！そう思っていました。 A,B,Cまでとりあえずコードを書いた。その後順位表みて3秒だけ迷ったけど全部提出！！
なかなかjudgeされないな〜って思いつつDに取り掛かりました。
その後ちょいちょjudgeを見に行くも、まだA,B,C判定されてねえ！
Dを書いてjudgeみたらCがWA!!マジカ。で、ちょっと手直ししてAC
ここまでDまで4完
その後、天才的な速度で考察を済ませてEを提出、AC！！
5完です！！！！！！１ perf1583!!(嬉しいね)

まぁ、コンテスト終わった後は精進も何もかもはかどらないの法則があるので、2試合CSGOをして、今執筆中って感じ。

今日解いた問題(ABC160)

ABC160 A-Coffee [文字列,if文]
1. 3文字目と4文字目が等しいかを見る 2. 5文字目と6文字目が等しいかを見る 3文字目はstringの要素番号が2みたいなのを知っているかっていう問題ですかね. ABC160 B-Golden Coins [切り捨て,最大化(easy)]
なんか

(なお、利用できる硬貨は500円玉、100円玉、50円玉、10円玉、5円玉、1円玉の6種類とします。)
とか書いてありますけど全くどうでも良い情報でしたね（10秒ぐらい取られた）
寝起きというのもあって（さっきも言ったけど、21時おきです。)問題分を読むのが難しかった。
けど、言っていることはつまり500円玉が何セット、あって、それを除いたら5円玉は何セットありますかみたいなことだとおもいます。
あ〜、なんか両替したとき、高橋君の嬉しさはいくらになりますか？

ってあって、1円玉が使えるってわかってるから、X円を全部1円玉にして、そこから作れるだけ500円玉を作って1000の幸福度を得る…みたいな感じに考えればいいんですかね（問題文をいちいち読むのであれば)

int main() {
    int x;
    cin >> x;
    ll ans = 0;
    ans = (x / 500) * 1000;
    x -= (x/500) * 500; // x % 500 で良い！！
    ans += (x / 5) * 5;
    cout << ans << endl;
}

多分これでok ABC160 C-Traveling Salesman Around Lake [図形(?),最短距離(easy)]
池の周りのセールスマン
お絵かきします。

pic.twitter.com/iujttGqjpb
— 素行不良体調不良消化不良 (@niboshi_wakai) 2020年3月28日

コンな感じな4枚のお絵かきを（今）してみました。
まぁ、なんとな〜〜〜〜〜〜〜〜く、要点を言うと どこか2つの地点だけの移動をみないことにすれば良い。 つまり、a0とa1,a1とa2,...,an-1とa0の距離をdist0,dist1,distn-1としたときに、 dist0~distn-1の和からdist野中の一番でかいやつを引けばいいんだけど、うまく説明出来ないな
なんなら俺もいま本当にそれで通るのか怪しくなってきた。あー通るわ… 楽しくないから次の問題いくね

ABC160 D-Line++ [連想配列(map),無向グラフ(だけど…),最短距離]
無向グラフとか言われて身構えさせられたけど、辺を受け取る処理も書かなくていいので怯えるな！！って感じな気がした問題
恐らく入力例を見るのが良くて、とりあえず1から2、2から3みたいに、kからk+1に行くときは最短距離が1だね〜〜っていう…)
で、最も距離が長くなるのはN-1って思うじゃん？実はそうじゃないんだよね（これは問題を解くのにさほど重要ではない)
まぁ重要じゃないから話さなくていっか。
何を話そう…うーーん
制約、みましたか? N ^ 2が10⁸よりも小さいです。
はい。

やること

任意の2頂点i,j(i < j)間の距離を求める。
マップ,距離をキー、バリューを出てきた回数としたものを用意する
1で求めた距離をバリューを＋１する。

距離の求め方は後ではなそう。
マップの嬉しい機能として、値の更新がなかったキーのバリューは0にしておいてくれるってことがあるんですよね。だから、これら1~3の手順をした後に 4. キーを0~N-1で回して出力。 5. AC

距離の求め方

iからjに行くときの経路を考えます。　　 1. i -> j　に直接行く 2. X,Yをつなぐ辺を使ってjまで行く( i -> x -> y -> j) このとき、i -> x　のコストは abs(x-i) + 1 + abs (y - j) です。（あってるよな？） 1 と 2で求めた値のうち、小さいほうが頂点i、jの最短距離でぷ。。

これ以上天才が言うことはないのでコード貼っときます。

int main()
{
    ll n , x, y;
    cin >> n  >> x >> y;
    --x, --y;
    // O(N^2)
    map<int,int> mp;
    rep(i,n){
        for(int j = i +1 ; j < n ; j++){
            // 単純なi と j の距離
            // i　から x 、x から y 、ｙからj　の２つを比較する
            ll tmp;
            tmp = abs(x - i) + 1; //今yまでキた
            tmp += abs(y - j); // tmp は, i -> x -> y -> j
            tmp =min((ll)j - i,tmp);
            mp[tmp] ++;
        }
    }
    For(i,1,n){
        cout << mp[i] << endl;
    }
}

ちなみに、i -> y -> x -> j の経路を考えなくて良いのか？って思う人もいるかもしれませんが、考えなくていいです。というのも、x < yであることが保証（制約から）されていて、i < jなので,i -> y -> x と移動してしまうと、一回遠ざかる…？あれ、なんかよく分からんくなってきた。
とりあえず i -> x -> y -> jだけ考えておけばイイヨ（証明、AC)
なんか今解説pdfみたら i->y->x->jも考えてた。なんで通ったんだろ

ABC160 E-Red and Green Apples [組み合わせ…？,最大化]
問題文を読んでいるとき、「うっ…DP…？」という言葉が頭をよぎりました。その後、紙に書いてpriority_queueが一瞬浮かんだけど、なんか嫌な予感がしたので、一回食べれるだけ全部食べちゃいました(かわいい)
これは、赤を食べれるだけ（つまりX個）、緑を食べれるだけ（つまりY個）、値の大きいものからX個とY個選んで食べてみました。そして、食べた物をメモしておきます。サイズはいくつですか？そうですね、X+Y個のメモが必要です。
メモを小さい順にソートしてあげましょう。
そして、その中にrの要素よりも小さいものがrと交換しちゃいましょう。そんな感じのノリでなんかうまく行く… （あれ、なんでうまく行くんだ？ちょっと不安になってきた)
(うわー配列外触っちゃってました（後日談))

ま、明日正しく解けばええやろ

　あとがき

結構ガバいので明日解説動画をみます！！（今日は結構眠たい)

[課題] D問題　Line ++ において、(i,j)の２点間の距離を求める際、 i -> x -> y-> jのほうが i -> y -> x -> jよりも常に短い距離であることを示そう。（示したいね)

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

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

草体にぼ日記

だらだらと

2020年3月28日　日記