AtCoder

ABC278 A問題(Shift)を解く

AtCoder_ABC278_A

AtCoder が提供しているABC(AtCoder Beginner Contest)278 のA問題をC++とPythonで解いてみました。ABC278は、2022年11月19日21:00に実施されました。

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

A問題 Shift(Difficulty : 17)

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

ABC278 A問題 Shift

数列を配列で表現して操作をする問題です。AtCoder Problems による Difficulty は、17 でした。ABC A問題として、標準的な問題です。

解答案

問題を解く方針を書きだします。

  • N と K、数列を読み込む。
  • K 回、以下を行う。
    • 数列の2項目以降をひとつ前の項にコピーする(先頭を取り除く)。
    • 数列の最後の項を0にする。
  • 最終的な数列を出力する。

C++ プログラム例(ABC278A)

配列は、問題と一致するように 1 から添え字を付けました。そのため、配列は、n + 1 個確保しました(8行目)。数列は、空白で区切るため、各項の後に空白か改行を出力しています(21行目)。

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

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	for (int i = 1; i <= k; ++i) {
		for (int j = 1; j < n; ++j) {
			a[j] = a[j + 1];
		}
		a[n] = 0;
	}

	for (int i = 1; i <= n; ++i) {
		cout << a[i] << " \n"[i == n];
	}

	return 0;
}

まず、問題で説明している操作を忠実にシミュレートしましたが、最終的な結果は以下の数列となります。

  • 読み込んだ、A1、A2、…、AN に対して、操作後の数列は以下となる。
    • 先頭から、AK+1、AK+2、…、AN になる。
    • 残りの K 個は、0 になる。

次のプログラムは、配列の添え字を0からにしています。上で述べていませんが、$N \leqq K$ となる場合は、すべて 0 になります。これは数列の項数より多く削除するためです。この場合を分けて出力しています。

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

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	if (k < n) {
		for (int i = k; i < n; ++i) {
			cout << a[i] << " ";
		}
		for (int i = 0; i < k; ++i) {
			cout << 0 << " \n"[i == k - 1];
		}
	} else {
		for (int i = 0; i < n; ++i) {
			cout << 0 << " \n"[i == n - 1];
		}
	}

	return 0;
}

どちらも AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC278A)

Python 版としては、C++ 版の後者をベースにしました。リストに対する以下の操作を使っているため、すっきり書けています。

  • a[k:] によって、k 番目以降のリストを抜き出せる(スライス)。
  • [0] * k によって、0 を k 個繰り返すリストを生成する。
"""AtCoder Beginner Contest 278 A"""
n, k = map(int, input().split())
a = list(map(int, input().split()))
if k < n:
    print(*(a[k:] + ([0] * k)))
else:
    print(*([0] * n))

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

最後に

ABC269から解説を書き始めました。今回で10回となりました。コンテスト本番は、C++ で解いています。Python 版は、C++ で解いたものを参考にコンテスト後にコーディングして、記事にしています。

ABC278 について、引き続き、D問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA