きろく

特筆すべき記録のまとめ

2019-04-30から1日間の記事一覧

いろはちゃんコンテスト Day1:H - ちらし寿司

問題 解法 解答 問題 atcoder.jp 解法 x99999... とするのが最適.しかし,N が x99999... という形であった場合,問題文にある X != N という条件を満たせない.そこで,例えば X = N = 199999 となってしまったとき,X = 289999 とすることで回避できる.…

いろはちゃんコンテスト Day1:G - 友達以上恋人以下

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := i - 1 日目までで,j 回好意をほのめかし,前回のほのめかしから k 日経過しているときの,i 日目以降に得られる機嫌の合計の最大値 と DP をおく.このとき遷移は,i 日目に好意をほのめかすかどうかの…

いろはちゃんコンテスト Day1:F - Head of The Dragon

問題 解法 解答 問題 atcoder.jp 解法 N を素因数分解したときの項数よりも K が大きいとき,条件を満たす解はない. そうでないとき,答えの 1 ~ K - 1 項まで順番に N の素因数を小さい順に当てはめていけばよい.最後に残った素因数を全て掛け合わせたも…

いろはちゃんコンテスト Day1:E - 放課後

問題 解法 解答 問題 atcoder.jp 解法 デートする日を最小化することを考える.以下,最小のデート回数を考える. B = 0,すなわち,記念日が無いとき,最小のデート回数は N / A. そうでないとき,0 日目と最初の記念日の間,B - 1 箇所ある隣り合う記念日…

いろはちゃんコンテスト Day1:I - リスのお仕事

問題 解法 解答 問題 atcoder.jp 解法 木を頂点,枝を辺として無向グラフを考える.このとき,前に移動した枝の隙間の大きさを状態として加えたダイクストラ法を用いて,頂点 1 から各頂点まで休まなければいけない最小の回数が求まる.よって,答えは (dist…