草体にぼ日記

だらだらと

2020年6月8日　日記

毎日

2020年 6月 8日 猫のフライ返し

好きだったあいつに受け入れてもらった

何度も何度も好きだったあいつに、ラブレターを出していました。
何度も、何度も。
文面を変えて何度も。
時には自分でも分からないくらい変なことを書いていたんだと思う。 だからかな、あいつはいつだって私に「無理だ」って言った。
そう言うだけだった。あいつはいつも私に何もしてくれない。
でも私は、何度だって書いた。あいつが好きだから。

私はあいつに6度目のラブレターを出した。
その時に気づいた。あいつは私のことが嫌いだったんじゃない。私があいつのことを何も分かっていなかったんだ。

あいつは受け入れてくれた。 ソレは、5通目のラブレターにニ行付け足しただけだった。

sum = 1;
sum = -1;

たったそれだけ。でも、あいつはそのニ行をずっと待っていた。

言ってくれなきゃ分からないよ　

そう言って私は、別の男にラブレターを書き始めた。

まえがき

なんか、人のブログみてて思うんですけど、僕のブログは伝えるためのブログって言うよりかは思いつきで書いているので、他人はあんまり読まないほうが良い気がします。
とくに今日解いた問題の部分なんて、自分で読める用にしか書いていないので解説記事として見たらブチギレられちゃうと思います。

健康管

よくねた

何した

きょうぎぷろぐらみんぐ　と大学の課題

具体的に

今日解いた問題

AGC039 B-Graph Partition

  • [ワーシャルフロイド法,二部グラフ判定,グラフの直径]
    まず問題の意味が分からなかったので解説動画を見て問題の意味を理解した。

解説アンド写経です。
僕から言えることはない .

各辺が隣り合う番号の頂点を結んでいるようにする。 各集合がNo Empty
どういうときに出来るか。二部グラフじゃないと駄目なことが分かる。全部の辺が偶数グループと奇数グループを結んでいるはず。

はぅう...(゜-゜):w

(゜-゜)、奇数にも偶数にもなっちゃう時、衝突して死ぬ…

3ミリ分かったようなわからないような。

ABC100 D-Patisserie ABC

  • [BIT全探索,価値の最大化]

自力ACです、しかしちょっと未証明感が強いですね…
テキトウに、M個選んだ時の綺麗さの和,おいしさの和,人気度の和をX,Y,Zとでもしておきましょう.
このとき、(X、つまり綺麗さの合計の絶対値) + (Y,つまりおいしさの合計の絶対値) + (Z,い人気度の合計の絶対値) = S とでも置いておきます。 すると、S = +-(X) +-(Y) +-(Z) ですね。+-はプラスかマイナスかのどちらか。的なニュアンスで。

となると、X,Y,Z,それぞれについて正に大きくするのを目指す。負に大きくするのを目指すかでわけでかんがえると良さそうだな…って気がします。
Xは正に、Yは負に大きく！、Zは負に大きくしよう！！としたとします。 この時、あるケーキ、綺麗さ[50],おいしさ[20],人気度[-10]の価値というものを定義しよう。
綺麗さは正に大きいと嬉しいので、x = 50,
おいしさは負に大きいと嬉しいので、 y = -1 * 20 = -20
=人気度は負に大きいと嬉しいので z = -1 * -10 = 10 よって、このケーキを選んだ時の価値はx+y+z = 40
みたいな感じなことが出来る…

そうして、価値が大きい順にM個取ったよ。さぁ、Sを更新しよう。みたいなノリ。
なんだけど…ここからがちょっとよく分からなくて… M個選んだ時、そのM個のxの和(X)が確かに正、Yが負、Zが負になっているかを確認して、OKなら更新…

OKじゃない時どうするんだ。みたいなのが悩みです。

布団にこもりながらかんがえてたら分かりました。 例えば、x,y,zそれぞれ+,+,-に最大化しようってしたときに、X,Y,Zが+,+,+になっちゃったとします。 そうしたら、その値っていうのは+,+,+に最大化しようとしたときの値で塗り替えることができるので問題無いんだね。

ABC047 D- 高橋君と見えざる手

  • [コストの最小化,差の更新,差の最大]

いろんな解説に書いてある通り、i番目の町まで見たときに、i-1番目の町までで一番安い物しかi番目の町で売ることはあり得ない。
i番目の町まで見た時、i-1番目の町までで一番安い物を売ることを考える。

同じようにして、i番目で買ったならi+1番目以降で一番高い町で売るのが最適。

でまぁ、僕が詰まったところは、 1 -> 3 -> 5 -> 7 ってなった時、1と3では差が2じゃん、3->5は差が2じゃん。5 -> 7は差が2じゃん。 1を2にして、5を6にしたら、7は8にしなきゃいけない…？ああ？？ってなってました。

いや、1を7で売るのが元々やんけ(気にしないで)

ABC059 C-Sequence

  • [二通り試す,操作の最小回数]

ブログ冒頭はこれです。（は？）

なるほどね。i番目までの和が偶数のときと奇数の時を二通り試すのか〜…
0番目までの和はいじらなくていいだろ。って無意識に思ってました。

ABC120 D- Decayed Bridges

  • [UnionFind,逆からみる]

M番目の橋から順に見ていきます。
まず、M番目の橋をつなげたことで、A[M]とB[M]が行き来出来るようになります。 逆にこの橋がなくなることで,A[M]とB[M]が行き来出来ないようになります。
この時増える不便さは1(A[M]とB[M]の一組だけ行き来できなくなるので.) この、値"1"を heru という配列の0番目に格納します。

次にM-1番目の橋を見ます。
この時、M-1番目の橋を繋げたことで、何組の島が新しく行き来可能になったかを見ます。 この値を heru という配列の1番目に格納します。

これを1番目の橋までやっていきます。
heru という配列を逆順にします。 M回出力します。i回目の出力は、heruの0からiまでの値の和。

UnionFindでやる。

あとがき

今日も元気でした！

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

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