ABC 354
Table of Contents
https://atcoder.jp/contests/abc354
A. Exponential Plant
https://atcoder.jp/contests/abc354/tasks/abc354_a
B. AtCoder Janken 2
https://atcoder.jp/contests/abc354/tasks/abc354_b
C. AtCoder Magics
https://atcoder.jp/contests/abc354/tasks/abc354_c
D. AtCoder Wallpaper
https://atcoder.jp/contests/abc354/tasks/abc354_d
2026/1/17 自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll A, B, C, D;
cin >> A >> B >> C >> D;
vvll areas = {
{2, 1, 0, 1},
{1, 2, 1, 0},
};
{
ll r = ((A % 4) + 4) % 4;
ll c = ((B % 2) + 2) % 2;
vvll tmp(2, vll(4));
rep(i, 2) {
rep(j, 4) {
tmp[i][j] = areas[(i + c) % 2][(j + r) % 4];
}
}
swap(areas, tmp);
}
vvll cnt(2, vll(4));
{
ll c = (C - A) / 4;
ll r = (D - B) / 2;
rep(i, 2) rep(j, 4) {
cnt[i][j] += c * r;
}
rep(i, (D - B) % 2) {
rep(j, 4) {
cnt[i][j] += c;
}
}
}
{
ll c = (C - A) % 4;
ll r = (D - B) / 2;
rep(i, 2) rep(j, c) {
cnt[i][j] += r;
}
rep(i, (D - B) % 2) {
rep(j, c) {
cnt[i][j] += 1;
}
}
}
ll ans = 0;
rep(i, 2) rep(j, 4) {
ans += cnt[i][j] * areas[i][j];
}
cout << ans << endl;
}
E. Remove Pairs
https://atcoder.jp/contests/abc354/tasks/abc354_e
自力 AC.
残りのカードの状態を $S_i$ とし、$S_i$ の状態からペアとなるカードの取り除き方が $m$ 通りあるとき、 $S_i$ からカードを除いた遷移先の状態を $S_{j_1}, \cdots, S_{j_m}$ とする。
$f(S_i)$ をカードの状態が $S_i$ で手番が来たときに勝てるか否かを表すとき
\begin{align*} f(S_i) = \begin{cases} \text{true if } f(S_{j_k}) \text{のうち } f(S_{j_k}) = \text{false} \text{ がある} \\ \text{false otherwise} \end{cases} \end{align*}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N), B(N);
rep(i, N) cin >> A[i] >> B[i];
vector<bool> fixed(1 << N), win(1 << N);
// 使われたカードの状態が state のときに手番が来たときに勝てるか
auto dfs = [&](auto dfs, int state = 0) -> bool {
if (fixed[state]) return win[state];
vector<bool> ret;
// 表
rep(i, N) rep2(j, i + 1, N) {
if (!(state >> i & 1) && !(state >> j & 1) && A[i] == A[j]) {
bool x = dfs(dfs, state | (1 << i) | (1 << j));
ret.push_back(x);
}
}
// 裏
rep(i, N) rep2(j, i + 1, N) {
if (!(state >> i & 1) && !(state >> j & 1) && B[i] == B[j]) {
bool x = dfs(dfs, state | (1 << i) | (1 << j));
ret.push_back(x);
}
}
fixed[state] = true;
for (bool x : ret) {
if (!x) return win[state] = true;
}
return win[state] = false;
};
string ans = "Aoki";
if (dfs(dfs)) ans = "Takahashi";
cout << ans << endl;
}
F. Useless for LIS
https://atcoder.jp/contests/abc354/tasks/abc354_f
2026/2/21 解説 AC
$A_i$ を末尾としたときの最長増加部分列の長さを $t_i$、$A_i$ を先頭としたときの最長増加部分列の長さを $h_i$ とする。 $t_i + h_i - 1$ が $A_i$ を含めたときの最長増加部分列の長さである。 これが全体の最長増加部分列の長さと等しいとき、$A_i$ を含めることができる。
$A_i$ を先頭とするときの最長増加部分列の長さは、$A$ を逆順にして $-A_i$ で LIS を計算すればいい
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
vll last(N), head(N);
vll lislast(N, INF), lishead(N, INF);
rep(i, N) {
{
auto it = lower_bound(all(lislast), A[i]);
*it = A[i];
last[i] = it - lislast.begin() + 1;
}
{
ll a = A[N - i - 1];
auto it = lower_bound(all(lishead), -a);
*it = -a;
head[N - i - 1] = it - lishead.begin() + 1;
}
}
ll maxlen = lower_bound(all(lislast), INF) - lislast.begin();
vll ans;
rep(i, N) {
if (last[i] + head[i] - 1 == maxlen) ans.push_back(i + 1);
}
cout << ans.size() << endl;
print(ans);
};
int t;
cin >> t;
rep(i, t) cal();
}
重複するロジックを省略したバージョン
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
vll tail(N), head(N);
vll lis;
rep(_, 2) {
lis.resize(N, INF);
rep(i, N) {
auto it = lower_bound(all(lis), A[i]);
*it = A[i];
tail[i] = it - lis.begin() + 1;
}
swap(tail, head);
reverse(all(A));
rep(i, N) A[i] *= -1;
}
reverse(all(head));
ll len = lower_bound(all(lis), INF) - lis.begin();
vint ans;
rep(i, N) {
if (tail[i] + head[i] - 1 == len) ans.pb(i + 1);
}
cout << ans.size() << endl;
print(ans);
};
int t;
cin >> t;
rep(i, t) cal();
}