ABC315 B問題（The Middle Day）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）315 のB問題をC++とPythonで解いてみました。ABC315は、2023年8月19日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 The Middle Day（Difficulty : 45）

問題はリンク先をご覧ください。

ABC315 B問題 The Middle Day

真ん中の日を求めて、どの月に入るか確認します。AtCoder Problems による Difficulty は 45 でした。

解答案

C++ プログラム例（ABC315B）

問題で与えられるD_iを読みながら、1年の日数sumを求めます（12行目）。sumは問題の制約から奇数になるため、真ん中の日 half は、sum/2+1 で求めることができます（15行目）。

1年の最初からカウントした日をdayとして、月の数だけ以下のループを行います。

• day+d[i] が half 以下なら、i+1が月となり、half-dayが日となります。
• 上記を満たさない場合は、dayにd[i]を加えて、次の月について調べます。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int m;
	cin >> m;
	vector<int> d(m);
	int sum = 0;
	for (int i = 0; i < m; ++i) {
		cin >> d[i];
		sum += d[i];
	}

	int half = sum / 2 + 1;
	int day = 0;
	for (int i = 0; i < m; ++i) {
		if (day + d[i] >= half) {
			cout << i + 1 << " " << half - day << endl;
			break;
		}
		day += d[i];
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC315B）

C++のプログラムをほぼそのまま移植しました。一年の日数を求めるために組込み関数 sum を使った程度の差分しかありません。

"""AtCoder Beginner Contest 315 B"""
m = int(input())
d = list(map(int, input().split()))

half = sum(d) // 2 + 1
day = 0
for i in range(m):
    if day + d[i] >= half:
        print(i + 1, half - day)
        break
    day += d[i]

こちらも「AC」と判定されました。

最後に

問題文によって、入力の変数名が異なっています。この問題の場合、要素数がMで、各月の日数がD_iでした。変数名は基本的に問題文に与えられている記号を小文字にしたものを使っています（慣用で大文字はマクロ定数を表すことが多いため）。

この問題を解いているときに、要素数をN、配列をA_iと勘違いして、少し時間を失いました。変数名をそのまま使うか、読み替えて毎回同じ変数を使うかは、問題にも依存するかもしれません。問題の変数名が多い場合は、問題と合っていたほうが混乱が少ないですし、変数名が少ない場合は、固定したほうが速く解くことができます。

しばらく試行錯誤してみようと思います。ブログでの紹介プログラムは、変数名を可能な限り、問題文と合わせておきます。

引き続き ABC の問題を紹介していきます。