A - Past ABCs 与えられる文字列は 6文字で、先頭の3文字は気にする必要が無く、末尾 3 文字は数字であることが保証されています。 そのため、文字列の4文字目から6文字目までの部分文字列を数字に変換して条件を満たすか値かどうかを調べればよいです。 B -…
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回ずつ行うと、たとえばのとき回程度になるため時間がかかりすぎます。そこで、 の場合、 を で割った商と余りを求めます。 回の操作で、 になるので、 であれば…
atcoder.jp 条件の整理 並び替えで と が一致するためには、少なくとも と で値の出現回数が一致する必要があります。 一致しない場合は、「No」です。操作前に、 の各組が同じ位置のとき、操作後には の組み合わせになります。 並び順は問題にしていないの…
atcoder.jp どんな操作？ 具体的に考えてみます。 で最初 を選んだとします。 1回目の操作で、 になります。 2回目の操作で、 になります。 3回目の操作で、 になります。 4回目の操作で、 になります。 4回の操作で最初に戻るので、周期4の繰り返しになりま…
atcoder.jp条件1 条件2 条件1,2を満たす最小のを求める問題です。 を決めると、条件2から となります。(ceilは小数点以下を切り上げる関数) の最小値を問われているので、 の最小値だけを考えて を調べればよいです。 また、は入れ替えても条件は変わらない…
atcoder.jp求めるのは ですが、式のとおりにを求めてから和の計算をするのは効率が悪いです。 そこで、Sと一致する桁の位置を固定して、それ以外の桁の数を任意とする数のうち、 以上 以下になるのはいくつかを数えて、 これを桁をずらして和をとることを考…
atcoder.jp 期待値の求め方 昇順に並び替えたときの 番目の値が である確率を とすると、 求めたい期待値は、 です。与えられた数列の中で を満たす の個数を 個、 の個数を 個、 の個数を 個、 の個数を 個とします()。 個の を1以上以下の整数に置き換える…
atcoder.jp 嬉しい列になる条件 嬉しい列は、「並び替えによって同じ列を2度繰り返すようにできるもの」です。 同じものが2度あらわれることから、列の中の各数字は偶数個になります。 逆に各数字の個数がすべて偶数であれば「並び替えによって同じ列を2度繰…
atcoder.jp 二分法探索 N本とM本の組み合わせですが、最大で となりうるため、すべての組み合わせを計算して、ソートして 番目を求めるのは時間がかかりすぎます。 番目を求めたいけれど、ソートするのが大変な場合、二分法で探索することを考えます。ある濃…
atcoder.jp 範囲で調べる 圧縮された配列を元に戻して (最大長さ ) 2つの配列の各要素を比較するのは時間がかかりすぎるため、圧縮した情報のまま数えていきます。ある値が、配列の何番目から何番目までの範囲になるかは、 の累積和から決まります。 ごとに…
atcoder.jp 問題文の内容把握 問題設定がわかりずらいですが、整理すると、各人について 3つの状態があります。 (A) 呼ばれていない (B) 呼ばれて、受付前 (C) 受付済イベントは3種類ありますが、イベント1 は状態(A) ⇒ (B) への遷移、イベント2は状態 (B) ⇒…
atcoder.jp b 進法での表記 N を b 進数に変換するには、それ以上割れなくなるまで繰り返し b で割り、余りを逆順に並び替えます。この結果が、 0 , 1 のみで表される場合に条件を満たすことになります。2進法は、必ず条件を満たします。N進法では 10, N-1進…
atcoder.jp 等比数列の和の公式が使えるか 問題は、 の を求めよというものです。 これは等比数列の和の公式から となり、 を計算すればよいように思えます。 この計算は、 と を求めて掛け合わせる計算になります。 は の逆元で、 を満たす のことです。こ…
atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 ロープを頂点とみなして、同じグループに属する頂点を木構造で表現することを考えます。Union-Find 木の表現と…
atcoder.jp二分探索で求める方法もありますが、ここでは直接求めていきます。平面上で (0,0), (A,0), (A,B), (0,B) を頂点とする長方形の内部に入る正三角形を考えていくことにします。 1辺の長さが の正三角形の頂点の一つを原点(0,0) におくと、残りの2つ…
atcoder.jp 単純グラフ：多重辺も自己ループももたないグラフ 有向グラフ：辺に向きがある（矢印）グラフ条件から、「頂点 b を中心として、"入ってくる辺 a → b"と"出ていく辺 b → c"の各ペアについて、 bの相手の頂点を直接結ぶ辺 a → c が無ければ追加す…
atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 同じグループに属する頂点を木構造で表現することにして、頂点 x の親を parent[x] に記録していきます。 頂点…
atcoder.jp 通れない都市があるという制約を考えないとき 移動は一方向で逆方向には進まないため、番号が小さな都市から順に「都市1から都市iに移動するまでのテレポート回数の最小値」を決定する動的計画法が使えます。 都市 i から 都市 i+k に直接移動可…
atcoder.jp 有向グラフとみなしてみる 数の大小関係 を小さいほうから大きいほうへ向かう向きを持った辺と考えると、有向グラフとして扱うこともできます。 問題は、有向グラフをトポロジカルソートして、順序が一意に定まるかどうかです。頂点 が出力辺のみ…
