操作によって作れるものの集合を考える(判定関数を考える)
最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった！ 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …
これをグラフの問題だと思えるかどうか！ 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…
これを本番間に合わせられたなかったのは辛かった... あと、数え上げパートがあんなにスマートにはできなかった。無限に から落とせなかった... 問題へのリンク 問題概要 黒石さんと白石さんは、一列に並んだ 個のマスからなる盤面を使って遊んでいます。 マ…
最初与えられる文字列が高橋くんの手だと勘違いして、サンプル 2 が無限にわからないとなっていました。 clar でお騒がせいたしました...ありがとうございます。 問題へのリンク editorial 問題概要 高橋くんと青木くんがジャンケンを 回行う。青木くんの出…
コンテスト中に間に合わなかった。あと、僕の考察は XOR の言葉ではなかったけど、よく考えたら XOR と等価だった。 問題へのリンク 問題概要 "A", "B", "C" のみからなる長さ の文字列 が与えられる。この文字列に以下の操作を好きな順序で好きな回数だけ行…
11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…
面白かった！！ 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます． の連続する 文字を選んで，それらをすべて 0 にす…
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…
これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …
これ系、この問題以降はたくさん見るようになったけど、この問題が先駆けとなった気がする 問題へのリンク 問題概要 'a', 'b', 'c' のみからなる長さ の文字列 が与えられる。 に以下の操作を好きな順序で好きな回数だけ行って得られる文字列が何通りあるか…
実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という！！！ 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…
めちゃくちゃ楽しかった 問題へのリンク 問題概要 長さ の数列を 個用意する。ただしこれらのなす 個の値は が 1 個ずつ登場するようにする。これらの数列から以下の操作を繰り返して、長さ の順列を作る。 空にならずに残っている数列のうち、先頭の要素の…
「操作によって出来上がるものが何通りあるか？」という問題では、まず判定問題を考える！(素振り) 問題へのリンク 問題概要 のグリッドがあって、各マスは白または黒に塗られている。以下の操作を好きな順序で好きな回数だけ行った結果得られる盤面が何通り…
マトロイドだ！！！！！！！ 問題へのリンク 問題概要 のボード上の 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。 今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。 最…
最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。 こういう問題を作れるのはすごい。 問題へのリンク 問題概要 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべ…
ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
本番これを間に合わせられなかったのが悔しい 問題へのリンク 問題概要 円周を 等分して、それぞれの弧を赤か青に塗る方法のうち、 'R' と 'B' のみからなる長さ の文字列 が与えられて 円周上のどの端点から出発しても弧を順番に左右どちらかに 回たどって…
かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…
コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だった...... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか？ (998244…
すごく面白かった！ 問題へのリンク editorial スコア: 191.85 / 500.00 問題概要 "I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して = "I" = "O" = "I" が成立することと定義する (1-indexed)。 いま、"I", "O", "?" のみか…
