プログラミング ABC258_D – Trophy
ABC258_D - Trophy 問題 提出 解けた 以下、解法を書く。 1度目のステージクリアには$A_i+B_i$時間がかかり、2度目のステージクリアには$B_i$時間がかかる。 X回ステージクリアするまでにあり得るパターンとしては、...
プログラミング プログラミング ABC307_D – Mismatched Parentheses
ABC307_D - Mismatched Parentheses 問題 提出 解けた 以前解けなかった問題だったが、比較的簡単に解けた。 以下、解法を書く。 $)$がでたら$($まで遡って削除する。 $($がなかったら削除はしない。 遡っ...
プログラミング ABC248_D – Range Count Query
ABC248_D - Range Count Query 問題 提出 解けた 公式解説とほとんど同じ。 $A_i$の数列->どの数字がどこで出現したか、に置き換える。 入力例1の場合、以下のようになる。 $1: $ $2: []$ $3: ...
プログラミング ABC315感想戦
コンテスト A問題 感想 Sを順番に見ていって、a,e,i,o,uのいずれかならスキップ、それ以外は出力する。 コンテスト中提出コード int main() { string s = in_str(); fore(si,s){ if(si=...
IT ABC233_D – Count Interval
ABC233_D - Count Interval 問題 提出 TLE: AC: 解けたが、もう少し簡単な方法があった 以下、思いついた解法を書く。 累積和を用いる。 累積和$B_i$とすると、以下のようになる。 $$B_1 = A_1$$...
IT ARC129_B – Range Point Distance
問題 提出 解けた 以下、解法を書く。 整数ペアが2つの場合を考えてみる。このとき、考えられる区間のパターンは2通りで、 $L_1<L_2<R_1<R_2$と$L_1<R_1<L_2<R_2$。前者は区間が重なっている場合で、$max(di...
IT ARC128_A – Gold and Silver
ARC128_A - Gold and Silver 問題 提出 解けたが、もっと簡単な方法があった 提出した解法は、dpして結果から逆算して取引したかしてないかを算出した。 dp配列に格納する値は以下のようにした。 $dp : i番目まで...
プログラミング ARC125 A – Dial Up
問題 提出 解けた 以下、解法を書く。 最小の操作回数を考えるとき、シフトの操作の有無で話が変わってくる。 シフトの操作が必要ないとき、単純にM回になる。 シフトの操作が必要ない時とは、$S1$のみで$T$が構成されている時である。 シフト...
プログラミング Insurance(ARC122B)
Insurance問題提出解けた以下、解法を書く。 三分探索と累積和を組み合わせて解いた。 最小にしたい関数は、失う金額の期待値なので、以下のようになる。 $$ \begin{align} E(x) &=& \frac{1}{N}\sum_...
c++ Tour(ABC204)
Tour 問題 提出 解けた 以下、解法を記載する。 スタート地点を固定して、全探索する。 全探索をDFSで行うと、$O(N+M)$になる。 スタート地点は全部でN個あるので$O(N(N+M))$になる。 この問題では、最大で$N=2000...