AtCoder Beginner Contest 100 D - Patisserie ABC 誤答コード
問題
誤答コード
#include <bits/stdc++.h>
#define chmax(x, y) x = max(x, y);
using namespace std;
using P = pair<int, int>;
bool c1 (vector<long long> &a, vector<long long> &b) {
return a[0] > b[0];
}
bool c2 (vector<long long> &a, vector<long long> &b) {
return a[0] < b[0];
}
bool c3 (vector<long long> &a, vector<long long> &b) {
return a[1] > b[0];
}
bool c4 (vector<long long> &a, vector<long long> &b) {
return a[1] < b[1];
}
bool c5 (vector<long long> &a, vector<long long> &b) {
return a[2] > b[2];
}
bool c6 (vector<long long> &a, vector<long long> &b) {
return a[2] < b[2];
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<long long>> in(n, vector<long long>(3)), v1, v2, v3, v4, v5, v6;
for(int i=0;i<n;i++) for(int j=0;j<3;j++) cin >> in[i][j];
v1.assign(in.begin(), in.end());
v2.assign(in.begin(), in.end());
v3.assign(in.begin(), in.end());
v4.assign(in.begin(), in.end());
v5.assign(in.begin(), in.end());
v6.assign(in.begin(), in.end());
sort(v1.begin(), v1.end(), c1);
sort(v2.begin(), v2.end(), c2);
sort(v3.begin(), v3.end(), c3);
sort(v4.begin(), v4.end(), c4);
sort(v5.begin(), v5.end(), c5);
sort(v6.begin(), v6.end(), c6);
vector<vector<vector<long long>> *> vec(6);
vec[0] = &v1;
vec[1] = &v2;
vec[2] = &v3;
vec[3] = &v4;
vec[4] = &v5;
vec[5] = &v6;
vector<vector<long long>> ans(6, vector<long long>(3));
for(int i=0;i<m;i++) {
for(int j=0;j<6;j++) {
for(int k=0;k<3;k++) {
ans[j][k] += (*vec[j])[i][k];
}
}
}
long long result = -1;
for(int i=0;i<6;i++) {
chmax(result, abs(ans[i][0]) + abs(ans[i][1]) + abs(ans[i][2]));
}
cout << result << endl;
return 0;
}提出結果
どっかでオーバーフローしているか、範囲外アクセスしているか。
ローカルで動かしてみて結果が正しいが、ジャッジにはRE(Runtime Error)と判断された時
皆さんも一度は経験があるのではないか。ローカルでは動くけど、提出してみてエラーになる問題。
今回対象にしている問題はこちら。
コードを提出した結果とそのスクショはこちら。
WAではなくREになっているのは、コードとして間違っている部分があることが多い。それを今回は発見していく。
提出コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, c;
cin >> n >> k >> c;
string s;
cin >> s;
vector<int> can;
vector<int> ans;
for(int i=0;i<n;i++) {
if(s[i] == 'o') can.emplace_back(i);
}
vector<int> days(can.size());
for(int i=n-1;i>=0;i--) {
auto it = upper_bound(can.begin(), can.end(), can[i]+c);
if(it == can.end()) days[i] = 1;
else {
int j = distance(can.begin(), it);
days[i] = days[j] + 1;
}
}
if(days.front() > k) {
cout << endl;
return 0;
}
int lim = -1;;
for(int i=0;i<days.size();i++) {
if(i == 0) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else if(i == days.size()-1) {
if(can[i-1] <= lim || days[i] != days[i-1]) {
ans.emplace_back(can[i]+1);
}
}
else if(can[i] <= lim) continue;
else if(can[i-1] <= lim) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else {
if(days[i] != days[i-1] && days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
}
if(!ans.size()) cout << endl;
else for(auto& el : ans) cout << el << endl;
return 0;
}#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, c;
cin >> n >> k >> c;
string s;
cin >> s;
vector<int> can;
vector<int> ans;
for(int i=0;i<n;i++) {
if(s[i] == 'o') can.emplace_back(i);
}
vector<int> days(can.size());
for(int i=n-1;i>=0;i--) {
auto it = upper_bound(can.begin(), can.end(), can[i]+c);
if(it == can.end()) days[i] = 1;
else {
int j = distance(can.begin(), it);
days[i] = days[j] + 1;
}
}
if(days.front() > k) {
cout << endl;
return 0;
}
int lim = -1;;
for(int i=0;i<days.size();i++) {
if(i == 0) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else if(i == days.size()-1) {
if(can[i-1] <= lim || days[i] != days[i-1]) {
ans.emplace_back(can[i]+1);
}
}
else if(can[i] <= lim) continue;
else if(can[i-1] <= lim) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else {
if(days[i] != days[i-1] && days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
}
if(!ans.size()) cout << endl;
else for(auto& el : ans) cout << el << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, c;
cin >> n >> k >> c;
string s;
cin >> s;
vector<int> can;
vector<int> ans;
for(int i=0;i<n;i++) {
if(s[i] == 'o') can.emplace_back(i);
}
vector<int> days(can.size());
for(int i=n-1;i>=0;i--) {
auto it = upper_bound(can.begin(), can.end(), can[i]+c);
if(it == can.end()) days[i] = 1;
else {
int j = distance(can.begin(), it);
days[i] = days[j] + 1;
}
}
if(days.front() > k) {
cout << endl;
return 0;
}
int lim = -1;;
for(int i=0;i<days.size();i++) {
if(i == 0) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else if(i == days.size()-1) {
if(can[i-1] <= lim || days[i] != days[i-1]) {
ans.emplace_back(can[i]+1);
}
}
else if(can[i] <= lim) continue;
else if(can[i-1] <= lim) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else {
if(days[i] != days[i-1] && days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
}
if(!ans.size()) cout << endl;
else for(auto& el : ans) cout << el << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, c;
cin >> n >> k >> c;
string s;
cin >> s;
vector<int> can;
vector<int> ans;
for(int i=0;i<n;i++) {
if(s[i] == 'o') can.emplace_back(i);
}
vector<int> days(can.size());
for(int i=n-1;i>=0;i--) {
auto it = upper_bound(can.begin(), can.end(), can[i]+c);
if(it == can.end()) days[i] = 1;
else {
int j = distance(can.begin(), it);
days[i] = days[j] + 1;
}
}
if(days.front() > k) {
cout << endl;
return 0;
}
int lim = -1;;
for(int i=0;i<days.size();i++) {
if(i == 0) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else if(i == days.size()-1) {
if(can[i-1] <= lim || days[i] != days[i-1]) {
ans.emplace_back(can[i]+1);
}
}
else if(can[i] <= lim) continue;
else if(can[i-1] <= lim) {
if(days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
else {
if(days[i] != days[i-1] && days[i] != days[i+1]) {
ans.emplace_back(can[i]+1);
lim = can[i] + c;
}
}
}
if(!ans.size()) cout << endl;
else for(auto& el : ans) cout << el << endl;
return 0;
}
疑うべきは配列の範囲外アクセスですよね！
となって発見できるのが、vector<int> daysの下のiの部分。nはもとも文字列sの長さであってdaysの長さではない。ここをdays.size()に直す。
そして提出した結果がこちら。
これで自分の解き方が間違っていることが大体わかった。あとはどこが間違っていたのかを考える段階。
これのどこが間違っていたのかに関しては別のノートでまとめようか。
では。
AtCoder Grand Contest 034 B - ABC やらかしコード
問題はこちら。問題の紹介、解説は全くしない。
AGCなのにABCという謎な問題。
以前この問題を解いて最後の一つのWAが取れず、ずっと考えていて今回一からコードを書き直すことにした。その結果依然としてWAが取れず悩んでいた。そのWAが取れたのでその経過をここに記す。
オーバーフローの可能性を考えていなかったのがまず失策。最大の場合を考える。つまりABCABCABC・・・・・ABCABの合計200000文字の文字列が入力として与えられた場合である。その場合の答えは66666 * (66666 + 1) / 2である。
この計算結果は2222211111
一方でINTの最大値は2147483647
である。
ギリギリオーバーフロー。アルゴリズム的には問題なく、答えの型をintからlong long に変更。結果AC。
一応書いたコードも載せておく。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
int main() {
string s;
cin >> s;
int n = s.size();
ll res = 0;
int start = -1;
vector<string> ans;
for(int i=0;i<n;i++) {
if(s[i] == 'A') {
if(start == -1) start = i;
else continue;
}
else if(s[i] == 'B') {
if(start == -1) continue;
else if(i == n-1) {
ans.emplace_back(s.substr(start, i-start));
start = -1;
}
else if(s[i+1] == 'C') i++;
else {
ans.emplace_back(s.substr(start, i-start));
start = -1;
}
}
else if(s[i] == 'C') {
if(start == -1) continue;
else {
ans.emplace_back(s.substr(start, i-start));
start = -1;
}
}
}
if(start != -1) {
ans.emplace_back(s.substr(start, n-start));
start = -1;
}
for(int i=0;i<ans.size();i++) {
string ss = ans[i];
int bcNum = 0;
for(auto it=ss.rbegin();it!=ss.rend();it++) {
if(*it == 'C') {
bcNum++;
it++;
}
else if(*it == 'A') res += bcNum;
}
}
cout << res << endl;
return 0;
}感想
また親の仇が増えた。オーバーフローお前もだ。
自分の書いたコードが正直ゴミにしか見えない件について。
競技プログラミングで書いたコードは往々にして後から読むことを考えていない。それはそのコンテストでしか書かないコードであるし、そしてデバッグするとしても100行もないコードなのでデバッグするのも容易だろうと勝手に思っている。そういう理由で僕は可読性やらそんなことを競技プログラミングの問題を解く際には全く考えていない。
だがふと今日自分が書いた競技プログラミング用のコードを見返してみた。そのコードはほとんど想定通りの動作をするのだが、一つのテストケースだけに通らないようなコードだ。「どこが間違っているのか」「どんなテストケースに引っかかっているのか」を検証するのにいい勉強になると思ったのだ。
結論として、自分が何を思ってこのコードを書いたのか全くわからなかった。というか後から読む人を殺すかの如く可読性の低いコードがそこにはあった。
if文は5つくらい重なっているし、さらにはその中の条件文には&&で繋いだものがあるし、とにかく酷いものである。コードリーディングをしていて体力が削られることこの上ない。
まだデバッグをするタイミングがそのコードを書いた五分後とかならこのコードもある程度理解できただろう。しかし、今は大体そのコードを書いてから1ヶ月近くがたっている。問題の設定を覚えていたとしても自分が何を思ってそのコードを書いたかなんて覚えているはずがないだろう。
そうしてデバッグ作業に疲れた僕は今こうしてその反省ブログを書いているわけだ。何と悲しいことで。
そんなことはどうでも良くて将来の自分のために言っておくことがある。
競技プログラミング用のコードだからと言って、可読性の低い即席コードを書くなということだ。
コンテストの時とかならまだ別である。その時は時間制限があるし、何よりも優先すべきは問題に正解することだ。
しかし、それ以外の場面で同じようなコードをずっと書いていると「あとでどこで間違っていたのか」が本当にわからなくなる。全部一から書き直して予想通りに動いたとしても、前回書いたコードのどこが間違っていたのがはわからない。正解はわかるが間違いが間違っている理由が理解できないまま先に進むということだ。
間違いは往々にして繰り返す。その時にいつも「何で自分の解放は間違っていたんだろうか」と考えて時間を無駄にすることになる。そのような時間の無駄をなくすためにも、そしてデバッグのスピードを上げるためにも、可読性の高いコードを書くことは必要なことだと思う。
競技プログラミングもそれ以外のプログラミングと同じようにデバッグが非常に大切なので可読性の高いコードを書いた方が自分のためになるよということが言いたかった。
以上。
(デバッグ予定のコードは全て葬り去り、一から書き直すことを決心しました。)
AtCoder Beginner Contest 142 E - Get Everythingを解いた感想
実装にだいぶ時間がかかった。けどできたのでよし。実行時間800msecとかなりアルゴリズム的には良くないコードを書いてしまった。けどそれしか解法が思いつかんかったから仕方ない。
問題はこちらです。
宝箱が最大12個与えられる。そしてその宝箱を開ける鍵が最大1000個与えられる。鍵について使うコストと開けられる宝箱の番号が与えられる。最小で幾らのコストで宝箱を全て開けることができるかという問題。
解法
DPするんだろうなと思いつつ、結果DP。開ける宝箱は高々12個しかないので全探索できる(2^12通り）。そして左から何番目までの鍵を使えるかで1000通り。合計5000000回計算すれば終わる。
詳しい内容はコードを見て。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int m;
cin >> m;
vector<int> cost(m);
bitset<12> initial("000000000000");
vector<bitset<12>> key(m, initial);
for(int i=0;i<m;i++) {
int a, b;
cin >> a >> b;
for(int j=0;j<b;j++) {
int c;
cin >> c;
c--;
key[i].set(c);
}
cost[i] = a;
}
const int lim = pow(2, n);
vector<vector<int>> dp(lim, vector<int>(m+1));
for(int i=0;i<lim;i++) {
for(int j=0;j<m+1;j++) {
if(i == 0) dp[i][j] = 0;
else if(j == 0) dp[i][j] = -1;
else {
bitset<12> bit(i);
bitset<12> amp = (bit & key[j-1]);
if(amp.none()) {
dp[i][j] = dp[i][j-1];
continue;
}
int idx = 0;
for(int k=0;k<12;k++) {
if(bit.test(k) && !key[j-1].test(k)) {
idx += pow(2, k);
}
}
if(dp[idx][j-1] == -1) {
dp[i][j] = -1;
continue;
}
int tmp = dp[i][j-1];
if(tmp == -1) tmp = INT_MAX;
dp[i][j] = min(cost[j-1] + dp[idx][j-1], tmp);
}
}
}
cout << dp[lim-1][m] << endl;
return 0;
}今日は体調があまり良くない。
こんにちは。
最近不眠症でなかなか夜寝付けず辛い日々を送っていますが、何とか頑張っている今日この頃です。皆さんも不眠症には気をつけてくださいね。夜はスマートフォンとか触ってたら睡眠の質が本当に落ちますから（自戒）。
昨日も今日も競技プログラミング。今日解いた問題はまだないので、昨日解いた問題を紹介します。
この問題はおそらくABCのF問題の中で最も簡単な問題です。しっかり考えれば分かると思うので皆さんも解いてみてはいかがでしょうか。木の構築、探索がわかっていれば解ける問題だと思います。
昨日は2問しか解けなかったので今日はもう少し解きましょう。今日解こうと思っている問題はこちら。
E のLeagueはTLEが一つだけ残ってしまっているのでそれを解消します。
では。明日これらの問題の解いた感想書きますね。
直感的にはすぐに分かるがちゃんと説明できない問題
この問題について。
まずある一点から最も遠い頂点を探す（50回クエリを投げる）。
そしてその最も遠い頂点から最も遠い頂点を探す（50回クエリを投げる）。
これで木の直径、つまり頂点間の距離の中で最大のものが取得できる。
直感的には当たり前だけど説明がなかなかできない。
