第1回 岩井星人アンソロジープログラミングコンテスト忘れてたあああああああああああ!
A問題(diff:43)
久々の150点A問題!
for文回しても行けますが、僕は自作ライブラリにBITで配列の転倒数を求めるライブラリを作っておいたので、転倒数が1かどうかで判定しました。この問題ではやっている操作が「バブルソート」そのものであり、バブルソートの交換回数 $=$ 転倒数であることから、この解法が正しいことが分かります。
計算量は数列の長さを $N$ として $O(NlogN)$ なので、$N = 5$ なら言うまでもなく間に合います。
ACコード(1ms)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct FenwickTree {//BIT
int N;
vector<ll> a;
FenwickTree(int n) {
N = n;
a.assign(N + 1, 0);
}
void add(int i, ll x) {
for(int j = i; j <= N; j += (j & -j)) {
a.at(j) += x;
}
}
ll sum(int i, int j) {
return sum_sub(j) - sum_sub(i - 1);
}
ll sum_sub(int i) {
if(i == 0) {
return 0;
}
ll s = 0;
for(int j = i; j > 0; j -= (j & -j)) {
s += a.at(j);
}
return s;
}
};
ll tento(vector<ll> a) {//転倒数を求める関数
int s = a.size();
FenwickTree tmp(s);
ll ans = 0;
for(int i = 0; i < s; i++) {
ans += i - tmp.sum_sub(a.at(i));
tmp.add(a.at(i), 1);
}
return ans;
}
//library end
int main() {
vector<ll> A(5);
for(ll &o : A) {
cin >> o;
}
if(tento(A) == 1) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
AC時間:2:22(にゃーん)
B問題(diff:147)
高校数学してて良かった、と思えた1問でした。多分してなかったら「等比数列?!初項?!公比?!」ってなって多分解けませんでした。
因みに、公式解説には誤差に注意とありますが、doubleにしたら行けます。($A_i \le 10^9$ なのでlong longとかも使わなくてokです)
(2025/01/26更新)テストケースにafter_contestが追加されたので誤差WAなりました。なので、正攻法で解き直しました。
ACコード(更新済み)(1ms)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll POW(ll a, int N) {
if(N == 0) {
return 1;
}
if(N == 1) {
return a;
}
ll ans = POW(a, N / 2) * POW(a, N / 2);
if(N % 2 == 1) {
ans *= a;
}
return ans;
}
//library end
int main() {
int N;
cin >> N;
vector<ll> A(N);
for(ll &o : A) {
cin >> o;
}
for(int i = 0; i < N - 2; i++) {
if(POW(A.at(i + 1), 2) != A.at(i + 2) * A.at(i)) {
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}
AC時間:3:54
C問題(diff:247)
最近のD問題が簡単になったみたいな問題ですね
この問題は、
- マス $(i,j) (1≤i≤H, 1≤j≤W)$ は、$a≤i≤b$ かつ $c≤j≤d$ をみたすとき、黒く塗られている。そうでないとき、白く塗られている。
という条件を満たす $a,b,c,d$ が存在するかという問題になります。逆に、これ以上黒い長方形を小さくできない、というものが条件を達成できなければ、それより大きな黒い長方形もできません。
このような限界の長方形は、「一番上にある黒の所属している行」を $h_{min}$ 、「一番下にある黒の所属している行」を $h_{max}$ 、「一番左にある黒の所属している行」を $w_{min}$ 、「一番右にある黒の所属している行」を $w_{max}$ とすると、4点 $(h_{min},w_{min}),(h_{max},w_{min}),(h_{max},w_{max}),(h_{min},w_{max}))$ による長方形だと言えます。
この長方形の中に1つでも白が確定しているマスがあれば、条件を満たさないので答えはNoです。逆に、この長方形が黒が確定しているマスと塗られていないマスだけで構成されていれば、Yesとなります。計算量は $O(HW)$ です。
ACコード(18ms)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
int H, W;
cin >> H >> W;
vector<vector<int>> xy(H, vector<int>(0));
vector<string> S(H);
for(int i = 0; i < H; i++) {
cin >> S.at(i);
for(int j = 0; j < W; j++) {
if(S.at(i).at(j) == '#') {
xy.at(i).push_back(j);
}
}
}
int h_min = -1;
for(int i = 0; i < H; i++) {
if((int)(xy.at(i).size()) > 0) {
h_min = i;
break;
}
}
int h_max = H;
for(int i = H - 1; i >= 0; i--) {
if((int)(xy.at(i).size()) > 0) {
h_max = i;
break;
}
}
int w_min = W;
for(int i = 0; i < H; i++) {
if((int)(xy.at(i).size()) > 0) {
w_min = min(w_min, xy.at(i).at(0));
}
}
int w_max = -1;
for(int i = 0; i < H; i++) {
if((int)(xy.at(i).size()) > 0) {
w_max = max(w_max, xy.at(i).at((int)(xy.at(i).size()) - 1));
}
}
for(int i = h_min; i <= h_max; i++) {
for(int j = w_min; j <= w_max; j++) {
if(S.at(i).at(j) == '.') {
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
}
AC時間:21:45
D問題(diff:1607)
青diffなんて解けるか～!
公式解説見るとベル数なるものが出てきました。もっと知識を増やしたいです。
僕が言えることではないですが一応
素材はながたかなさんのXから借りました
E問題(diff:1227)
dpという発想までは行きましたが、そこからわかりませんでした
ナップサックということだけは分かりました
感想
2回目の緑パフォを出しました!かなり速解きできたので、良かったです。
そろそろDも解けるといいなぁ(次回できればグラフ探索系かDPのD問題来てほしい)