■考えたこと 制約的に何歩で(X,Y)に行けるかを愚直に シミュレーションする方針で解けると推測。ACしたコードは下記。 using ll = long long; int main() { int r, x, y; cin >> r >> x >> y; ll l = (ll)x * x + (ll)y * y; ll r2 = (ll)r * r; ll ans = 1;…

■考えたこと 制約的に全探索と思った。 再帰で実装した。ACしたコードは下記。 struct Edge { int to; ll cost; Edge(int to, ll cost) : to(to), cost(cost){} }; int main() { int n, m; cin >> n >> m; vector<vector<Edge>> g(n); for (int i = 0; i < m; i++) { int </vector<edge>…

■考えたこと y座標が同じ座標ごとにまとめれば見通しが良くなる。 まとめ後はx座標とR/Lのペアでデータを持ち、昇順でソートしてRLのペアが 存在するか判定すればOK。ACしたコードは下記。 int main() { int n; cin >> n; vector<int> x(n), y(n); for (int i = 0</int>…

■考えたこと全探索をすると計算量O(HWN) = O(125 x 10^6)であり間に合うか心配だったが この方針で実装してACした。ACしたコードは下記。 int main() { int h, w, n; cin >> h >> w >> n; string t; cin >> t; vector<string> s(h); for (int i = 0; i < h; i++) cin</string>…

■考えたこと dpのような気がしたので入力例1の値で以下の表を書いてみた。 9 1 8 6 3 2 7 9 2 5 i \ j 0 1 0 true true 1 true true 2 true true 3 true false 4 false true dpの定義は以下。 dp[i][j] = A[i][j]が条件を満たすかどうか。 dp[0][0] = dp[0][…

■考えたこと問題文を読んでも解法が思いつかなかった。とりあえず入力例1で周遊パスを買っていったときの様子を紙に書いてみた。 1日周遊パスは2枚セットで10円で販売されているので各セット購入したとすると・0セット：7 + 1 + 6 + 3 + 6 = 23円・1セット：…

■考えたこと蟻本のLake Counting (POJ No.2386) と同じ問題。とりあえずdfsで連結しているセンサーをなめていき(訪れたセンサーはtrueにしておく) 再帰終了後、カウントを足すという方針で解いた。ACしたコードは下記。 const int di[] = { 1, 0, -1, 0, 1, …