グラフ
AtCoder Beginner Contest 335 (ABC335) のE問題 (Non-Decreasing Colorful Path) の解説記事です。
問題 個の町があり、これらの町の間には 本の道路があり、道路 は町 と町 を結び、その長さは である。 また、どの町にも必ず自転車が1台売られており、町 での自転車の速度指標は である。 ここで速度指標とは、その自転車を使用することにより掛かる時間の…
AtCoder Beginner Contest 333 (ABC333) のD問題 (Erase Leaves) の解説記事です。
問題 頂点からなる木構造のグラフと、整数 が1個ずつランダムに入った順列 が与えられる。 ここで、グラフ内の頂点 の距離を とする。 組の整数 が与えられるので、そのそれぞれについて が成立するような が の中に含まれるか判定せよ。 入力 まず最初の1行…
問題 木構造のグラフとは、 ループを含まない 頂点 辺のグラフのことを指す。 頂点の木構造のグラフに対して、 日間で整数 が1日ごとに与えられる。 また、グラフは1日1回までなら、以下の操作を行うことができる。 ある頂点 と、 に隣接している頂点 と隣接…
問題 頂点の木があり、頂点は と、辺は と番号をつけられている。 また、辺 (ただし、 )は頂点 と頂点 を結んでいる。 を満たすすべての整数組 に対して、以下の値の総和を求めよ。 頂点 から出発し、番号が 以上 以下である辺のみを 本以上辿って到達でき…
問題 から までの番号がついた 人の人がいる。 「人 は人 よりも背が高い」という情報が 個与えられるとき、これらの情報に矛盾がないかを判定せよ。 入力 まず最初の1行目には、整数 が与えられる。 次の 行については、順に整数 が与えられる。 条件 出力 …
問題 パーティーに 人の参加者がおり、 人目の参加者は 個のキャンディを持っている。 このパーティーにて、キャンディの交換会を開催する。 交換会では、各参加者は以下の作業を必ず1回ずつ行う。 整数 (ただし、 )と非負整数 を選び、 番目の人に 個のキ…
問題 あなたは から までの番号が付けられた 匹の動物の所有者である。 しかし、動物の維持費は高いので、全ての動物を売却することにした。 ここで、それぞれの動物は、ある特定の1匹の動物を非常に恐れていることが分かっている。 正確には、動物 は動物 …