解説見ても計算量について理解できなかったので、自分なりに考えたものの備忘録。atcoder.jp 問題 長さ の整数列 が与えられる。 これを並び替えた数列を として、次の条件を満たすものの総数を で割った余りを求める。ただし、重複する要素は区別する。 ・ …

リンク atcoder.jp 問題概要 頂点有向グラフが与えられる。 グラフの頂点をランダムに選び、選んだ頂点から到達可能な頂点を消す作業を、グラフが空になるまで繰り返す。 このときの操作回数の期待値を求める。 制約 (考察) 同じような考え方を用いる問題を…

問題へのリンク (問題内容は省略) atcoder.jp 考察 想定解ではなかったが、汎用性がありそうなのでメモしておく。各クエリに対して効率的に求めたいが、 をそのままにして考えるのは難しい。( 例えば、 について昇順でソートしても、 について単調性がある保…

atcoder.jp 問題概要 '0', '1', '?' からなる長さ の文字列が与えられる。 '?' には、'0' または '1' が入れられる。 それを埋めた '0' と '1' からなる文字列の任意の連続部分列の中で '0' と '1' の個数の差が 以下となる文字列の個数を で割った余りを求…

atcoder.jp 問題概要 長さ の整数列 がある。 を満たすすべての整数 に対して、次の問題を解く。 整数 に対して、, ( or ) を満たす の最大値を求める。ただしここで or はビットごとの論理和を表す。 制約 考察 → 実装 ある を見ているとき、最大値に関わり…

昨日の ABC155 の D 問題の類題であり、D 問題はこれを引っ張ってきて何とか通せた。 実装を無限にバグらせて、通ったのコンテスト終了 10 分前くらいだけど… atcoder.jp 問題概要 長さ の数列 が与えられる。 の計算で現れた 個の値を昇順で並べたときの 番…

排他的論理和 (XOR) は桁上がりのない加算 (ﾌﾞﾝｯﾌﾞﾝｯ ←素振り音)atcoder.jp 問題 要素数の数列が与えられる。 XOR をで割った余りを求めよ。 制約 入力値はすべて整数である。 考察 → 実装 で解けるなら、なんてことはない問題であるが、制約上厳しいものが…

atcoder.jp 【問題の概要】 が与えられる。 を両端とした要素数 個の数列を考える。 このとき、隣り合う要素の差が 以上 以下であるような数列を作ることは可能であるかを判定せよ。 未定の要素に対して、大小の制限はない。 【考察】 よく分からないので、…

atcoder.jp【問題の概要】 番号1から番号Nの人がいて、トーナメントで番号1の人が優勝した。番号2から番号Nの人に関しては、どの番号の人に負けたかという情報が与えられる。この情報と矛盾を生じないトーナメントで、その深さが最小であるときの深さを出力…