Beta Round #71

Codeforces

ir5 & rng回。もふもふ。

A: Bus Game

  • 問題斜め読みした挙句。dp[x][y]とか無理だよと一瞬だけ絶望してた。
  • はい。ただのシミュレーションですね。
  • 100円を払いたい方て払う、100円を払いたい方て払う、20円払う、でいいかな。
    • sample合わない。
      • あ、先に20円払っとかないとダメだよね。
  • 合った。submit. Pretest Passed.
bool Ciel(int &a,int &b){
  ----b; a ? --a : b-=10; a ? --a : b-=10; 
  return a>=0 && b>=0;
}

bool Hanako(int &a,int &b){
  ----b; b >= 10 ? b-=10 : a--; b >= 10 ? b-=10 : a--;
  return a>=0 && b>=0;
}

int main(){
  int a,b;
  while(cin >> a >> b){
    while(true){
      if(!Ciel(a,b)){ cout << "Hanako" << endl; break; }
      if(!Hanako(a,b)){ cout << "Ciel" << endl; break; }
    }
  }
}

B: Colorful Field

  • 問題文をあんまり読まずに図で把握した。
  • 障害物の座標値から直接計算しないと間に合わないっぽい。
    • 難しそう・・・と見せかけてそうでもないな。
    • 1次元にしてvectorに放り込んでlower_bound。
  • 適当に書いたら答え出てきた。submit. Pretest Passed.
int main(){
  const string S[] = {"Carrots", "Kiwis", "Grapes"};
  int n,m,k,t;
  while(cin >> n >> m >> k >> t){
    vint v(k);
    REP(i,k){ int a,b; cin >> a >> b; a--; b--; v[i]=a*m+b; }
    sort(ALL(v));
    while(t--){
      int a,b; cin >> a >> b; a--; b--;
      int p = lower_bound(ALL(v),a*m+b) - v.begin();
      if(v[p]==a*m+b) cout << "Waste" << endl; 
      else cout << S[(a*m+b-p)%3] << endl;
    }
  }
}

C: Beaver

  • 問題の把握に時間が掛かった。
    • 主に sample 0 の "...street" のところにも str があるのを見落としてたせい。
  • で、これは・・・難しくないか？
    • KMPとかRabin-Karpとかは何か違うっぽい。
    • しゃくとりっぽく頑張る？なんだかバグりそう。
    • 求める文字列の開始位置の候補は禁止ワードの出現位置の2文字目で、終了位置の候補は出現位置の最後から2文字目で。
      • 各開始位置について定数か対数時間ぐらいで終了位置が分かればよくて。
        • 適当に書けばなんとかなるかな？バグリそうな気がする。
  • どつぼにハマってる感があるのでちょっと落ち着いてみよう。
  • 開始位置を決め打ちして終了位置を探すことを考える。
    • その位置より前に始まった禁止ワードは考えなくてよくて。
    • それ以降に始まる禁止ワードのうち、最も早く終わるものを探せばよい。
      • 各禁止ワードの開始位置をリストアップしておいて、lower_boundでいいかな。
        • あれ、さっきまで悩んでたのが嘘みたいに簡単だった。なんだこれ。
  • 実装。
    • cin が遅そうだったのでscanfで頑張る。
    • 答えでない。さんざん悩んだ挙句 strlen を忘れてるのに気づいた。ひどい。
  • 答えでてきた。submit. Pretest Passed.
  • 禁止ワードごとに独立に考えるという発送がなかなか出てこなかったのが敗因だろうか。
    • 図に頼りすぎたのが良くなかったかもしれない。
const int N = 1<<20;
char s[N];
int l;

vint matches(const string& t){
  vint res;
  REP(i,l) if(equal(ALL(t),s+i)) res.push_back(i);
  return res;
}

int main(){
  while(~scanf("%s",s)){
    l = strlen(s);
    int n; scanf("%d",&n);
    vector<string> t(n);
    REP(i,n){ char buf[16]; scanf("%s",buf); t[i]=buf; }

    vector<vint> v;
    REP(i,n) v.push_back(matches(t[i]));

    int ans = 0, pos = 0;
    REP(i,l){
      int res = l - i;
      REP(j,n){
        int p = lower_bound(ALL(v[j]),i) - v[j].begin();
        if(p < v[j].size()) ls(res,(int)(v[j][p]+t[j].size()-1-i));
      }
      if(ans < res) ans = res, pos = i;
    }

    cout << ans << ' ' << pos << endl;
  }
}

D: Password

E: Security System

  • 一応読んだけど、難しそうだしあんまり解いてる人もいないし。スルーしよう。LockしてHackだ。
  • Aで100円玉を1枚払うパターンを考えてない人が2人もいてホクホクでした

System Test

  • ABC通って2662点、41位。
    • 自分にしては結構いい順位だと思うけど、あんまりCodeForcesでたことないのでどれぐらいいい順位なのかよくわからない。
  • Aはみんなのよりコードが短くて、勝った感があります。
  • Writerお疲れ様でした。楽しかったです。