精進メモ 2021/07/26~
公開し忘れていました。
2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020)
チーム練です。ばやしこくん、suzuken君と出ました。
suzuken君:A,C,I(考察)
ばやしこくん:D(考察)、G(考察・実装8割)、K
僕:D(実装)、E、F、G(実装2割)、I(実装)
という担当でした。
D. Jogging
下限は無視してよく、まずはダイクストラを普通にします。
それぞれの頂点について、そこまでにかかる時間×2が、上限未満であれば、その頂点に繋がっている辺を答えに加算できます。
答えをチェックする配列のサイズがになっており、1ペナしました。反省。
F. Mentors
大きい方から愚直に当てはめていけば良いです。
子が既に1つある頂点の個数でまとめられるので、あとはDPです。については特別処理するだけでOKです。
H. Figurines
永続セグ木で検索すると、hotman君の記事が出てきて、それを読むとそのまま応用できる問題が出てきます。これを頑張って書き換えればOKです。
OKですが、入力について、それぞれの日について、フィギュアの更新が2つで固定というわけではないらしいです。これに気づけず、コンテスト中はACできませんでした。
許しません。
I. Emails
適当な頂点から最遠点を探すと、グラフ内の距離の最大値は、先ほどの最遠点の2倍以内に収まります。
答えは、その距離のlogです。
ABC212
FGHのうち2問解こうとしたら、GHが解けなくてFもギリギリになってしまいました。さっさとFを解いておくべきでした…
D - Querying Multiset
mapでを管理します。
出力時は、一番小さい値に、現時点での総和を足せば答えです。
E - Safety Journey
包除でやったらMLE＆TLEの1ペナをしました。配列のサイズを減らしたら通りました(TLEはよくわからず)。
回移動して、今
にいるようなルートの中で、違反した回数が少なくとも
回(偶奇)になるようなもののパターン数
として遷移すればOKです。
F - Greedy Takahashi
力でなんとかしました。
バスについては、乗る時刻と降りる時刻、クエリについては、出発する時刻と出力をする時刻の2つにわけます。
あとは、時刻でソートを行い、それぞれを順番に処理していけばいいです。今どの頂点にいるかは、バスの乗り降りをするたびにUnion Findでうまくまとめました。
