AOJ 0011 Drawing Lots
問題概要
w個の縦棒、n個の横棒で構成されるあみだくじがある。
横棒iは、aiとbiをつなぐ。
横棒は、上に存在するものから与えられる。
制約
- w ≤ 30
- n ≤ 30
解法
まず、始めに横棒が1本もない場合を考える。
その場合、i番目の縦棒から始めるとi番目の縦棒へと行き着くことは明らかである。
次に、1つの横棒があり、縦棒1と縦棒2をつなぐとすると、縦棒1から始めると縦棒2へと行き着き、縦棒2から始めると縦棒1へと行き着く。
つまり、2つの縦棒の結果を交換することになる。
複数の横棒がある場合でも、これが成り立つので、n個の横棒について、iが小さい順に交換を行うことで最終的な結果が得られる。
コード
#include <iostream> #include <algorithm> using namespace std; int main() { int w, n, a, b; char c; cin >> w >> n; vector<int> v(w); for (int i = 0; i < w; i++) { v[i] = i+1; } for (int i = 0; i < n; i++) { cin >> a >> c >> b; a--; b--; swap(v[a], v[b]); } for (int &x: v) { cout << x << endl; } return 0; }