AtCoder2回目の挑戦！
今回も解けたのはB問題までで、C問題は解説を見ながらトライしました。
B問題もかなり難しかったように感じました…かなり沼ってしまったので、次回までにBまではすらすら解けるように練習しておきたいです。
問題のリンク
A - Sigma Cubes
問題
1からNまでの数字 i について以下の計算をします。
- (-1)^iを求める
- i^3を求める
- 各項について1と2の積を求め、その和を出力する
解答例
(-1)^iについては必ず1か-1になり、iが偶数か奇数かによって判別できます。
i^3は3回かけるだけです。
for文でiを増やしていって、sumにその和を入れていきましょう。
for文が0から始まるので(i+1)としています。
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
int sum = 0;
for(int i=0; i<N; i++){
int a = 1;
//偶数か奇数かを判定
if((i+1)%2){
a = -1;
}
//3乗を計算し、足し合わせる
sum += a * (i+1) * (i+1) * (i+1);
}
cout << sum;
}
B - Find Permutation 2
問題
1～Nまでの数を1回ずつ使って数列を作り、出力します。
ただし、「-1 -1 2 -1」のように与えられ、-1以外の場所の数字は固定されています。
また、存在しない場合は「No」と出力します。
解答例
順列全探索を使用します。
1~Nの数字を並び替えてできる全パターンを探索すれば答えにたどりくけますし、今回の条件なら全探索してもタイムアウトしません。
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
//P:取得した数列を入れる配列
vector<int> P;
//Q:全探索用に1～Nを入れる配列
vector<int> Q;
bool d = false;
for(int i=0; i<N; i++){
int num; cin >> num;
P.push_back(num);
}
for(int i=0; i<N; i++){
Q.push_back(i+1);
}
//順列全探索ではdo-while文を使うらしい
do {
bool b = true;
for (int i = 0; i < Q.size(); i++) {
//一致していない場合、bをfalseにする
if(P[i] != -1 && P[i] != Q[i]){
b = false;
}
}
//すべての数字を確かめてもbがtrue＝これが回答
if(b) {
cout << "Yes" << endl;
bool first = true;
for(int x : Q){
if(!first) cout << " ";
else first = false;
cout << x;
}
return 0;
}
}
//順列全探索ができる呪文(笑)
while (next_permutation(Q.begin(), Q.end()));
//回答が見つからなかった場合
cout << "No" << endl;
}
おまけ
私が本番で提出した回答です。
順列全探索を知らなかったため、気合で作成しました。
参考にしないでください…
一応仕組みを解説します。
Qに-1以外の数字を入れていきます。
Noを出力しないといけないのは、同じ数字が入ってた時なので、まずはそれを検索。
あとは-1の部分に、使える数字numを順番に数字を入れていきます。
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<int> v;
//P：元の数列
vector<int> P;
//Q：Pの数字の部分だけ
vector<int> Q;
bool d = false;
for(int i=0; i<N; i++){
//よく見たら同じ変数名numを使ってて分かりづら過ぎますね。
//スコープ的に動作はしますが…
int num; cin >> num;
P.push_back(num);
if(num != -1){
Q.push_back(num);
d = true;
}
}
//比較しやすいようにQを並び替え
sort(Q.begin(), Q.end());
//Qが空だとエラーが起きるので除外
if(d){
int i=0;
//隣り合ってる数が同じでないか確認
while(i < (Q.size()-1)){
if(Q[i] == Q[i+1]){
cout << "No" << endl;
return 0;
}
i++;
}
}
//Pのうち、与えられた数字は使えないため除外。
//まだ使える数字のみをnumに入れる
vector<int> num;
for(int i=0; i<N; i++){
bool a = true;
for(int x : Q){
if(x == i+1){
a = false;
break;
}
}
if(a){
num.push_back(i+1);
}
}
//Pが-1の部分にnumの数字を入れる
vector<int> ans;
for(int i=0; i<N; i++){
if(P[i] == -1){
ans.push_back(num.back());
num.pop_back();
}else{
ans.push_back(P[i]);
}
}
//答えを出力
cout << "Yes" << endl;
bool first = true;
for(int x : ans){
if(!first){
cout << " ";
}else{
first = false;
}
cout << x;
}
}
C - Rotate and Sum Query
問題
与えられた数列について、以下の処理を行います。
- クエリ1：指定回数だけ、先頭の数を末尾に移動
- クエリ2：指定された部分の和を出力
解答例
クエリ1について、キューとかが使えそうですが、キューではクエリ2が実行できません。
そのため、配列に数字を格納して、先頭の位置frontをメモしておきます。リングバッファみたいなイメージかな？
クエリ1の指定回数だけfrontの位置を後ろにずらせばOKです。
松見まで行ったらfrontを先頭に戻しましょう。
クエリ2について、単純に足すだけに見えますが、毎回足すとタイムアウトします。
そこで、あらかじめ先頭からの和を、配列sumに記録しておきます。
例えば3番目から5番目までの和は、5番目までの和から2番目までの和を引けばいいですね。
ただし、クエリ1で先頭の位置が移動するため、sumは数列の長さNの2倍くらいの長さが必要になります。
また、sumの先頭は0を入れておきましょう。理由は、frontが先頭にある時、front-1が存在しなくならないようにするためです。
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,Q;
cin >> N >> Q;
//先頭の位置をメモ
int front = 0;
//num：取得した数列
vector<int> num(N);
//sum：数列の先頭からの和。
//長さはNの2倍で、すべて0を入れて初期化。
//桁が巨大になるのでint型だとオーバーフローしてWAになります
vector<long long> sum(2*N + 1,0);
for(int i=0; i<N; i++){
cin >> num[i];
}
for(int i=1; i<N*2+1; i++){
sum[i] = sum[i-1] + num[(i-1)%N];
}
for(int i=0; i<Q; i++){
int n; cin >> n;
//クエリ1
if(n == 1){
int x; cin >> x;
//frontが末尾まで来たら先頭に戻すために、剰余 % を使う
front = (front+x) % N;
}
else{//クエリ2
int y,z; cin >> y >> z;
long long ans = sum[front + z] - sum[front + y - 1];
cout << ans << endl;
}
}
}
感想
今回も時間内にはBまでしか解けませんでしたが、Bですら1時間くらい沼ったのがダメダメでしたね…
順列全探索、全然知らなかったです…
先週はアルゴリズムの勉強を急いでC問題を数問練習してましたが、今週はB問題をしっかり固める練習をしようと思います。