E - Chords 円周上に $2N$ 点が等間隔に、$1$ 〜 $2N$ の順に番号づけられて並んでいます。$A_i$ と $B_i$ を結ぶ弦で、交わるものはあるかどうか判定してください。 解法では、$A_i < B_i$ になるようにswapした後の説明をします。 解法1 - stackを使う解法…

D - At Most 3 (Contestant ver.) $10^6$ 未満の正の整数を $100$ 進法で $3$ 桁であらわすことができる。つまり、 $100$ 進法で $100^0$ の位、$100^1$ の位、$100^2$ の位がそれぞれ $0$ 〜 $99$ であるおもりを全て持つと個数は $297$ 個であり、$10^6$ …

E - Subsequence Path DPできます。 長さ$N$のDP配列(これは頂点 $1$ からの最短距離を表します)を $dp[1]=0,dp[i]=inf(i > 1)$ で初期化します。そして、各 $E_i$ に対して、$chmin(dp[A_{E_i}], dp[B_{E_i}] + C_{E_i})$ と遷移していきます。これにより、…

E - Traveler 各色ごとに回収する順番を考えます。色 $i$ に対して、最も座標が小さいものを $Min_i$ 、最も座標が大きいものを $Max_i$ とすると、簡単に言えば $Max_i$ までまっすぐ行ってから $Min_i$ に行く、または $Min_i$ までまっすぐ行ってから $Ma…

E - Simple String Queries Fenwick Treeを使います。Point AddとRange Sumを高速にできます。 Fenwick Treeを $26$ 本持つと $1$ 文字を変更したり、各文字について、区間にその文字が現れる個数を高速に求めることができたりします。 type1のクエリについ…

E - Small d and k 各頂点の次数は $3$ 以下、そして各クエリで $k_i$ は $3$ 以下という制約があります。すると、各クエリで見る必要がある頂点は $40$ 頂点に抑えることができるので、BFSをすることで解けます。ただし、訪問の判定に、毎回全ての頂点に対…