Nachia さんの考えたアルゴリズムを実装しました。 www.mathenachia.blog 注意 簡単なランダムチェッカーを通しています。 時間計算量については確認していませんが、ACPC 2021 Day2 J を AC することはできました。 下のコードはグラフが入力された場合に答…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367&lang=ja 解法 ネットワークはマシンを頂点としケーブルの太さを各辺の重みとする木と考えます。 add クエリが扱いにくいので、各頂点 に対し整数 を辺 の重みが常に となるようにすると、ad…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2733 公式解説とは異なる解法で解きました。 問題概要 個の同じ大きさの立方体で構成された幅 、高さ 、奥行き の立方体がある。 を満たす各 について、左から 番目・下から 番目・前から 番目の…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1198&lang=ja 解法 のうち一方のみが含まれる円が 1 つ以上存在する場合、 と をその円と交差しないように結ぶことはできないので、答えは明らかに NO となります。 がともに 1 個以上の円に含ま…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1352 問題概要 座標平面上に半径 の円形のロボットがあり、その中心を原点からある点に移動させたい。ただし、ロボットと重なってはならない点が 個指定される。ロボットの最短移動距離を求めよ…

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp 解法 2 台のロボットの距離が 未満になったり 以上になったりすることが発生する時刻をすべて列挙することを考えます。 ロボットの組を全探索します。ロボットが 2 台とも動いてい…