torus711 のアレ

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

BFS

AtCoder Beginner Contest 339, D : Synchronized Players

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_d 問題概要 $n \times n$ のグリッド状の盤面があり,各セルは空きマスまたは障害物である.また,2 つの駒が盤面の(相異なる)セルに置かれている. 駒たちに対し,以下の操作を適用することがで…

AtCoder Beginner Contest 292, E : Transitivity

問題文 https://atcoder.jp/contests/abc292/tasks/abc292_e 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる. 以下の操作を考える. グラフ $\hat G = ( V, \hat E \leftarrow E )$ を用意する 以下の操作を可能な限り適用する 相異なる頂点 $u, v, …

AtCoder Beginner Contest 245, F : Endless Walk

問題文 https://atcoder.jp/contests/abc245/tasks/abc245_f 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる. 頂点 $v \in V$ であって,$v$ を始点として $G$ 上で無限に(辺に沿った)移動を繰り返すことができるものの個数を求めよ. 制約 $1 \le…

AtCoder Beginner Contest 184, E : Third Avenue

問題文 https://atcoder.jp/contests/abc184/tasks/abc184_e 問題概要 $H \times W$ のグリッド状の迷路がある.空きマスは,単なる空きマスと,英小文字が書き込まれたものがある. 移動は 上下左右の隣接するマスへ移動する 現在地に書かれている文字と同…

AtCoder Grand Contest 044, B : Joker

問題文 https://atcoder.jp/contests/agc044/tasks/agc044_b 問題概要 $N \times N$ のグリッド状の盤面の各セルに人が $1$ 人ずつ,合計 $N^2$ 人いる.人は $1$ から $N^2$ の整数で,左上から row-oriented で番号付けされている. 入力でサイズ $N^2$ の…

AtCoder Beginner Contest 168, D : .. (Double Dots)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_d 問題概要 $N$ 頂点 $M $ 辺の連結な重み無し単純無向グラフが与えられる.各頂点に以下の条件を満たす「道標」を設定せよ. 道標は隣接する頂点を指す 道標が指す頂点への移動を繰り返すとき,頂…

TopCoder SRM 670, Division 1, Level 2 ( Division 2, Level 3 ) : Treestrat

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13990&rd=16550 問題概要 $N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする.プレイヤーを A, B として,A は赤いトークンを,B は青いトークンを使う. 木の頂点は $0$ から $…

TopCoder, Single Round Match 646, Division 2, Level 2 : TheGridDivTwo

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278 問題概要 今,無限に広い 2 次元空間の原点にいる.1 回の移動では 4 近傍(上下左右)のいずれかの方向に距離 1 移動することができる. 平面上のいくつかの座標はブロッ…

TopCoder, SRM 637, Division 2, Level 2 : PathGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13506&rd=16080 問題概要 グリッド状の盤面を使ったゲームをする。盤面の高さは 2 で固定であり、横の長さは正整数で表される。また、盤面上の各セルは黒または白に塗られている。初期状…

AtCoder Beginner Contest #007, C : 幅優先探索

問題文 http://abc007.contest.atcoder.jp/tasks/abc007_3 問題概要 迷路が与えられる。スタート地点からゴール地点へ移動する最小手数を求めよ。(問題文参照)

TopCoder SRM 612, Division 1, Level 1 : EmoticonsDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845 問題概要 丁度一つの顔文字を含むテキストファイルを、次の三種類の操作によって編集する。 全ての文字列をクリップボードにコピーする クリップボードの文字列をバッファ…

Codeforces #192, Division 2, A ( Division 2, B ) : Biridian Forest

問題文 http://codeforces.com/contest/330/problem/D 概要 R * C のグリッド状のマップがある。 マップには一つの出口があり、主人公が一人いる。 その他のセルは木があって通れないか、何もないかである。 何もないセルには 0 から 9 人の敵がいる。 主人…

TopCoder SRM 583, Division 1, Level 1 : TravelOnMars

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12608&rd=15503 概要 リング状に N 個の街がある。 i 番目の町からは距離 以内の街へ一回で移動できる。 スタート地点とゴール地点が与えられたとき、最小で何回移動する必要があるか求め…

TopCoder SRM 574, Division 2, Level 2 : TheNumberGameDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12485&rd=15494 概要 数に対して、以下の二つの操作を定義する。 数を反転する 数を 10 で除し、剰余は切り捨てる 二つの数 A, B が与えられる。 上記の操作で A を B に変換するとき、必…

AtCoder Regular Contest #011, C : ダブレット

問題文 http://arc011.contest.atcoder.jp/tasks/arc011_3 概要 ある単語について、文字を一文字置換する操作が許される。 与えられた辞書を使って、start から last まで変換するときの手順を求めよ。

Codeforces #149, Division 2, C : King's Path

問題文 http://codeforces.com/contest/242/problem/C 概要 × のチェス盤にキングが置かれている。 キングを ( x0, y0 ) から ( x1, y1 ) まで移動させたい。 使用可能なセルの情報が与えられるので、最小の移動回数を出力せよ。 移動できない場合は -1 を出…