2021年 7月 2日
まえがき
お誕生日おめでとうございます。
にゃんにゃんのにゃ〜ん
うしうし！もぐもぐ！
少し昔話をしましょうか。
昔々、あるところに、おじいさんとおばあさんがいました。
でも、そのさらに昔、おじいさんとおばあさんは、お兄さんとお姉さんでした。
さらに遡ると、お兄さんとお姉さんは赤ちゃんでした。
おわり
健康管理
健康です。
何した
南下した
具体的に
今日解いた問題
ABC081 D- Non-decreasing
- [累積和の考え,天才考察,解説AC]
世界で一番おもしれえ問題です。
全ての要素が非負整数である数列に対して、累積和を取ると、累積和は講義単調増加になります.
また、全ての要素が負である数列に対して,累積和を取ると、単調減少になるます。
つまり、全ての要素が非負整数のときは、操作は
a1 a2 (a2 = (a1) + a2)
a2 a3 (a3 = (a2) + a3 = (a1 + a2) + a3)
というふうに行うことで、累積和の数列を作れます（言葉遣いしらないバブ)
次に、全ての要素が負数のときは、
an an-1 (an-1 = (an) + an-1)
an-1 an-2 (an-2 = (an-1) + an-2 = (an + an-1) + an-2
というふうに行うことで、後ろから見ると単調減少の数列を作れる(つまり、前から見たら単調増加になってる！
じゃあ、全て負or全て正をどうやって作るかっていうと、aの中で絶対値が一番大きいものを全ての要素(1 ~ n番目)に足して上げれば全て正か全て負になります。
めちゃくちゃ面白いね
ABC074 D- Restoring Road Network
- [写経AC,ワーシャルフロイド法,構成可能判定]
まず、与えられたA1,1~AN,Nについては、なんかまぁ、辺があるとして、其の辺に対してワーシャルフロイド法を用いて、全点対間最短距離をもう一回求める。
其の結果、二点間の最短距離が元のものよりも小さくなってしまうものがあったら、おかしいことが起きてるので-1を出力。
そうでない場合は、どうにかして答えを求める。
これは頑張ればいける。（俺は頑張れなかった）
この部分がめちゃくちゃ難しい。けど、やってることはダイクストラ法やプリム法でやってることと同じで、まず辺の長さが小さいものから見ていくっていうのを用いればやれる。（俺はやれない)
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
