2020/2/13

 ICPC 2019-2020 North-Western Russia Regional I

ピラミッドの高さを二分探索すると、各モニュメントの情報からピラミッドの頂点があるべき領域がわかる(正方形状の領域の積集合を考えればよい) 

 

ICPC 2019-2020 North-Western Russia Regional J

グラフ構築

ある頂点から別の頂点へのパスの数がmod10で与えられるので、条件を満たすグラフを出力すればよい(入力は必ずvalid)

こういうのは確定する部分から漸次決定していけばよくて、頂点番号が大きいものから順に、頂点番号が小さい頂点からのパスから順に考える

頂点番号が大きいものから順に見ることで、ある辺を貼った時にどこへのパスがつながるかを、貼った辺の先の頂点の情報を見ることで線形時間で判定できる

頂点番号が小さい頂点からのパスから順に考えることで、ある頂点から出る辺を貼るかどうか判定するときに、これから貼る"その頂点から出る辺”について考慮する必要がなくなる

 

ICPC 2019-2020 North-Western Russia Regional M

普通のmapでやると間に合わない→unordered_mapを使う

std::distanceはイテレータがランダムアクセスでない場合線形時間がかかる

こういう実装は素早くできるようにならないといけないね...

 

 

 

unordered_mapについて

キーの順番を無視している分キーの生成、更新が高速(償却定数時間)

hash tableを用いて実装されているので衝突するケースで線形時間がかかる(hackありの状況で使うのは危険)

 

 

高速化のためのコンパイルオプションについて

#pragma GCC optimize("Ofast") 

コンパイル時の最適化における実行速度の優先度を高められる(高速化をしたい時はとりあえずつけておいて良さそう)

 

#pragma GCC optimize("unroll-loops")

ループ展開を行う(ループ内に分岐がある場合はあまり効果がない?)(そもそも対して速くならない?)(要検証)

 

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

浮動小数点演算の最適化を行う

 

注意点として、コンパイルオプションを指定できないジャッジ環境では使えない