はじめに この記事はNAIST Advent Calendar 2022 の 18日目 AtCoder problemsで300日ストリークを続けてみた の記事です。 みなさんプログラムを書いてますか？ 毎日なにかしらプログラムを書いていたいタイプなんですが、実際のところは調べる時間が必要だ…

これは好きなタイプの問題でした。かなり。 問題 頂点の木が与えられる。以下のクエリを処理したのち、各頂点の情報を出力せよ。 のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。 のとき : 頂点 から…

問題 個のボールが与えられる。ボールは、座標軸上に位置し、その色はである。 座標軸を移動しながらボールの色が広義単調増加となるように回収する時、移動するコストを最小化せよ。 atcoder.jp 考察 色ごとにDPしたくなるが、各色と次の色の間ですべての推…

11月一度もブログ投稿してないけど、問題自他はこまめに解いてました。 思い出すシリーズです。 問題 長さの2つの数列が与えられる。 個のクエリに答えよ。 : の先頭個の値の集合との先頭個の値の集合が等しいかどうかを答えよ atcoder.jp 解法 クエリにオン…

問題 個の数列が与えられる. を求めよ.atcoder.jp 解法 問題文から上記の言い換えは比較的容易.後はこれを埋めて行けば良い. これが茶diffと聞いてインフレもここまで来たか…と思ったが、実際は通るらしい.これでは面白く無いので、解法を考えてみよう.区間…

問題 頂点辺の連結な単純無効グラフが与えられる。グラフ上の頂点に向かう単純パスが一意に定まるか判定せよatcoder.jp 解法 頂点辺というのがポイント。辺の数がだった場合、任意の二つの頂点を結ぶ単純パスは一意に定まる。言い換えると、この場合は木にな…

問題 長さの整数列が与えられる． を満たすすべての整数について，を求め，その最小値を答えよ atcoder.jp 解法 解法1 なので，個の数字をstd::setで管理すれば解けるSubmission #33224842 - AtCoder Beginner Contest 194 解法2 上記の解法では，更新部分は…

問題 個の区間が与えられる。個の区間が重複していた数を答えよ。 atcoder.jp 解法 まず最も簡単な愚直な解法を考えてみる。 の区間をすべて全探索してしまい、かぶっている区間の数を数え上げて、最後にそれを答えとしてしまえば良い。 この解法はTLEとなる…

問題 長さ の数列が与えられる。以下の操作を回繰り返す。 ・ 最初の数をとする。 に を追加する。 を答えよ 解法 愚直にシミュレーションするのは自明にTLEとなる。 よく考えると、追加されるのはで割ったあまりを添え字とする数列である。この数は、たかだ…

注意事項 はじめに NAISTの環境（物理） アクセスといろいろな環境とか 食堂・コンビニ 図書館 NAISTでの環境（研究とか） 学校での生活 授業 チューター 中間発表 研究室 研究室の環境（物理） 研究室の環境(not 物理) 私生活 コロナウイルスによる諸々 就…

問題 atcoder.jp 解法の前のお勉強 辺のコストの持ち方以外は難しくない。制約的に、Dijkstra法を用いることで解ける。さて、問題はコストが負になりうるという点である。 Dijkstraのアルゴリズムは、負の辺があると動作しない。ならば、負の辺を消してしま…

問題 大事なところだけ抜粋すると、 を個の2つの組に分ける通り数答えよ。atcoder.jp 解法 2つの組というところがミソで、うまく数え上げることができなかった。 例えば、{ (1,2), (3,4) } と{ (2,1), (3,4)} は同じになる。 これを回避するには、各要素の右…

問題 長さの数列が与えられる。 の連続する部分列を一つ選び、これを一度flipする。 スコアをに含まれる1の個数とするとき、の取りうる値が何通りあるか求めよ。atcoder.jp 考えたこと ・答えの候補はたかだか程度なので、全部試せる ・最大値さえわかれば良…

問題 atcoder.jp 解説 尺取法で解ける．いつもサボるのでちゃんと書いておこうともう． 半開区間( )で区間を管理しながら行う． 尺取法は，ある条件を満たす区間をできるだけ伸ばして，条件が合わなくなったら左の区間を縮めていく． 更新のタイミングが（個…