ABC181の感想
AtCoder Beginner Contest181に参加しました。
問題はこちらから。
結果はこんな感じでした。
2600 / 6634 で パフォーマンスは 812でした。今回は初めてD問題まで解けたのですが、なんか消化不良でした。問題自体はそこまで難しくはないと思ったのですが、問題の条件をプログラムに起こすことに時間がかかりました。この辺は演習量というか経験が足りてないな、という感じですかね。
感想を書いていきます。
a 問題は服の色を当てる問題です。おそらくですが、登場人物は白の服を1着、黒の服を1着の計2着を着まわしているのでしょう。今日は白い服を着ています。n 日後は何色ですか?っていう問題です。
偶数日後は白、奇数日後は黒を出力します。
b 問題は黒板に書かれた数字を足す問題です。1回の操作で、a から bまでの数をすべて書きます。n 回操作をしたときに、黒板に書かれた数の和をはいくつでしょうという問題です。
数列の和の公式を使いました。公差が 1なのでSn=n*(n+1)/2です。これを、n = a, bで求めて引きます。植木算になるのでa を追加しときます。これを n 回です。
c 問題は3点が直線上にあるかの問題です。はじめは三角不等式がイコールになればいいじゃんと考えましたが、長さを出すときにルートを取るので浮動小数点誤差が生じます。なので諦めました。
結局、1,2点の傾き=2,3点の傾きで解きました。普通にやると割り算になっちゃうので、上手く変形しました。
d 問題は 8 の倍数が作れるかを求める問題です。1~9までの数字が s 個与えられるので、上手く組み合わせて 8の倍数を作ります。作れるかどうかを判定します。
1000は8の倍数なので、判定は下3桁を確認すればよいです。また、200も8の倍数なので、100の位の偶奇で2つに分かれます。あとは、20個ほどの条件(奇数なら04, 12, 20,..)を全部 if文に書きました。今までで最も酷いコードを書いてしまったので、それを残しておきます。解説記事では美しいコードにしておきます。
e 問題はn人の生徒がいて2人1組を作ります。そして、ペアの身長の差の和を求めます。この和が最小となるペアを作る問題です。ただし、生徒は奇数人なので、一人余ります。その一人は身長が可変な先生とペアを組みます。
本問題は解けなかったのですが、思考過程を書いていきます。
身長をソートして、その前後の人と差を取れば、なんか小さくなりそうです。ここで、どこかに先生を入れると先生の後ろの人はペアが変わります。変わったときに、その変化量を監視すれば、答えがでそうだなーって考えてました。
cとdにかなり時間を割かれてしまったため、e問題を全然考えられなかったことが悔やまれます。e問題を解くためには、難しい問題を勉強しつつも、簡単な問題を速く解く力を鍛える必要があるなと感じました。簡単な問題といっても、別にそんなに簡単ではないのですが、、、
今日で競技プログラミングを初めて3か月となりますが、ようやく茶色のレートになれました。茶色は学生のなかでは優秀って感じらしいです。が、本当にそうなんですかね?まだまだ、わからないことばっかりなのですが。
ただ、想像よりも茶色になるのに苦戦しました。もっと簡単になれるものだと思ってました。3回ぐらいでぱぱっと行けるものかと、、
初めてのコンテストが8400 / 9700 位でしたので、どうやら苦戦しつつも成長はしてるみたいです。
次の目標はどうしましょう。とりあえずはパフォーマンス1200目指してお勉強を続けます。
最後に d 問題のコードを載せておきます。「このコンテストで通ればそれでいい」という必死さが表れています。お恥ずかしい。
#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 ll = long long;
using namespace std;
int main()
{
string s;
cin >> s;
vector<int> dn(10,0);
bool ok = false;
int cnt = 0;
vector<int> s12(2);
while (!s.empty() && !ok)
{
int d = s[0] - '0';
if (!(d & 1))
{
if (dn[0] >= 1)
{
if (dn[0] >= 2 || dn[4] >= 1 || dn[8] >= 1) ok = true;
}
else if (dn[1] >= 1)
{
if (dn[6] >= 1) ok = true;
}
else if (dn[2] >= 1)
{
if (dn[3] >= 1 || dn[4] >= 1 || dn[7] >= 1) ok = true;
}
else if (dn[4] >= 1)
{
if (dn[8] >= 1 || dn[6] >= 1) ok = true;
}
else if (dn[5] >= 1)
{
if (dn[6] >= 1) ok = true;
}
else if (dn[6] >= 1)
{
if (dn[9] >= 1) ok = true;
}
else if (dn[8] >= 2) ok = true;
}
else
{
if (dn[0] >= 1)
{
if (dn[2] >= 1 || dn[4] >= 1||dn[6] >= 1) ok = true;
}
else if (dn[1] >= 1)
{
if (dn[2] >= 1) ok = true;
}
else if (dn[2] >= 1)
{
if (dn[5] >= 1 || dn[8] >= 1 || dn[9] >= 1) ok = true;
}
else if (dn[3] >= 1)
{
if (dn[6] >= 1) ok = true;
}
else if (dn[4] >= 1)
{
if (dn[4] >= 2||dn[8] >= 1) ok = true;
}
else if (dn[6] >= 1)
{
if (dn[7] >= 1 || dn[8]>=1) ok = true;
}
}
++dn[d];
s.erase(0, 1);
if (cnt < 2)
{
s12[cnt] = d;
++cnt;
}
}
if (cnt <= 2)
{
int ts = s12[0] + 10 * s12[1];
if (ts % 8 == 0) ok = true;
ts = 10*s12[0] + s12[1];
if (ts % 8 == 0) ok = true;
}
if (ok) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
この記事が気に入ったらサポートをしてみませんか?