ABC181の感想

AtCoder Beginner Contest181に参加しました。

問題はこちらから。

Tasks - AtCoder Beginner Contest 181

結果はこんな感じでした。

2600 / 6634 で パフォーマンスは 812でした。今回は初めてD問題まで解けたのですが、なんか消化不良でした。問題自体はそこまで難しくはないと思ったのですが、問題の条件をプログラムに起こすことに時間がかかりました。この辺は演習量というか経験が足りてないな、という感じですかね。

感想を書いていきます。

a 問題は服の色を当てる問題です。おそらくですが、登場人物は白の服を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 個与えられるので、上手く組み合わせて ８の倍数を作ります。作れるかどうかを判定します。

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;

}