AtCoder が提供しているABC（AtCoder Beginner Contest）379 C問題をC++とPythonで解いてみました。ABC379は、2024年11月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sowing Stones（Difficulty : 951）
問題の詳細は、リンク先をご覧ください。
前のマスから石を処理していきます。AtCoder Problems による Difficulty は 951 でした。
解答案
入力例1について確認します。
| マス | 1 | 2 | 3 | 4 | 5 |
| 石の個数 | 3 | 0 | 0 | 2 | 0 |
すべてのマスに石を配置しようとすると、マス1の石は3個から1個になります。減った石はマス2とマス3に移動します。マス4の石は2個から1個になります。減った石はマス5に移動します。
操作の回数は、マス1からマス2に石が2個、マス2からマス3に石が1個、マス4からマス5に石が1個の合計で4回の操作が必要となります。
次に入力例2について確認します。
| マス | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 石の個数 | 4 | 0 | 0 | 2 | 0 | 0 | 0 | 4 | 0 | 0 |
マス1にある石を可能な限り移動します。マス1からマス2に3個、マス2からマス3に2個、マス3からマス4に1個移動します。この結果、マスと石の個数は以下となります。
| マス | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 石の個数 | 1 | 1 | 1 | 3 | 0 | 0 | 0 | 4 | 0 | 0 |
次にマス4から石を動かそうとしますが、次に石があるマスは8となっており、マス7からマス4まで4個の石が必要ですが、マス4には3個しか石がなく、どのように石を移動してもすべてのマスに石を置くことができません。この場合、不可能となります。
手順をまとめます。
- X[i] が昇順にソートされていると仮定します。
- X[1] が 1 でなければ、その時点で不可能となります。
- X[2]-X[1] より A[1] が少なければ、不可能となります。
- X[1] から X[2] に可能な限り石を動かします。
- 操作回数は、初項 A[1]-1、最後の項がA[1]-(X[2]-X[1]) の等差数列の和となります。
- A[2] には、A[1]-(X[2]-X[1]) 個の石を加えます。
- 上記操作を繰り返します。
- X[M] から マスNに対して同様な処理をします。
C++ プログラム例（ABC379C）
上記の考察をプログラムとして実装します。入力例からは、勘違いしやすいですが、x[i] はソートされていないため、ソートして格納します（18ー26行目）。また、問題文と上記の考察は、要素を1からカウントしていますが、プログラムでは0からカウントします。
- X[m-1] を n-1 にしています。これにより最後の処理が繰り返しでできるようになります（27ー31行目）。
- x[0] が 0 でなければ不可能となります（33－36行目）。
- X[i] を先頭から処理します（38－48行目）。
- 初項 $a$、最後の項 $b$、項数 $n$ の等差数列の和は、$n (a + b) / 2$ となります（46行目）。
- a[m-1] が 1 でなければ結果的に不可能となります（50ー53行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n, m;
cin >> n >> m;
vector<int> x(m);
for (int i = 0; i < m; ++i) {
cin >> x[i];
}
vector<ll> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<pair<int, ll>> p(m);
for (int i = 0; i < m; ++i) {
p[i] = make_pair(x[i] - 1, a[i]);
}
sort(p.begin(), p.end());
for (int i = 0; i < m; ++i) {
x[i] = p[i].first;
a[i] = p[i].second;
}
if (x[m - 1] != n - 1) {
++m;
x.push_back(n - 1);
a.push_back(0);
}
if (x[0] != 0) {
cout << -1 << endl;
return 0;
}
ll result = 0;
ll diff;
for (int i = 1; i < m; ++i) {
diff = x[i] - x[i - 1];
if (a[i - 1] < diff) {
cout << -1 << endl;
return 0;
}
result += diff * ((a[i - 1] - 1) + (a[i - 1] - diff)) / 2;
a[i] += a[i - 1] - diff;
}
if (a[m - 1] != 1) {
cout << -1 << endl;
return 0;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC379C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 379 C"""
import sys
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = list(map(int, input().split()))
p = [(0, 0)] * m
for i in range(m):
p[i] = (x[i] - 1, a[i])
p.sort()
for i in range(m):
x[i] = p[i][0]
a[i] = p[i][1]
if x[m - 1] != n - 1:
m += 1
x.append(n - 1)
a.append(0)
if x[0] != 0:
print(-1)
sys.exit()
result = 0
for i in range(1, m):
diff = x[i] - x[i - 1]
if a[i - 1] < diff:
print(-1)
sys.exit()
result += diff * (a[i - 1] - 1 + a[i - 1] - diff) // 2
a[i] += a[i - 1] - diff
if a[m - 1] != 1:
print(-1)
sys.exit()
print(result)こちらも「AC」と判定されました。
最後に
問題の状況をよく読み、分析することで解くことができました。
引き続き ABC の問題を紹介していきます。
