こんにちは、えあーです。
昨日のABC159お疲れさまでした。
私がやられた事案を紹介します。
問題
ABC159のD問題での事案です。
まず、問題はこちら。
D – Banned K
とりあえず雑にやるとO(n^2)でTLEなのは明らかなので、
別の方法を検討します。幸い数分で浮かびました。
なのでそれに従って実装します。
1回目提出コード
まずは私が1回目に提出したコードを載せます。
そのままなのでAtCoderのページからでも見られるかと。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define all(v) (v).begin(), (v).end()
int main() {
int n;
cin >> n;
vector<int> na(n);
vector<int> v(n+1);
rep(i,n){
cin >> na[i];
v[na[i]]++;
}
vector<int64_t> nor(n+1);
vector<int64_t> abn(n+1);
rep(i, n+1){
if(v[i] > 1){
nor[i] = (v[i] * (v[i]-1))/2;
abn[i] = ((v[i]-1) * (v[i]-2))/2;
}
else{
nor[i] = 0;
abn[i] = 0;
}
}
int64_t alln = accumulate(all(nor), 0);
rep(i, n){
cout << alln-nor[na[i]]+abn[na[i]] << endl;
}
}
競プロだからコード汚いとか変数名雑いとか許してくれ～
ということで、このコードを提出しました。
この記事の本題ではないのでコード解説は下の方でやります。
結果はWAでした。
サンプルケースは全部通しているし、理論は完璧だと思っていたのでかなり焦りました。
ACしたコード
そして20分後、ACしたコードが下記。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define all(v) (v).begin(), (v).end()
int main() {
int n;
cin >> n;
vector<int64_t> na(n);
vector<int64_t> v(n+1);
rep(i,n){
cin >> na[i];
v[na[i]]++;
}
vector<int64_t> nor(n+1);
vector<int64_t> abn(n+1);
rep(i, n+1){
if(v[i] > 1){
nor[i] = (v[i] * (v[i]-1))/2;
abn[i] = ((v[i]-1) * (v[i]-2))/2;
}
else{
nor[i] = 0;
abn[i] = 0;
}
}
int64_t alln = accumulate(all(nor), 0LL);
rep(i, n){
cout << alln-nor[na[i]]+abn[na[i]] << endl;
}
}
どこが違うの？
って感じですが、
- 4～5行目 intをint64_tに
- 28行目 0を0LLに
たったこれだけです。
前者は完全に私のミス（v[i] * (v[i]-1)がオーバーフローする可能性がありますね）です。
後者は知りませんでした。（それもミスと言えばミスなんですけど）
std::accumulateの第3引数は初期値ということなので、
とりあえず0突っ込んどきゃOKでしょみたいに思っていましたが、
ここにintの0を突っ込むとオーバーフローします。
ということでint64_tの和を求めるときはちゃんと0LLで宣言するようにしましょう。
私はこれで30分（リアルタイム20分＋WA2回）持っていかれました。悲しい。
コード解説
一応考え方とコードの解説を。
茶色コーダーくらいに参考にしてもらえると嬉しい。
（読んでみて思ったけどクソわかりにくい。おまけコーナーだし許して、すまん）
思考の流れとともに。
オーダーとか細かいところまで合ってるかはわからんです。
・1個取り除いたやつで条件通り計算するとO(N)かな？
→N回やる必要があるのでそのままやるとO(N^2)でTLE
・1個取り除くだけだから全部まとめて計算しておいて、
不要なやつを外した値が出せたら早そう。
（事前に準備しておけば、出力はO(1)にできそう）
・2個選ぶ組み合わせなので同じやつがいくつあるかわかれば計算できる、
ついでにそれを除去した値も準備しておけそう
・i番目がいくつか、整数の値ごとにボールがいくつあるのかを記録すればいけそう
（上記コードのnaとvがそうです）
面倒だしvはn+1個準備しておこうってのも思いました
（0番目要素が無意味だけど、後から1個ずつずらすとミスしやすいので）
・同じボールを2個選ぶ組み合わせも変わらないし、
取り除かれた場合と取り除かれていない場合と両方計算して保持しておこう
（上記コードのnorとabn。norが取り除かれない場合、abnが取り除かれた場合）
・あとはガリガリ書くだけ
強いて言えばnorとabnって直接使わないので、
先にallnとnor-abnを覚えたvectorを使っても良かったのかも。
コメント