torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

2020-11-16から1日間の記事一覧

AtCoder Beginner Contest 183, F : Confluence

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_f 問題概要 $N$ 人の人がいて,人 $i$ はクラス $C_i$ に属している.以下の 2 種のクエリを処理せよ. クエリ 1 : 人 $a, b$ が含まれる集団が合流する クエリ 2 : 人 $x$ が属している集団で,ク…

Weighted-Union Heuristic

はじめに 界隈で「データ構造をマージする一般的*1なテク」と呼ばれている技法があります.``Introduction to Algorithms'' [1] では Data Structure for Disjoint Sets の章で ``Weighted-Union Heuristic'' として挙げられています. hatena diary の終了…

AtCoder Beginner Contest 183, E : Queen on Grid

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_e 問題概要 高さ $H$ ,幅 $W$ のグリッド状の盤面を考える.セル $( i, j )$ は空白か壁かのいずれかである. この盤面の位置 $( 1, 1 )$ に駒が置かれている.駒は,右,右下,下のいずれかの方向…

AtCoder Beginner Contest 183, D : Water Heater

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_d 問題概要 給湯器がひとつあり,毎分 $W$ リットルのお湯を出せる. 給湯器を使いたい人が $N$ 人いて,$i$ 番目の人は時刻 $S_i$ から $T_i$ まで($T_i$ 丁度は含まない),$P_i$ リットルのお湯…

AtCoder Beginner Contest 183, C : Travel

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_c 問題概要 $N$ 個の街があり,街 $i$ から街 $j$ へ移動するのにかかる時間は $T_{i,j}$ である. 街 $1$ を出発して,街 $1$ 以外のすべての街を丁度一度ずつ訪問してから街 $1$ に戻ってくるルー…

AtCoder Beginner Contest 183, B : Billiards

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_b 問題概要 二次元空間を考える.$X$ 軸は鏡面である. ここで,$( S_x, S_y )$ から光を発射して,鏡面に反射させ,$( G_x, G_y )$ に光を届けることを考える.鏡面にぶつかるときの $x$ 座標の値…