A - Shift Editorial by kyopro_friends
解法
問題文の指示に従って実際に操作を行います。各言語で「\(A\) の先頭(または指定した位置)の要素を削除する」「\(A\) の末尾に \(0\) を挿入する」を行う方法を調べて実装しましょう。
(※例えばC言語にはそのような操作を直接行う方法はありません。諦めましょう)
実装例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
// 入力を受け取る
int n,k;
cin >> n >> k;
vector<int>a;
for(int i=0;i<n;i++)cin >> a[i];
for(int i=0;i<k;i++){
a.erase(a.begin()); //aの先頭の要素を削除
a.push_back(0); //aの末尾に0を追加
}
//出力する
for(int i=0;i<n;i++)cout << a[i] << ' ';
}
実装例(Python)
# 入力を受け取る
N,K=map(int,input().split())
A=list(map(int,input().split()))
for _ in range(K):
A.pop(0) # Aの先頭(0番目)の要素を削除
A.append(0) # Aの末尾に0を追加
# 出力する
print(*A)
注意点
この問題はこれで解くことができましたが、注意点が1つあります。一般に、配列に対して「指定した位置の要素を削除する」という処理には、配列の長さに比例した時間がかかります。今回は操作対象の配列の長さが \(N\) であることから、削除 \(1\) 回につき \(O(N)\) の時間がかかり、プログラム全体で \(O(NK)\) の時間がかかります。
C問題以降の多くの問題では、処理にかかる時間を考慮する必要があります。上で書いたコードの計算量を \(O(K)\) と誤解しないように、必要に応じて組み込み関数の計算量を確認しておきましょう。
高速な解法
サンプル2, 3から予想できるように、
- \(K\geq N\) なら \(N\) 個の \(0\) を出力
- \(K< N\) なら \(A\) の末尾 \(N-K\) 項と \(K\) 個の \(0\) を出力
として \(O(N)\) で解くことができます。
実装例(C++)
#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=0;i<n;i++)cout << 0 << ' ';
}else{
for(int i=0;i<n-k;i++)cout << a[k+i] << ' ';
for(int i=0;i<k;i++)cout << 0 << ' ';
}
}
実装例(Python)
# 入力を受け取る
N,K=map(int,input().split())
A=list(map(int,input().split()))
# 出力する
if K>=N:
print(*[0]*N)
else:
print(*(A[K:]+[0]*K))
この解法は冒頭で述べた解法に比べ効率が良いですが、どのような場合分けが必要であるかや何を出力すべきかを自分でしっかり考える必要がある点が難しいです。競技プログラミングにおいては「計算量が悪いが考察や実装が簡単」と「計算量が良いが考察や実装が難しい」の対立が起こることが多くあります。特に高難易度の問題においては、不必要な高速化のために悩んでしまうことがないよう、計算量を適切に見積もり、高速化の必要がある箇所を見極めることが大切です。
posted:
last update: