酒入ってたけど、入ってなくても思いつかなかったな。codeforces.com 問題概要 つの 文字列で 文字でも一致する状態を "a bit similar" であるとする。 文字列 が与えられたとき、 から得られる長さ の部分文字列すべてに対して "a bit similar" である辞書…

難しい、全然分からんかった。 リンク codeforces.com 問題概要 (雑) 長さ の区間があり、 個の区間が の形式で与えられる。これらの区間を つのグループに分けることを考える。(各区間はただ一つのグループに属し、複数個には属さない。) 各グループでは長…

こういう問題を素早く解けるようになりたい。 リンク codeforces.com 問題概要 の 個の街がある。街 には の確率で電波塔が設置される。電波塔のパワー は自由に設定でき、距離が 未満の街に電波が供給される。街 と街 には電波が供給されず、 に重複なしで…

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

問題へのリンク atcoder.jp 問題概要 の収納スペースと、既に片付けられている 個のマスコットの配置が与えられたとき、残りのマスコットの片付ける方法を で割った余りを求める。 ただし、途中で長方形ができるだけ多くなるように並べる。 制約 考察 長方形…

隣接 項間漸化式の一般項 の値を高速に求める手法を最近知ったのでメモをしておく。 一般項を求めるのは、 行列で行列累乗を用いると、 で求めることができる。 ただ、きたまさ法と呼ばれる手法を用いれば、 で求めることができる。表記など怪しいので、詳し…

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

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

DP は比較的すぐに浮かんだのに、復元できなくて詰んだ、反省。 リンク D. Nastya and Scoreboard codeforces.com 問題概要 上図のように数字を点灯させることができる Scoreboard がある。 個の Scoreboard の状態が与えられるが、新たに 個点灯させたとき…

問題へのリンク C - Eugene and an array codeforces.com 問題概要 長さ の数列 が与えられる。区間の和が となる連続部分列を含まない連続部分列の個数を求めよ。 制約 考察 ある条件を満たす数え上げの問題である。 本番では、さっと順序立てて書けずに、…

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

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

本渡楓と楠木ともりの FUN'S PROJECT LAB のイベントに行ってきた。 あまりチケットが取れる期待していなかったのだが、昼の部と夜の部ともに取れた。 本渡上陸作戦は単独イベントまで 4 年いかないくらいかかったのに、ゲストがいるとは言え 1 年足らずで単…

Codeforces で青になった。 上振れすぎだが素直に嬉しい。 Atcoder まだ緑なんだけど… ここ数日やる気がなさ過ぎて、何もできていない、やばい。 こんなんでは維持できないなあ…

競技プログラミングというか、ほとんど高校数学の話ではあるが… 解いた問題のことを書きたいが、気力がないので、簡単な話でお茶を濁しておく。任意の底の対数を計算したいが、C++ ではそのような関数は用意されておらず、底の変換公式に従って計算する必要…

Codeforces でこの操作が必要な問題があり、それにかなりの時間を取られていたら終わってしまったので、メモしておく。 問題の説明などを書く気力がないので、操作方法だけ記す。 問題のリンク : Problem - D - Codeforces例えば、 回の操作で から のいずれ…

atcoder.jp 問題の概要 匹のスライムが横一列に並んでいて、左から 番目のスライムの大きさは である。 隣り合う 匹のスライムを合体させて、 匹のスライムにする。 このとき、 匹のスライムの大きさを とすると、 のコストを支払う。 また、合体後の大きさ…

atcoder.jp 問題 から の番号が振られている 枚の皿があり、皿 には 個の寿司が置かれている。 すべての寿司がなくなるまで、次の操作を繰り返す。 の目が等確率で出るさいころを振り、出目を とする。皿 に寿司がある場合、皿 の寿司を 個食べる。皿 に寿司…

書いたことはあったが、やり方を忘れていて悲しかったので、簡単にまとめておく。DAG (Directed Acyclic Graph) とは、閉路を持たない有向グラフのことを指す、有向非巡回グラフである。 トポロジカルソートとは、この DAG の頂点をどのノードもその出力辺の…