IT ARC128_A – Gold and Silver
ARC128_A - Gold and Silver 問題 提出 解けたが、もっと簡単な方法があった 提出した解法は、dpして結果から逆算して取引したかしてないかを算出した。 dp配列に格納する値は以下のようにした。 $dp : i番目まで...
2023-08
IT 
プログラミング 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...
プログラミング ABC314感想戦
コンテスト A問題 感想 円周率の小数第N位までを出力する問題だけど、小数第100位までの値が与えられている。 なので、与えられている文字列の先頭から$N+2$個を出力するといい。 コンテスト中提出コード int main() { ll n...
c++ Tax Included Price(ARC118)
Tax Included Price 問題 提出 公式解説とは異なるやり方だが解けた 以下、解法を書く。 税込価格を変形して、 $\lfloor \frac{100+t}{100}A \rfloor = \lfloor (1+\frac{t...
IT ℕ Coloring(ARC115)
ℕ Coloring 問題 提出 解けたが、数学的に正しいのか分からず解いた 最近の自分の中のトレンドとして、解法が数学的に正しいのか考えてから解くようにしたいと思っている(まだ全然できないが笑)。 この問題では、解法を思いついたものの、こ...
c++ Long Common Subsequence(AGC052)
Long Common Subsequence(AGC052) 問題 解けず。解説を読んで再考 まず、「$2N+1$の$01$文字列であって$S_1+S_1$、$S_2+S_2$、$S_3+S_3$いずれの部分列であるもの」は「$S_1+S...