AtCoder が提供しているABC（AtCoder Beginner Contest）334 のC問題をC++とPythonで解いてみました。ABC334は、2023年12月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Socks 2（Difficulty : 1030）
問題はリンク先をご覧ください。
Kが奇数のとき、左からの累積和と右からの累積和を組み合わせて最小値を求めます。AtCoder Problems による Difficulty は 1030 でした。
解答案
最初に K=2 となる入力例1を検討します。靴下は、
色1が1枚、色2が2枚、色3が1枚、色4が2枚
この場合、（色1、色2）、（色2、色3）、（色4、色4）としても、（色1、色3）、（色2、色2）、（色4、色4）としても奇妙さの最小値は2となります。
上記から、 Kが偶数の場合は、以下を計算すれば最小値になることが分かります。
(a[1]-a[0]) + (a[3]-a[2]) + … + (a[k]-a[k-1])
一番難しいのは、Kが奇数の場合です、この場合は途中の1枚しかない靴下を1枚無視することができます。式は、上記と同じです。
(a[1]-a[0]) + (a[3]-a[2]) + … + (a[k]-a[k-1])
※ただし、a[i] を一枚抜くことができる。
添え字が小さい方から加えた差と添え字が大きい方から（K-1) 枚分の計算をすることによって、a[i] を計算から抜くことができます。残りはプログラム例で説明します。
C++ プログラム例（ABC334C）
プログラムの補足です。
- kが偶数の場合は、結果を計算して終了します（15ー23行目）。
- kが奇数の場合
- 左からの累積和と右からの累積和を計算しておきます（25ー34行目）。
- K/2組の和を左からと右からの累積和から計算します（38行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(k);
for (int i = 0; i < k; ++i) {
cin >> a[i];
}
if (k % 2 == 0) {
int result = 0;
for (int i = 0; i < k / 2; ++i) {
result += a[2 * i + 1] - a[2 * i];
}
cout << result << endl;
return 0;
}
vector<int> s_left(k / 2 + 1);
s_left[0] = 0;
for (int i = 0; i < k / 2; ++i) {
s_left[i + 1] = s_left[i] + a[2 * i + 1] - a[2 * i];
}
vector<int> s_right(k / 2 + 1);
s_right[0] = 0;
for (int i = 0; i < k / 2; ++i) {
s_right[i + 1] = s_right[i] + a[k - 1 - (2 * i)] - a[k - 1 - (2 * i + 1)];
}
int result = INF;
for (int i = 0; i <= k / 2; ++i) {
result = min(result, s_left[i] + s_right[k / 2 - i]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC334C）
Python では途中で終了する場合に sys.exit() を呼び出します。基本的な考え方は、C++版と同じです。以下となります。
"""AtCoder Beginner Contest 334 C"""
import sys
INF = 1 << 30
n, k = map(int, input().split())
a = list(map(int, input().split()))
if k % 2 == 0:
result = 0
for i in range(k // 2):
result += a[2 * i + 1] - a[2 * i]
print(result)
sys.exit()
s_left = [0] * (k // 2 + 1)
s_left[0] = 0
for i in range(k // 2):
s_left[i + 1] = s_left[i] + a[2 * i + 1] - a[2 * i]
s_right = [0] * (k // 2 + 1)
s_right[0] = 0
for i in range(k // 2):
s_right[i + 1] = s_right[i] + a[k - 1 - (2 * i)] - a[k - 1 - (2 * i + 1)]
result = INF
for i in range(k // 2 + 1):
result = min(result, s_left[i] + s_right[k // 2 - i])
print(result)こちらも「AC」と判定されました。
最後に
今回は、A問題、D問題とE問題を解いた後でB問題を解きました。結果的にC問題は時間が足りなくなりました。速く解ことにより、解けるか解けないか境界にある問題に取り組む時間を増やしたいです。
引き続き ABC の問題を紹介していきます。
