2023年最後の回で、成績最低の回。。
B問題が解けず、つられてC問題もWAの嵐。
成績は1完(泣)
A Christmas Present
割愛します。
#include<bits/stdc++.h>
using namespace std;
int main () {
int B,G;
std::cin >> B >> G;
if(B<G){
std::cout << "Glove" << std::endl;
}
else{
std::cout << "Bat" << std::endl;
}
}
B Christmas Trees
難しかった。初めてB問題が解けないという屈辱を味わった。
C++以外の言語を使ってる人にとってはなんともない問題。
C Socks2
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int N, K;
std::cin >> N >> K;
std::vector<int> A(K, 0);
for (int k = 0; k < K; k++) std::cin >> A[k];
std::sort(A.begin(), A.end());
if (K % 2 == 0) {
int ans = 0;
for (int k = 0; k < (K-1);) {
ans += A[k + 1] - A[k];
k += 2;
}
std::cout << ans << std::endl;
return 0;
}
else {
std::vector<int> Strange(K, 0);
//まず先頭（＝０番目）を無視した時の奇妙度を計算する
int tmp_strange = 0;
for (int k = 1; k < K; ) {
tmp_strange += A[k + 1] - A[k];
k += 2;
}
Strange[0] = tmp_strange;
//i番目を無視したときの奇妙度をi-1番目を無視した時の奇妙度から計算していくDPをする
for (int ignore = 1; ignore < K; ignore++) {
if (ignore % 2 == 0) {
//インデックスが偶数＝奇数番目のとき
//i-1番目を無視した時のペアはi番目とi-2番目でペアを作っているので、
//i番目とi-2番目のペアを解除し、i-1番目とi-2番目でペアを作らせる。（それ以外はそのまま）
Strange[ignore] = Strange[ignore - 1] - (A[ignore] - A[ignore-2]) + (A[ignore - 1] - A[ignore - 2]);
}
else{
//インデックスが奇数＝偶数番目のとき
//i-1番目を無視した時のペアはi番目とi+1番目でペアを作っているので、
//i番目とi+1番目のペアを解除し、i+1番目とi-1番目でペアを作らせる。（それ以外はそのまま）
Strange[ignore] = Strange[ignore - 1] - (A[ignore + 1] - A[ignore]) + (A[ignore + 1] - A[ignore - 1]);
}
}
std::cout << *min_element(Strange.begin(), Strange.end()) << std::endl;
return 0;
}
}当時はWAが取れなかったが、「i番目を無視した時の奇妙度」は「i-1番目を無視した時の奇妙度」から計算できることに気づいてDPで実装するとすんなり解ける問題。
DP使わずやるとTLEする。
D Reindeer and Sleigh
A、B、C問題で時間切れだったため、着手すらできず。
解いてみると無茶苦茶カンタンｗｗ
どの問題を解くかの選択も重要なのね。。
#include <iostream>
#include <vector>
#include <algorithm>
// [初期アイデア]
// Rを小さい順にソート
// RRを合計値にする
// 例） RR[0]＝R[0]、RR[1]＝RR[0]＋R[1]、RR[2]＝RR[1]＋R[2]
// RR[i]＜＝x＜RR[i+1]となるiをみつける （二分探索）
// i+1が答え
int main()
{
int N, Q;
std::cin >> N >> Q;
std::vector<long> R(N,0);
std::vector<long> RR(N,0);
for (int i = 0; i < N; i++) {
std::cin >> R[i];
}
std::sort(R.begin(), R.end());
for (int i = 0; i < N; i++) {
RR[i] += R[i];
if (0 < i) {
RR[i] += RR[i - 1];
}
}
long X;
for (int i = 0; i < Q; i++) {
std::cin >> X;
auto Iter = std::upper_bound(RR.begin(), RR.end(), X);
std::cout << (Iter - RR.begin()) << std::endl;
}
}
コメント