ABC351をやった。
A: max(0, sum(A)-sum(B)+1)
B: やるだけ
C: 左から取るものと誤読して時間を無駄にした。よく見たら右からだったのでstackだった。
D: まず磁石の範囲に入るマスにマークを付ける。磁石の影響を受けないマスの連結成分をufで求め、磁石の影響を受けるマスを各連結成分に寄与させる。
E: まずパリティで分け、偶奇それぞれについて別々に同じことをやっていく。
まず45度回転させてマンハッタン距離に置き換える。具体的には(x,y)->(x+y,x-y)として距離を半分にすればよい。求めるのは$|X_i-X_j|+|Y_i-Y_j|$の総和だが、これは$|X_i-X_j|$の総和と$|Y_i-Y_j|$の総和を別途求めて足せばよい。そしてXでソートすれば$|X_i-X_j|$の絶対値が不要になるし、Yでソートすれば同様なので、適宜頑張れば行ける。
F: 最初ソートするだけじゃね？と思ったら違った。
まず式から分かるように、$A_j>A_i$なる場合のみ見ればよい。ある$j$について、$A_j>A_i$なる$i$の数とそのような$i$についての$A_i$の総和を求めればよいことが分かる。これは座標圧縮してBITに載せればよい。
G: 分からず。ある頂点の値が$+x$だけ変わった場合、その親頂点の値は$+x\prod_{c\in C(p_n), c\neq n}f(c)$だけ変わる…みたいなのは考察した。
HLDが道具の名前として頭に浮かんだが浮かんだだけなのでどうにもならず、先週やったクエリ平方分割をやろうとしたが考察しきれなかった。
cpprefjpを読み進めた。今日は言語機能の「属性構文」～「共用体の制限解除」まで。
属性構文
構文としては知っているが、[[carries_dependency]]は知らなかった。というかstd::atomic関連のことを全体的にちゃんと把握していないというのが正しい。どうやらまず前提として、std::atomicには値の依存性を設定して最適化を抑え処理順序を守らせる機能があるらしい。純然たるライブラリだと思っていたのでこれは意外だった。そしてその依存性情報を伝播させるための機能として[[carries_nodependency]]があるようだ。
宣言時に要素数を指定した配列オブジェクトの、定義時の要素数を規定
なかなかの枝葉末節だ。しかし宣言が定義に影響を与えるのもちょっと気持ち悪いな。
委譲コンストラクタ
知ってるやつ。
右辺値参照・ムーブセマンティクス
現代C++の重要な機能なので知ってはいるが、あんまりちゃんとは理解していない。一応いい機会なので軽く調べた。lvalue/rvalueがあること、rvalueにさらにxvalue/prvalueの別があること、lvalueとxvalueを総称してglvalueということを覚えた。xvalueという概念がどういうケースの議論に役立つのか、glvalueとかいう概念を使うことはあるのかがちょっとピンとこない。
std::forwardの意義もあまり分かっていなかったのだが、どうやら関数の引数として右辺値を右辺値参照で受け取った場合、それを関数内で使うと左辺値になってしまうため、それをちゃんと左辺値参照で受け取った者は左辺値に・右辺値参照で受け取ったものは右辺値にするのがstd::forwardの意義らしい。
しかしC++11より前はどうしていたのかというと、const左辺値参照でどうにかしていたらしい。びっくり。
可変引数マクロ
さすがに全く存在を知らなかった。こんなのあったんだ。
可変引数テンプレート
知ってるやつだったが、テンプレートテンプレートというものをこれの記事を読むまですっかり忘れていた。テンプレートテンプレートにも可変長引数が使えるらしい。
参照への参照を折りたたむ
一体どういう意義なんだ？と思って調べたが、どうやらcpprefjpに載っているようにエラー回避策の不要化に加え、完全転送周りの問題解決あたりが目的らしい。
初期化子リスト
知ってるやつ。
列挙子の末尾へのカンマ付加を許可
知ってるやつだが、C99互換という目的があったとは初めて知った。結構その目的での新仕様多いのか。
共用体の制限解除
そもそも共用体自体中々使わないが、C++11までクラス入れるのが出来なかったとは知らなんだ。使う場合はコンストラクタとデストラクタを自力で呼び出すらしい。仕方ないが中々面倒だ。今どきは特別な理由が無ければstd::variantsを使うべきだろう。
ここ最近3時とか下手すると4時くらいまで起きていたりしてひどいので、今夜は早く寝る。サークルの集まりにABCと、休日にしてはやることやった日なので寝れていいはずだ。
Categories: 未分類