atcoder.jpできるだけ長く連続した'o' の長さを求める問題ですが、長さを求めるためには最初の'o' の位置 と最後の'o'の位置 から と考えればよいです。 'o'が連続する連続部分文字列をできるだけ長くするためには、最初の'o'は文字列の先頭あるいは'x'の次…

atcoder.jp 積が N になるための出た目の回数 サイコロを何回か振った結果、1,2,3,4,5,6 の目が出た回数がそれぞれ 回のとき、全部の積を素因数分解すると、 となります。これが N と一致するためには、まず N を の形に素因数分解でき、かつ が成り立てばよ…

atcoder.jpエラトステネスのふるいで素数のリストを作成して、 を 番目の素数 () とします。 をループして、条件を満たすの個数を求めることを考えます。 すなわち の値を固定すれば、の範囲は となります。 この範囲に入るのが素数リストの何番目から何番目…

atcoder.jp 部分文字列の数え上げ まず、部分文字列を数える方法を考えてみます。文字列の長さを文字とすると、各文字に対して選ぶか選ばないかの2択なので、部分文字列の選び方は 通りあります。 しかし、これは同じ部分文字列になる選び方が複数あるとき、…

atcoder.jp頂点[p_i] から黒頂点までの最短距離が であることから、距離 以下の頂点はすべて白頂点であると確定します。 各頂点について調べることで、白と確定する頂点をすべてリストアップします。 そのあとで、未確定の頂点は黒として、各頂点[p_i] から…

atcoder.jp となる を一つ求める問題です。 であることから、 ではなく、どこかで となります。 1と の間の について、 であれば、1から の間に値が変わることが無いかもしれませんが、からの間では少なくとも1つ値が変わるところがあります。そこで、からの…

atcoder.jp巨大なマス目から、(R,C) を選び、R行 または C列 のマス目の総和の問題です。 あらかじめ、各行の総和と各列の総和を計算しておくと、問題の値は、 と求められます。 ほとんどのマス目は 0 であることから、0以外の値のある行と列のみをリストア…

atcoder.jp動的計画法で、サイコロを 回振ったあとに地点 にいる確率を とします。 さらに1回サイコロを振ることによって地点 のいずれかに確率で到達します。(地点が N より大きくなる時は、N に置き換えます。) このことから、 … と確率の加算を行います。…

atcoder.jp各クエリで を数とみなした値を更新していきます。 クエリ1は、値を10倍してを加えます。 クエリ2は、先頭の数字にをかけた値を引きます。 このクエリのために、追加する数字を配列に記録することと、をあらかじめ計算しておきます。 それぞれの値…

atcoder.jp 期待値の求め方 マスの数は個で、ここから 個 の選び方は、 通りです。 選んだマスの位置を とすると、スコアは となります。スコアが になる選び方が 通りあるとすると、スコアの期待値は と計算されます。ここから を求めることを考えていきま…

atcoder.jp安いほうから順に 個を選ぶことを考えてみます。 各種類を1つだけ買った時の価格を集合に加えます。 集合の中から一番安い価格を取り出します。 その価格に、さらに1つ追加で買うときの価格をに加えます。 は同じ値の重複を許さないようにして、か…

atcoder.jp正の整数に対して なら なら を何回繰り返すと になるかという問題です。この操作を1回ずつ行うと、たとえばのとき回程度になるため時間がかかりすぎます。そこで、 の場合、 を で割った商と余りを求めます。 回の操作で、 になるので、 であれば…