2014 Yandex.Algorithm Elimination Stage, Round1 D - Splitting Money
問題概要
n 個の数列が与えられる．
各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる．
最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなるようにしたい．
そのような集合AとBは何通りあるか．ただし，同じ数字であっても，元の数列で違う位置にあるものであれば，それらは区別するものとする．
・制約
1 <= n <= 10^4
1 <= a_i <= 10^4
解法
まず，数字の値が小さいことに注目する．
また，集合AのXORと集合BのXORが等しいとは，そもそもどちらかの集合に含めるとしたすべての要素のXORが0であることと同値である．
そのように数字を選んだ場合，各要素をどちらに振り分けても，それぞれのXORの値は等しくなる．
以上の2つから，以下の dp で計算することができる．
dp[i][j] := i 番目の要素まで見て，どちらかの集合として使う要素の XOR の値が j となるような値の振り分け方
ある数字を集合として使う時，どちらの集合に入れるかで2通りあるので，遷移は
dp[i + 1][j ^ a[i]] += dp[i][j] * 2
となる．
計算量は O(n * a_i) ．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 1e9 + 7; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> dp(1 << 14); dp[0] = 1; for(int i = 0; i < n; ++i) { auto nxt = dp; for(int j = 0; j < (int)dp.size(); ++j) { const int x = j ^ a[i]; if(x < (int)nxt.size()) { (nxt[x] += (2 * dp[j]) % mod) %= mod; } } dp = move(nxt); } cout << dp[0] << endl; }
2014 Yandex.Algorithm Elimination Stage, Round1 C - Non-Convex Quadrilaterals
問題概要
n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする．
もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする．
こうしてできる四角形のうち，凹四角形であるもののなかで，周の長さが最も大きいものの値はなにか？
・制約
1 <= n <= 10^4
1 <= a_i <= 10^8
解法
実際に四角形を書けばすぐわかるが，ほとんどの四角形はいい感じに変形すると，
おなじ4辺をもつ凹四角形に変形できる．
したがって，基本的に四角形が作れるならそれは凹四角形にできるから，数字の大きい方から4つ選んでいって，実際に四角形を構築できるか考えれば十分である．
四角形が構築できる条件は，4つの辺のうちの最大の長さが他の3辺の長さの和未満であることである．
コーナーケースが1つあり，それは正方形である．これはどう変形しても凹四角形にできない．
計算量はソートの分で O(nlogn)．
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } sort(rbegin(a), rend(a)); int ans = -1; for(int i = 0; i + 3 < n; ++i) { if(a[i] == a[i + 1] && a[i] == a[i + 2] && a[i] == a[i + 3]) continue; // square int sum = 0; for(int j = i + 1; j <= i + 3; ++j) { sum += a[j]; } if(sum > a[i]) { ans = a[i] + sum; break; } } cout << ans << endl; }
2014 Yandex.Algorithm Elimination Stage, Round1 B - Adjusting Ducks
問題概要
n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える．
この操作によって，数列に含まれる値として，単独で存在するものがないようにしたい．最小のコストはいくらかかかるか？
・制約
1 <= n <= 10^5
1 <= a_i <= 10^8
解法
基本的には値の近い2つの数字をペアにしていけば良さそうである．
よって，最初にソートして以下の dp をした．
dp[i][j] := i 番目の要素まで見て，その要素が直前の要素に変えられたか，あるいは直前の値を今見ている値に変えたかとしたときの最小コスト．
今見ている要素に直前の値を合わせる時，そのさらに前の（つまり2個前）要素は，今見ている要素に合わせるのは明らかに不利である．なぜなら，その場合は直前の要素に今の値を合わせたほうがコストが小さく済むからである．
したがって，この場合は2つ前の要素は，今見ている要素とは無関係に考えてよい．
次に，今見ている要素を直前の値に合わせるときは，同じような理由で2つ前の値は直前の値に変えられていると考えて良い．
この遷移のやり方だと，今見ている値を直前の値に合わせて，かつ2つ前の値をその前の値に合わせるようなものを考えていないようだが，実は問題ない．なぜなら，これは直前の値を今見ている値に合わせたのと同じだからであり，これは先程の遷移に含まれているからである．
以上で O(N) でこの問題をとくことができる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <typename T> constexpr T inf; template <> constexpr ll inf<ll> = 1e18; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } sort(begin(a), end(a)); vector<vector<ll>> dp(n + 1, vector<ll>(2, inf<ll>)); dp[1][0] = dp[1][1] = abs(a[0] - a[1]); for(int i = 2; i < n; ++i) { dp[i][0] = dp[i - 1][1] + a[i] - a[i - 1]; dp[i][1] = min(dp[i - 2][1], dp[i - 2][0]) + a[i] - a[i - 1]; } cout << min(dp[n - 1][0], dp[n - 1][1]) << endl; }
感想
変な dp をしてしまったが，もっとわかりやすいのがありそう．うーん．
C++11で始めるマルチスレッドプログラミング その2 std::mutex 編
はじめに
本記事は
C++11で始めるマルチスレッドプログラミングその1 ～std::thread事始め～ - すいバカ日誌
の続きとなる記事です（何年越しだよ）．
今回は std:;mutex による基本的な排他制御について書きます．
本記事を書いた時点では C++17 がもう策定されていますが，タイトルはC++11のまま行きます．
排他制御について
異なるスレッドが同じリソースを共有するような場面は当然発生します．
しかし，異なるスレッドが共有リソースに対して同時にアクセス（すくなくとも1つは変更操作）をした場合，データ競合 (data races) が発生し，未定義動作となってしまうことがあります．ちなみに，data races は C++ の規格としてその定義が書かれているので参照してください．*1
データ競合が問題になる例として，双方向 linked-list (以下単に list と書く) を考えてみましょう．
list に対して erase 操作を行った場合，3つの要素（それ自身，直前，直後）のポインタをすげ替える必要があり，これらは命令として一度に実行することは出来ません．
したがって，それぞれの処理の間には，他のスレッドが入り込む余地があり，ここで問題が発生します．例えば直前の要素の next ポインタのみを挿げ替え終わっている時点で，他スレッドが直後の prev ポインタを参照する，ようなことは容易に想像できます．
このように，処理の途中段階では，データ構造の不変条件 (invariants) が崩れていることが多く，そのような状態でのデータ構造への操作は危険な操作となります．
したがって，共有リソースはデータ競合を防ぐための何らかの保護機能を用いなければなりません．
それには Lock-free なデータ構造や transactional なデータ構造を用いるという方法もありますが，今回扱うのは std::mutex (mutual exclusive) による排他制御です．
排他制御は，共有リソースに対しての同時（書き込み）アクセスが，ただ1つのスレッドしか許さないようにすることを言います．
std::mutex による排他制御
まずはサンプルコードから．
#include <iostream> #include <thread> #include <mutex> #include <vector> #include <string> std::mutex stdout_m; // std::cout の排他制御 template <typename T> void threadsafe_print(T v) { std::lock_guard<std::mutex> lock(stdout_m); std::cout << v << std::endl; } class widget { public: void heavy_process(int i) { std::lock_guard<std::mutex> lock(m); threadsafe_print("called heavy_process with: " + std::to_string(i)); std::this_thread::sleep_for(std::chrono::seconds(1)); v.push_back(i); } void print() { std::lock_guard<std::mutex> lock(m); threadsafe_print("called print"); for(auto x : v) { threadsafe_print(x); } } private: std::vector<int> v; std::mutex m; }; int main() { widget w; std::thread t1([&] { for(int i = 1; i <= 10; ++i) { w.heavy_process(i); } }); std::thread t2([&] { for(int i = 11; i <= 20; ++i) { w.heavy_process(i); } }); t1.join(); t2.join(); w.print(); }
このコードをもとに説明していきます．
stdout_m, widget::m, std::lock_guard
これらが今回の主役の std::mutex です．mutex を用いた排他制御では，アクセスの試み -> mutex を lock -> データに対する処理 -> 終了 -> mutex の unlock という流れになります．
lock, unlock は mutex から直接呼ぶことも出来ますが，RAIIを利用して書くのが安全です．std::lock_guard がそれに該当します（コンストラクタで lock，デストラクタで unlockする）．
stdout_m で std::cout を排他制御しないと，出力が混ざって見にくいのでそうしています．
widget::m については，各 widget オブジェクトごとに別となります．
mutex が lock されている間は，他のスレッドはその mutex を lock できません．
この場合，unlock されるまで待つことになります．これによって排他制御が実現します．
heavy_process, print
heavy 内部で std::vector にデータを追加します．これは他スレッドが同時に行うと問題なので，排他制御が必要です．
print 内部で v を参照していますが，ループの途中で heavy_process が呼ばれると v の状態が変わってしまうので排他制御が必要になります(途中でイテレータが無効になるかもしれない）．
std::this_thread::sleep_for
指定した時間だけ今のスレッドを sleep します．テストに便利なので今後もよく使うと思います．
以上でサンプルコードの解説は終わります．
試しに lock_guard を消してみると，たまに異常終了するのが観察できるので，いろいろ試して遊んでください．
スレッドセーフ性*2とデータ構造のインターフェース
マルチスレッド下での共有されるデータ構造の設計をすることになったとしましょう．
このとき，そのデータ構造のインターフェースは，注意深く設計する必要があります．
その点について確認するため，簡単なスレッドセーフなキュー safe_queue を実装してみましょう．
std::queue
よくある queue のインターフェースの一部を抜粋・簡略化して示します．
template <typename T, typename Sequence = std::deque<T>> class queue { public: explicit queue(); explicit queue(Sequence const& s); bool empty() const; size_t size() const; T& front(); T const& front() const; void push(T const&); void push(T&&); void pop(); };
front と pop が完全に分割されています（pop で先頭要素を return しない）が，これは Exceptional C++ などでも触れられているとおり，例外安全性を保つために必要な分割です．
この設計を何も考えずそのまま safe_queue に流用して良いでしょうか？
答えは No となります．
なぜだめなのか？
例えば以下のプログラムを，スレッドAとBが safe_queue に対して処理を行うことを考えます．
safe_queue<int> que; if(!que.empty()) { auto value = que.front(); que.pop(); // ... }
このとき，たとえは以下のようなフローが考えられます(empty, front, pop はそれぞれ std::mutex により排他制御されていると仮定します）．
(thread A) que.empty() の評価 (thread B) que.empty() の評価 (thread A) auto value = que.front(); (thread B) auto value = que.front(); (thread A) que.pop(); (thread B) que.pop(); // ???
thread B からの que.pop() は，予期した動作ではなさそうです．
というのも，thread A, B ともに見ている値は同じ que の先頭要素なのに対し，B が pop する値はまだ見ていない2番めの要素だからです．
このように，それぞれの関数内で std::mutex を lock したからといって，スレッドセーフなデータ構造が作れるという単純な話ではないのです．
解決策
std::mutex での排他制御を目指す場合，front と pop が分離されていると先に述べた問題が発生してしまうので，分離しないという選択を取ります．
ただし，例外安全性は保証したいので，多少コストを書けてどちらも実現する方法を考えます．例えば以下のようなものがあります．
- 引数の参照に対して pop が先頭要素を返す．デメリットは，呼び出し側で格納用の変数を宣言する必要があること．格納用の変数が作れないこともある（初期化に何らかの有効かつ意味あるデータが必要・初期化コストが無視できない）．
- 戻り値に pop されたデータを指すポインタを返す．ポインタのコピーには例外が発生しないことを利用．デメリットは，内部で何らかの形でポインタの管理が挟まるので，ゼロコストとは言えないこと．
今回はこの案を採用し，また front() は提供しないことにします．
safe_queue の実装例
class empty_queue : std::exception { public: const char* what() const throw() { return "Empty queue"; } }; template <typename T> class safe_queue { public: safe_queue() {} safe_queue(safe_queue const& other) { std::lock_guard<std::mutex> lock(other.m); que = other.que; } safe_queue& operator=(safe_queue const&) = delete; void push(T value) { std::lock_guard<std::mutex> lock(m); que.push(value); } void pop(T& res) { std::lock_guard<std::mutex> lock(m); if(que.empty()) throw empty_queue(); res = que.front(); que.pop(); } std::shared_ptr<T> pop() { std::lock_guard<std::mutex> lock(m); if(que.empty()) throw empty_queue(); auto const res = std::make_shared<T>(que.front()); que.pop(); return res; } bool empty() const { std::lock_guard<std::mutex> lock(m); return que.empty(); } size_t size() const { std::lock_guard<std::mutex> lock(m); return que.size(); } private: std::queue<T> que; mutable std::mutex m; }; int main() { safe_queue<int> sq; for(int i = 0; i < 1000; ++i) { sq.push(i); } std::thread t1([&] { while(!sq.empty()) { auto value = sq.pop(); threadsafe_print("[thread A] poped: " + std::to_string(*value)); } }); std::thread t2([&] { while(!sq.empty()) { auto value = sq.pop(); threadsafe_print("[thread B] poped: " + std::to_string(*value)); } }); t1.join(); t2.join(); }
まとめ
今回は std::mutex による排他制御の基本だけを扱いました．
ミューテックス自体の実装の話は
C++ミューテックス・コレクション -みゅーこれ- 実装編 - yohhoyの日記（別館）
がわかりやすかったです．
もしかすると次回に続くかもしれません（本当か？）．
*1:N4727 §6.8.2.1 Data races
*2:C++とスレッドセーフ性については yohhoy さんの記事スレッドセーフという幻想と現実 - yohhoyの日記（別館）が参考になります
Codeforces I. Photo Processing (2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest)
解法
求めたい値は二分探索で求めましょう．
あとはある x にたいして題意を満たす分割が可能か調べます．
写真の値はソートしておくと，題意の分割は連続部分列の分割になります．
その上で，以下の累積和を考えます．
dp[i] := 写真 [0..j] ( j <= i ) だけを考えた時，題意を満たす分割が可能な j の個数
写真 i について考えます．この写真は少なくとも i - k より左にある写真を含むような列に含まれなければなりません．また，vi - x 以上である値を持つ最も左の写真より左側の写真を一緒に含めることも出来ません．
r = i - k，l = (vi - x 以上の最も左の写真の位置) とすると，l から r の間でうまく分割できれば，この写真を分割することができます．
これは先程の累積和を使って言い換えると，l から r の間に dp[j] != dp[j + 1] となるような位置があれば良いということになります．
したがって，dp[l - 1] と dp[r] の値を比べて，それらが違えば間に分割できる位置があると判定することが出来ます．
計算量は O(N log V) です．
ソースコード
fn lower_bound<T: Ord>(v: &Vec<T>, first: usize, last: usize, val: T) -> usize { let (mut lb, mut ub) = (first, last); while ub - lb > 0 { let mid = (ub + lb) / 2; if v[mid] < val { lb = mid + 1; } else { ub = mid; } } return ub; } fn main() { let cin = stdin(); let cin = cin.lock(); let mut sc = Scanner::new(cin); let n: usize = sc.read(); let k: usize = sc.read(); let mut v: Vec<i32> = vec![0; n + 1]; for i in 1..n+1 { v[i] = sc.read(); } v.sort(); let v = v; let (mut lb, mut ub): (i32, i32) = (-1, 1e9 as i32); while ub - lb > 1 { let mid = (lb + ub) / 2; let mut dp: Vec<i32> = vec![0; n + 1]; dp[0] = 1; for i in 1..n+1 { dp[i] = dp[i - 1]; let l = lower_bound(&v, 1, n + 1, v[i] - mid) - 1; if i < k { continue; } let r = i - k; if r >= l && dp[r] > if l > 0 { dp[l - 1] } else { 0 } { dp[i] += 1; } } if dp[n] == dp[n - 1] { lb = mid; } else { ub = mid; } } println!("{}", ub); }
AOJ 0597 Xiao Long Bao
解法
汁が飛び散る範囲が小さいので，それを利用します．
ある連続する8個の区間を考えると，そのなかで各小籠包がどの順で食べられるかさえわかれば，答えを求めることができます．
7! = 5040 なので，以下の dp を考えます．
dp[i][p] := 右端を i 番目まで見た時に，そこから ( i 番目も含めて) 手前7個の食べる順番が p であるようなときの最大
ただし，p は順列です．
dp[i][p] の状態から遷移を考えます．区間内の小籠包が互いにどれだけ点数を与えるかはすでに求まっているということになるので，新しい i + 1 番目の小籠包を p に付け加えることになります．
付け加える前に，i - 6 番目（つまり左端）の小籠包は今後みるひつようがないので，取り除きます．この小籠包が x 番目に食べられるとするなら，区間内の y ( < x) 番目に食べられる小籠包を，y + 1 番目に食べられるということにしておきます．
つぎに，i + 1 番目の小籠包が，区間内で何番目に食べられるかをすべて試します．k 番目に食べられるとするなら，そこから距離 d[i + 1] 以内で，かつ自分よりあとに食べることになる小籠包の数だけ，a[i + 1] を加算します．また，k 番目より先に食べる小籠包についても，同様に考えて加算します．
さて，先程取り除いた左端の小籠包ですが，もし i + 1 番目の小籠包，あるいは左端の小籠包の汁の飛び散る範囲が 7 なら，この2つの順番も考慮する必要があります．
これは，i + 1 番目の小籠包も x 番目に食べるとしたときに，左端の小籠包とどちらを先に食べるか（これは自由に決めて良い．なぜなら他の小籠包の順番はもう決まっていて，これとは独立だから．）を試して良い方を取ります．
それ以外のときは，他の小籠包と同様に単純に x と k を比較すれば良いです．
以上で解くことが出来ました．
計算量は O(n * 7 * 6 * 7!) となり，間に合います．
ソースコード
fn next_permutation<T: Ord>(v: &mut Vec<T>) -> bool { if v.len() == 0 || v.len() == 1 { return false } let mut i: usize = v.len() - 1; let n = v.len(); loop { let ii = i; i -= 1; if v[i].cmp(&v[ii]) == Ordering::Less { let mut j = n - 1; while v[i].cmp(&v[j]) != Ordering::Less { j -= 1; } v.swap(i, j); for k in 0..(n - ii) / 2 { // reverse v.swap(ii + k, n - k - 1); } return true } if i == 0 { // i == first v.reverse(); return false } } } fn main() { let cin = stdin(); let cin = cin.lock(); let mut sc = Scanner::new(cin); let n: usize = sc.read(); let mut d: Vec<usize> = vec![0; n]; let mut a: Vec<usize> = vec![0; n]; for i in 0..n { d[i] = sc.read(); } for i in 0..n { a[i] = sc.read(); } let d = d; let a = a; let mut dp: Vec<HashMap<Vec<usize>, usize>> = vec![HashMap::new(); n]; let mut perm: Vec<usize> = (0..7).collect(); while { dp[0].insert(perm.clone(), 0); next_permutation(&mut perm) } {} for i in 0..n-1 { let mut nxt: HashMap<Vec<usize>, usize> = HashMap::new(); for (p, r) in &mut dp[i] { let mut np: Vec<usize> = vec![0; 7]; for j in 0..6 { np[j] = p[j + 1]; if p[0] > p[j + 1] { np[j] += 1; } } for _j in 0..7 { let mut rr = *r; for kk in 0..6 { if i >= kk { if np[6 - kk - 1] < np[6] && d[i - kk] >= kk + 1 { rr += a[i - kk]; } if np[6 - kk - 1] > np[6] && d[i + 1] >= kk + 1 { rr += a[i + 1]; } } } if i >= 6 && p[0] == np[6] { let t1 = if d[i - 6] == 7 { a[i - 6] } else { 0 }; let t2 = if d[i + 1] == 7 { a[i + 1] } else { 0 }; rr += max(t1, t2); } else if i >= 6 && p[0] > np[6] { rr += if d[i + 1] == 7 { a[i + 1] } else { 0 }; } else if i >= 6 && p[0] < np[6] { rr += if d[i - 6] == 7 { a[i - 6] } else { 0 }; } if nxt.contains_key(&np) { let r2: usize = *nxt.get(&np).unwrap(); nxt.insert(np.clone(), max(rr, r2)); } else { nxt.insert(np.clone(), rr); } np[6] += 1; for k in 0..6 { if np[k] == np[6] { np[k] -= 1; } } } } dp[i + 1] = nxt; } println!("{}", dp[n - 1].iter().fold(0, |ans, (_, a)| max(ans, *a))); }
感想
これは普通に難しかった．遷移が少しややこしい．
AOJ 0624 Food stalls
解法
bitDP で解きます．
あるマスにいるとき，それまでに買った屋台の情報を持つのですが，右か下にしかいけないことから，保存すべき場所が少なくなります．
具体的には，右，下，右上，左下の4箇所の購入状況を保存しておけば十分です．
あとは，実際に移動した時の買い方を全部試すだけで良いです．
空きマスは0円の屋台としても答えは変わらないので，そうすると一部実装がサボれるかも．
計算量は O(16 * HW)
ソースコード
fn main() { let cin = stdin(); let cin = cin.lock(); let mut sc = Scanner::new(cin); let h: usize = sc.read(); let w: usize = sc.read(); let mut map: Vec<Vec<char>> = vec![Vec::new(); h]; for i in 0..h { let s: String = sc.read(); map[i] = s.chars().collect(); } let map = map; let mut val: Vec<Vec<i32>> = vec![vec![0; w]; h]; for i in 0..h { for j in 0..w { if map[i][j] == '.' { val[i][j] = 0; } else { val[i][j] = (map[i][j].to_digit(10)).unwrap() as i32; } } } let val = val; let mut dp: Vec<Vec<Vec<i32>>> = vec![vec![vec![INF; 1 << 4]; w]; h]; dp[0][0][0] = 0; for i in 0..h { for j in 0..w { for b in 0..(1 << 4) { if i + 1 < h { // go down let (ny, nx) = (i + 1, j); let mut pay = 0; if b & (1 << 1) == 0 { pay += val[ny][nx]; } let mut v: Vec<(i32, usize)> = Vec::new(); let nb = 0b0110 | ((b & (1 << 2)) << 1); if ny + 1 < h { v.push((val[ny + 1][nx], (1 << 1))); pay += val[ny + 1][nx]; } if nx + 1 < w { v.push((val[ny][nx + 1], (1 << 2))); pay += val[ny][nx + 1]; } if nx != 0 && b & (1 << 0) == 0 { v.push((val[ny][nx - 1], INF as usize)); pay += val[ny][nx - 1]; } if v.len() == 0 { dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay); } for (nobuy, bb) in v { let nb = if bb == INF as usize { nb } else { nb ^ bb }; dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy); } } if j + 1 < w { // go right let (ny, nx) = (i, j + 1); let mut pay = 0; if b & (1 << 2) == 0 { pay += val[ny][nx]; } let mut v: Vec<(i32, usize)> = Vec::new(); let nb = 0b0110 | ((b & (1 << 1)) >> 1); if ny + 1 < h { v.push((val[ny + 1][nx], 1 << 1)); pay += val[ny + 1][nx]; } if nx + 1 < w { v.push((val[ny][nx + 1], 1 << 2)); pay += val[ny][nx + 1]; } if ny != 0 && b & (1 << 3) == 0 { v.push((val[ny - 1][nx], INF as usize)); pay += val[ny - 1][nx]; } if v.len() == 0 { dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay); } for (nobuy, bb) in v { let nb = if bb == INF as usize { nb } else { nb ^ bb }; dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy); } } } } } println!("{}", dp[h - 1][w - 1].iter().min().unwrap()); }
感想
実装に若干失敗しています．右に移動する時と左に移動するときで共通処理が割りとあるので，コード量的にはもっと減らせるはずです．
が，変にまとめて混乱するよりは愚直に書いてみるかということでそうなりました．
