読者です 読者をやめる 読者になる 読者になる

spark573’s blog

こゃーん

ABC033 参加記

URL↓

http://abc033.contest.atcoder.jp/

Atcoderによる解説↓

http://www.slideshare.net/chokudai/abc033

結果 300点186位



【A問題】
4桁の整数が与えられるのでそれがゾロ目か判定する問題。
どう考えても1111の倍数か判定するだけでOKだったけど、0000はINT型変数に入らないと思い込んでstringで読み込んで判定してた。おバカ。
ソースコード

#include <iostream>
#include <string>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  cout << (s[0] == s[1] && s[1]== s[2]  && s[2]==s[3] ? "SAME" : "DIFFERENT") << endl;
}

【B問題】
人口が総人口の過半数以上である町の名前を出力する問題。
「『過半数以上』って半分は含むのか・・?」って戸惑ってしまったがサンプルが優しさを見せてくれたので事なきを得た。
「人口」の英訳(population)が「po」まで出てきた結果ひどい変数名になった。
ソースコード

#include <iostream>
#include <string>
using namespace std;
 
int main(){
  string name[1010];
  int po[1010];
  int N;
  int sum_po=0;
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> name[i] >> po[i];
    sum_po += po[i];
  }
  for(int i=0;i<N;i++){
    if(po[i]*2 > sum_po){
      cout << name[i] << endl;
      return 0;
    }
  }
 
  cout << "atcoder" << endl;
}

【C問題】
数式の中の整数を0に置換するという操作で、数式の値を0にするための置換の最小回数を求める問題。
整数は1桁限定だったりカッコが無かったりで優しさを感じた。さすがABC。
プラスの数を数えるとともに、プラスで区切られた部分数式(つまり掛け算部分)が0かどうかで答えを調整、という流れで解いた。
が、WA。
その後ちょっと考えたら、部分数式を愚直に計算したら余裕でオーバーフローすることに気づいた。
一昔はこういうバグに永遠に気づかないままコンテスト終了とかザラだったので早く気付けて嬉しかった。
とりあえず式中の整数が1以上ならそれを1に置換する感じでオーバーフローを防いだ。
ソースコード

#include <iostream>
#include <string>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  int t=0;
  int ans=0;
  int f=0;
  for(int i=0;i<s.size();i++){
    if(i%2 == 0){
      if(f==0){
        if(s[i]!='0') t+=1;
      }
      else{
        if(s[i]=='0') t*=0;
      }
    }
    else{
      if(s[i] == '+'){
        f=0;
        if(t>0){
          ans++;
        }
        t=0;
      }
      else{
        f=1;
      }
    }
  }
  if(t>0) ans++;
  cout << ans << endl;
}

【D問題】
N個の点があり、それらの点3つで構成される三角形を全通り考えた時、鋭角三角形、直角三角形、鈍角三角形の数を数える問題。
D問題に突入した時点で1時間40分くらいあったが解けなかった。弱い。
二つの点を直径の端とする円について、内部にある点は鈍角、円上の点は直角、それ以外は鋭角として、うまくまとめて数えられないかずっと考えていた。
残り1時間くらいになって「分かった!!!」ってなって実装するも永遠にデバッグする羽目になった。
(*)lower_boundがずっと「〜〜以上が現れる場所」を示すと勘違いしてた(*がついたらその場所のを示しますよね・・・)
残り20分くらいになってようやくそのミスに気付く。しかし出る答えは全然違う。
いろいろなケースで考えるうちに嘘解法であることに気付く。絶望。(残り5分)

残り1時間になったくらいで順位表見たら全完が10人くらいしかいなくて、最終的に全完が19人だったので、Beginnerとは何かを考えさせられた。

【感想】
最近は土日バイト休んでるのでAtcoderのコンテストに参加できるけど、いずれ再開したら参加出来なくなるな〜と思って折角なので参加記を書いた。
精進したい。