またもや３完という成績。
４完の壁は高い。。
A Long Loong
#include<bits/stdc++.h>
using namespace std;
int main () {
int N;
std::cin >> N;
std::cout << "L";
for(int i=0; i<N; i++){
std::cout << "o";
}
std::cout << "ng" << std::endl;
}
B CTZ
#include<bits/stdc++.h>
// #include <format>
using namespace std;
int main () {
int N;
std::cin >> N;
std::bitset<60> bs(N);
int ret = 0;
for(int i=0; i<60; i++){
// if(s[i] == '0')
if(bs[i] == 0)
{
ret++;
}
else{
break;
}
}
std::cout << ret << std::endl;
}
C Even Digits
#include<bits/stdc++.h>
using namespace std;
int dig[5] = {0,2,4,6,8};
int main () {
long long N;
std::cin >> N;
long long tmp = N-1;
if(tmp == 0){
std::cout << 0 << std::endl;
return 0;
}
std::stack<int> s;
while(0<tmp){
s.push(dig[int(tmp%5)]);
tmp = tmp/5;
}
while(0<s.size()){
std::cout << s.top();
s.pop();
}
std::cout << std::endl;
}
D Pyramid
#include<bits/stdc++.h>
using namespace std;
int main () {
int N;
std::cin >> N;
std::vector<long long> A(N, 0);
for(int i=0; i<N; i++){
std::cin >> A[i];
}
int k = 0;
if(N%2==0){
k = N/2;
}
else{
k = (N+1)/2;
}
std::vector<long long> tmp;
while(true){
tmp.resize(2*k-1);
long long num = 0;
for(int i=0; i<(2*k-1); i++){
if(i<k){
num++;
}
else{
num--;
}
tmp[i] = num;
}
bool is_ok = true;
for(int i=0; i<tmp.size(); i++){
if(tmp[i]<=A[i]){
}
else{
is_ok = false;
}
}
if(is_ok == true){
std::cout << k << std::endl;
return 0;
}
else{
k--;
}
}
}
案の定上記のコードでTLEを食らったので、こっちのコード作成中に時間切れ。
悔しいので解き直して再度解答をUPします。
#include <iostream>
//#include<bits/stdc++.h>
//using namespace std;
#include <vector>
int main() {
long long N;
std::cin >> N;
std::vector<long long> A(N, 0);
//A.push_back(0);
for (long long i = 0; i < N; i++) {
std::cin >> A[i];
}
//A.push_back(0);
long long right = 0;
long long ret = 0;
long long center_val = 0;
for (long long left = 0; left < N; ++left) {
long long tmp_ret = 0;
while ((right < N) && (((right+1)-left) <= A[right])) {
/* 実際に right を 1 進める */
// ex: sum += a[right];
++right;
}
/* break した状態で right は条件を満たす最大なので、何かする */
while ((right < N) && (0<(A[((((right + 1) - left) + 1) / 2)-1] - ((((right + 1) - left) - ((((right + 1) - left) + 1) / 2))))) && (A[((((right + 1) - left) + 1) / 2)-1] - ((((right + 1) - left) - ((((right + 1) - left) + 1) / 2))) <= A[right])) {
++right;
}
tmp_ret += (right - left);
/*if (0 < tmp_ret) {
long long tmp_center_val = 0;
if (tmp_ret % 2 == 0) {
tmp_center_val = std::max(A[tmp_ret / 2], A[(tmp_ret / 2) - 1]);
tmp_ret = tmp_ret / 2;
}
else {
tmp_ret = (tmp_ret + 1) / 2;
tmp_center_val = A[tmp_ret];
}
tmp_ret = std::min(tmp_ret, tmp_center_val);
}*/
ret = std::max(ret, tmp_ret);
/* left をインクリメントする準備 */
if (right == left) ++right;
//else left = right-1;
}
//std::cout << ret << std::endl;
if (ret % 2 == 0) {
ret = ret / 2;
}
else {
ret = (ret + 1) / 2;
}
std::cout << ret << std::endl;
}尺取り法で頑張ったが、公式解説放送をみて尺取り法は悪手だと判明。おとなしく方針転換して解きなおしたコードがこちら。
#include <iostream>
//#include<bits/stdc++.h>
//using namespace std;
#include <vector>
int main() {
long long N;
std::cin >> N;
N += 2; //入力された数列の先頭と末尾に０を追加するため。
std::vector<long long> A(N, 0);
for (long long i = 1; i < N-1; i++) {
std::cin >> A[i];
}
std::vector<long long> StepCountLeft(N, 0); //頂点より左に最大何段作れるかを計算してメモする
for (long long i = 1; i < N; i++) {
/*
* i番目から左に作れる段数の最大は高々[i-1]+1段。
* [i-1]+1よりも入力された数値が小さい場合はその数分しか作れない。
*/
StepCountLeft[i] = std::min(StepCountLeft[i - 1] + 1, A[i]);
}
std::vector<long long> StepCountRight(N, 0); //頂点より右に最大何段作れるかを計算してメモする
for (long long i = N - 2; 0 <= i; i--) {
/*
* i番目から右に作れる段数の最大は高々[i+1]+1段。
* [i+1]+1よりも入力された数値が小さい場合はその数分しか作れない。
*/
StepCountRight[i] = std::min(StepCountRight[i + 1] + 1, A[i]);
}
long long ret = 0;
for (int i = 0; i < N; i++) {
/*
* ある頂点から作れるピラミッドの段数は、その頂点の左側に作れる段数とその頂点の右側に作れる段数の小さいほうになる。
* すべての頂点で作れる段数を調べ、最大のものが問題の答えとなる。
*/
ret = std::max(ret, std::min(StepCountLeft[i], StepCountRight[i]));
}
std::cout << ret << std::endl;
}
コメント