ARC121の感想
NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
AB(107:09+1WA)
順位：1120 / 3534
パフォーマンス：1301
久しぶりのARCでした。いつものABCと違ってA問題から難しいので１問も解けなかったらどうしようかとドキドキしていました。結果としては2完でした。B問題でWAが出たときは心が折れそうになりましたが最後まで諦めずに考えることができたのは良かったのではないでしょうか。よく頑張ったと思います。
感想いきます
A問題
チェビシェフの最大値を求めます。この問題の解法を見つけるまではとても速かったです。5分ほどでしょうか。以下の通りにやれば解けそうだなということに気づきました。
候補となるのはソートした端っこのもの、xとyで同じものを取ってくる可能性もあるので各3個ずつぐらい持ってきて、全探索する。
ですね。各要素をpair<int,int>に詰め込んでソートしたのですが、同じものを取ってきてしまう可能性がありますので、一旦setに詰め込んで重複を消しました。
ただ、これでやっても答えが合いません。
問題文を見返してみると、どうやらx,yともに同じものがあるみたいです。
ということで、それらを区別するために
tuple<int,int,int>
で
x, y, 番号
を管理しました。これで上記の操作を行えば答えが求まります。
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
int n;
cin >> n;
vector<tuple<int,int,int>> xy,yx;
rep(i, n)
{
int x, y; cin >> x >> y;
xy.emplace_back(x, y, i);
}
sort(xy.begin(), xy.end());
set<tuple<int,int,int>> s;
rep(i, 3)
{
s.insert(xy[i]);
s.insert(xy[xy.size() - i - 1]);
}
sort(xy.begin(), xy.end(), [](tuple<int,int,int>& a, tuple<int,int,int>& b)
{return get<1>(a) < get<1>(b);});
rep(i, 3)
{
s.insert(xy[i]);
s.insert(xy[xy.size() - i - 1]);
}
vector<tuple<int,int,int>> t;
for (auto it = s.begin(); it != s.end(); ++it)
{
t.emplace_back(*it);
}
vector<int> ans;
rep(i, t.size())rep(j, t.size())
{
if (i < j) continue;
int x1, y1,x2,y2;
tie(x1, y1,ignore) = t[i];
tie(x2, y2,ignore) = t[j];
int now = max(abs(x1-x2),abs(y1-y2));
ans.emplace_back(now);
}
sort(ans.rbegin(), ans.rend());
cout << ans[1] << endl;
return 0;
}
B問題
様々な色の犬を2匹ずつ犬小屋に入れていきます。
この問題は20分ぐらいまったく解法が浮かびませんでした。
ペアを組んだら不満がなくなるから、値の大きな奴をペアにすればよい。
ペアを作っていくから典型でもやった区間DPかな
でも、隣り合う必要はないから違う
とかいろいろ考えてました。
結局、ペアを作るということは各色ごとに余る犬は高々1匹です。ただ、3色すべて1匹余ることはありません。１匹余る色は2色までです。
ですので、余らない色をR、余る色をB,Gとすると、
BG
BR+GR
でペアを作ったときの不満の最小値が答えとなります。
このときに、BR＋GRで同じRを参照することはできないので、まず、GからRとペアを作って、そのR以外でBとペアを作る。そののち、今度はBとRを先にペアを作って、その後Gとしました。
ただ、コンテスト後に知ったのですがこの必要はないみたいです。同じRを参照するときにはBとGのペアが不満の最小値になるみたいですね。
これを1色の時、2色の時、３色で奇数が２偶数が１の時と愚直に書きました。本当に愚直に書きましたので、バグがあったらいやだなと思いました。
とりあえず書けましたのでひとまず提出。WAでした。
ソースコードが長くなっているため、デバックするのが本当に嫌でした。心が折れそうになるも、頑張ってデバックをしました。結局は、now２とするところをnow1にしていただけでした。コピペって恐ろしいですね。
これを直して提出。無事AC。ホッとしました。
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main()
{
int n;
cin >> n;
vector<ll> r, g, b;
rep(i, n*2)
{
ll a;
char c;
cin >> a >> c;
if (c == 'R') r.emplace_back(a);
if (c == 'G') g.emplace_back(a);
if (c == 'B') b.emplace_back(a);
}
int nr = r.size();
int ng = g.size();
int nb = b.size();
if (nr % 2 == 0 && nb % 2 == 0 && ng % 2 == 0)
{
cout << 0 << endl;
return 0;
}
sort(r.begin(), r.end());
sort(g.begin(), g.end());
sort(b.begin(), b.end());
if (nr == 0 || ng == 0 || nb == 0)
{
if (ng == 0)
{
swap(r, g);
swap(nr, ng);
}
if (nb == 0)
{
swap(r, b);
swap(nr, nb);
}
ll ans = 1e18;
int idx1 = 0;
int idx2 = 0;
while (1)
{
ans = min(ans, abs(g[idx1] - b[idx2]));
if (idx1 == ng - 1 && idx2 == nb - 1)break;
else if (idx1 == ng - 1) ++idx2;
else if (idx2 == nb - 1) ++idx1;
else if (g[idx1] < b[idx2]) ++idx1;
else ++idx2;
}
cout << ans << endl;
return 0;
}
//rは絶対に偶数
if (ng % 2 == 0) swap(r, g),swap(nr,ng);
if (nb % 2 == 0) swap(r, b),swap(nr,nb);
ll ans = 1e18;
int idx1 = 0;
int idx2 = 0;
//bとgでペアを作る場合
while (1)
{
ans = min(ans,abs(g[idx1] - b[idx2]));
if (idx1 == ng - 1 && idx2 == nb - 1)break;
else if (idx1 == ng - 1) ++idx2;
else if (idx2 == nb - 1) ++idx1;
else if (g[idx1] < b[idx2]) ++idx1;
else ++idx2;
}
//aとb,aとgでペアを作る場合
idx1 = 0;
idx2 = 0;
ll now1 = 1e18;
int NG = -1;
while (1)
{
if (now1 > abs(g[idx1] - r[idx2]))
{
now1 = abs(g[idx1] - r[idx2]);
NG = idx2;
}
if (idx1 == ng - 1 && idx2 == nr - 1)break;
else if (idx1 == ng - 1) ++idx2;
else if (idx2 == nr - 1) ++idx1;
else if (g[idx1] < r[idx2]) ++idx1;
else ++idx2;
}
idx1 = 0;
idx2 = 0;
ll now2 = 1e18;
while (1)
{
if (now2 > abs(b[idx1] - r[idx2]) && idx2 != NG)
{
now2 = abs(b[idx1] - r[idx2]);
}
if (idx1 == nb - 1 && idx2 == nr - 1)break;
else if (idx1 == nb - 1) ++idx2;
else if (idx2 == nr - 1) ++idx1;
else if (b[idx1] < r[idx2]) ++idx1;
else ++idx2;
}
ans = min(ans, now1 + now2);
//aとb,aとgでペアを作る場合b->g
idx1 = 0;
idx2 = 0;
now1 = 1e18;
NG = -1;
while (1)
{
if (now1 > abs(b[idx1] - r[idx2]))
{
now1 = abs(b[idx1] - r[idx2]);
NG = idx2;
}
if (idx1 == nb - 1 && idx2 == nr - 1)break;
else if (idx1 == nb - 1) ++idx2;
else if (idx2 == nr - 1) ++idx1;
else if (b[idx1] < r[idx2]) ++idx1;
else ++idx2;
}
idx1 = 0;
idx2 = 0;
now2 = 1e18;
while (1)
{
if (now2 > abs(g[idx1] - r[idx2]) && idx2 != NG)
{
now2 = abs(g[idx1] - r[idx2]);
}
if (idx1 == ng - 1 && idx2 == nr - 1)break;
else if (idx1 == ng - 1) ++idx2;
else if (idx2 == nr - 1) ++idx1;
else if (g[idx1] < r[idx2]) ++idx1;
else ++idx2;
}
ans = min(ans, now1+ now2);
cout << ans << endl;
return 0;
}
あとがき
こんなに長いコード書くのは良くないですね。本当にデバッグが大変でした。ある程度の機能を関数にまとめておかないと、1つ変更したときに変更点が多くなってしまいます。反省です。
また、全体的に実装がのんびりでした。A問題も解法はすぐに浮かんだのに、tupleの要素取得やソートの引数指定など、何も見ずに書けませんでした。10分ぐらいでしょうか、調べる時間がありました。
この辺は量をこなすしかないのでしょうね。プログラミング”言語”といわれるぐらいですから、言語なのでしょう。コツコツ毎日やらねばです。
色々書きましたが、総括としては
久しぶりのARCはドキドキしたけど楽しかった
という感じですね。いつもは日曜日の夜なのでなかなか重い腰が上がりませんが、土曜日なら気兼ねなく参加できます。次回もやる気が起きましたら参加しますので、私のやる気に期待していてください。
この記事が気に入ったらサポートをしてみませんか？