2021-05-01から1ヶ月間の記事一覧
atcoder.jp 問題 消費税T%のとき課税後の整数値として現れないN番目のものを出力せよ。 制約 解説 ある自然数Aがあって、T*A の結果、100の位へ繰り上げがあるなら、(100+T)*A/100-1 は登場しない整数値である。 なぜなら、T*A で100の位への繰り上げが生じ…
atcoder.jp 問題 以下の条件を満たす長さNの数列Aを構築せよ。 数列のどの2つの要素も互いに素ではない 解説 まず、どの2つの要素も互いに素ではなく、一方で全体のgcd は1である、という点に着眼し、数列の要素を3つのグループに分けることを考える。 グル…
atcoder.jp 問題 Nが のようにK分割されている。Mが与えられるので同様にK分割し、その結果を整数列Bとしたとき、 が最小となるようなものを1つ出力せよ。 制約 解説 数列Bの要素として実数を許すなら、 とすることで、 を全て0にすることができる。 しかし…
atcoder.jp 問題 N個の要素からなる集合A の2つの異なる部分集合で和の mod 200 の値が等しいものが存在するかを判定し、存在する場合はその2つの集合を出力せよ。 制約 公式解説 公式解説は、鳩ノ巣原理により の場合は必ず解が存在することから、 の範囲に…
燃やす埋める系の問題をまとめて解いたので、学んだ点について書き残しておく。 燃やす埋める問題とは以下の様な問題である。 いくつかのものが与えられて、それを赤か青に塗り分ける必要がある(燃やすか埋めるか)。それぞれがどちらの色に属するかによっ…