【AtCoder】ABC 453 C - Sneaking Glances

2026-04-15

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/灰Diff AtCoder/NoviSteps/3Q 競技プログラミング AtCoder/全探索/bit全探索 AtCoder/小数を整数に変換して考える

C - Sneaking Glances

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 338 / NoviSteps: 3Q / 配点: 300 点

問題概要

数直線上の座標 $0.5$ に高橋君がいる。

高橋君はこれから $N$ 回の移動を行い、 $i$ 回目の移動では、「正の方向」「負の方向」のいずれかを選び、その方向に $L_i$ 進む。

高橋君は座標 $0$ を最大で何回通り過ぎることが出来るか求めよ。

制約

$1 \le N \le 20$
$1 \le L_i \le 10^9$
入力はすべて整数

考察

まず、 $N$ の制約が非常に小さいことに注目しよう。

毎回の行動毎に高橋君は2通りの行動を選択できるので、全ての行動パターンは $2^N$ 通りである。このパターン数は最大でも $2^{20} \approx 10^6$ であるため、bit全探索によって全ての行動パターンを試すことができそうである。

行動パターンは $0$ から $2^N-1$ までの $N$ ビットの整数で表され、 $i$ ビット目が $1$ であれば $i$ 回目の移動は正の方向、 $0$ であれば負の方向に移動することを意味するものとする。

あとはforループ内でシミュレーションを行い、座標 $0$ を通り過ぎる回数を数えればよいのだが、実装上のポイントをいくつか挙げておく。

初期位置の小数を整数に変換する

高橋君の初期値が $0.5$ であるため、そのままシミュレーションを行うと処理が煩雑になる。

ここで、全ての $L_i$ は整数であることを利用し、座標軸を2倍して考えることにする。つまり、初期位置を $1$ としてシミュレーションを行い、移動距離も全て2倍すればよい。

座標 $0$ を通り過ぎる回数の数え方

座標 $0$ を通り過ぎるということは、移動の前後で座標の符号が異なることを意味する。

これは、移動前後の座標の積を取ることで判定できるが、そのまま積を取ると、座標の値が非常に大きくなってしまう可能性があるので、以下のような符号を表す関数を定義すると良いだろう。

\mathrm{sgn}(x) = \begin{cases} 1 & (x > 0) \\ 0 & (x = 0) \\ -1 & (x < 0) \end{cases}

その上で、 $\mathrm{sgn}(\text{移動前の座標}) \times \mathrm{sgn}(\text{移動後の座標}) < 0$ であれば、座標 $0$ を通り過ぎたと判定できる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
7. 
8.template <typename T>
9.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
10. 
11.// ======================================== //
12. 
13.int main()
14.{
15.    int N;
16.    cin >> N;
17.    vector<ll> L(N);
18.    rep(i, 0, N) cin >> L[i], L[i] *= 2;
19. 
20.    auto sgn = [&](ll x) -> int {
21.        if (x > 0)
22.            return 1;
23.        else if (x == 0)
24.            return 0;
25.        else
26.            return -1;
27.    };
28. 
29.    int ans = 0;
30. 
31.    rep(bit, 0, (1 << N)) {
32.        int cnt = 0;
33.        ll pos = 1;
34.        int prev_sgn = sgn(pos);
35. 
36.        rep(i, 0, N) {
37.            if (bit & (1 << i)) {
38.                pos += L[i];
39.            } else {
40.                pos -= L[i];
41.            }
42.            
43.            if (sgn(pos) * prev_sgn < 0) {
44.                cnt++;
45.                prev_sgn = sgn(pos);
46.            }
47.        }
48. 
49.        chmax(ans, cnt);
50.    }
51. 
52.    cout << ans << endl;
53. 
54.    return 0;
55.}