典型力のNASA of NASA
ところできょうびNASA of NASAって聞かなくなりましたね
これはなに
2019/12/30の14:45から第一回PASTのバーチャル参加をしました 88点でした 評価はなにになりますか 使った方針を述べていきます
A
C++には std::any_of といういい関数があります any of 入力が英小文字ならerrorと出力して終わります
そうでないなら整数にして2倍にしておわりです
B
C++にはfor文といういい言語機能があります 直前のAと今のAを持ちながらやっていきます
C
C++には std::nth_element といういい関数があります おわりです
D
ヒストグラムを作ります
C++には std::all_of といういい関数があります all of ヒストグラムが1ならCorrectと出力して終わります
そうでないなら2であるようなindexと0であるようなindexを出力して終わります ここはよく考えると find といういい関数が使えますね
E
急に難しくなってませんか
C++には std::bitset といういいデータ構造があります bitsetには operator|= といういい操作が実装されています おわりです
F
std::vector<std::string> にまとめて std::sort をします
文字列の文字cについて .back().push_back(c | 32) をして、偶数回目のnon-zeroな c & 32 が来たら .emplace_back() をします sort しておわりです 日本語が細切れすぎますね、競プロ界のルー大柴？
G
全通りは310=59049通りです 各状態についてコストの計算は45回くらいの足し算で抑えられるので全体で2.6*106回くらいです 全通りを高速に列挙するのは
for(unsigned long i{0}; i < 1UL << N; ++i) for(unsigned long j{i}; j < 1UL << N; ++j |= i)
によってO(3N)です おわりです
H
これなに むずかしいです
(奇数枚目/偶数枚目)の(最小在庫/累計売上)の4つを持ちます 売りながら更新します おわりです
I
dpをします おわりです
J
全点間最短距離が求められたとします 私は求められませんでしたけど 本当に黄色ですか？
このとき答えはdist[最初][v]+dist[中間地点][v]+dist[ゴール][v]の最小値になります vを全探索しても間に合いますね おわりです たぶん
K
私は詳しいんです std::bitset で上司の情報を持ちながら全部探索したら間に合... [MLE]
仕方がないのでLCAを書きます 今回は初めてオイラーツアー+RMQによるLCAを書きました
rootからのBFS行きがけ順で頂点にindexを振り直します DFSをしてオイラーツアーと各頂点が出てくるところを持ちます RMQをします 楽をしたかったのでSegment Treeを書きました おわりです
L
使う小さい塔の集合32通りを定めると(使うので)最小全域木を書くだけでいいと思います ところで解けていませんけど 本当に黄色ですか？
M
お ま か せ 二番煎じですか？ ごめんなさい...
実家のような二分探索です 誰か有志コンで有理数でこれ求めさせる問題出しませんか 喜んで解く場合とそうでない場合があります
判定問題「強さをx以上にできますか？」を考えます 単体で強さx+eのもののe×m(質量)の値でソートすると大きい方から足すのが最適になりますね お助けも同様にやります おわりです
N
開けたい区間[x, x+C]をx=0からずずずと動かしていくことを考えます すると各区間がx=いくらのときに 取り除くべきになる/取り除かなくてもよくなる のかがわかります ソートして処理していってコスト最小がこたえです
O
座圧してDPしていきます i番目に大きいものの最良期待値の計算とi+1番目に大きいものの最良期待値の計算ではi番目に大きい数が書いてあるサイコロを振った時の期待値しか変わらないのでそれだけ再計算します おわりです
おわりに
むずかしいですね グラフ理論は書かない期間が続くとグッと書けなくなるのでこれを読んでいる皆さんはぜひ私のようにならないようにしてくださいね おわりです
