名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

CODE FESTIVAL 2015 予選Aに参加しました

AtCoder C++ Python 競技プログラミング

むー，思っていたより非常に参加者が多かった．450位前後です．恥ずかしいので，ユーザーネームも変えて参加しておきました．まる．提出したリンクでも貼っておくので，気になる人はユーザーネーム見といて…．
C問題3WAやらかして，原因がわかってなかった．ソートしろってそれ一番言われてる．




A問題

2014 → 2015 にしてくださいって．タイピングゲーム，

print(input().replace("2014", "2015"))

B問題

問題
B: とても長い数列 - CODE FESTIVAL 2015 予選A | AtCoder

回答
Submission #509318 - CODE FESTIVAL 2015 予選A | AtCoder

{} → {A1}→{A1, A2, A1}→{A1, A2, A1, A3, A1, A2, A1} みたいなものを作るので，その集合の和を求めてください，って問題です．
dpでdp[i] = dp[i-1] * 2 + Ai みたいな計算するのも有りみたいですけど…．ただ，よく見ると，出現頻度がわかるんですよね．

めんどくさいのでツイートペタって方法で行きます（ごめんなさい）

N＝3のとき，A1が4回，A2が2回，A3が1回出現したので，N=mのとき，Aiは(2^(m-i-1))回出現じゃないかなって予測した

って感じになるので，これを足し合わせる感じで回答．

n = int(input())
l = list(map(int, input().split()))
res = 0
for i in range(n):
    res += l[i] * (2 ** (n-i-1))
print(res)

C問題

問題
C: 8月31日 - CODE FESTIVAL 2015 予選A | AtCoder


回答
・C++
Submission #511775 - CODE FESTIVAL 2015 予選A | AtCoder

・Python3
Submission #513856 - CODE FESTIVAL 2015 予選A | AtCoder


書き写すとどれくらい時間短縮できるかリストを作っておき，それをソートして，順に適応させていく．
ちなみにソートしないで，その場で毎回リスト内のmaxとなる要素のインデックスを持ってきて計算すると，TLEする（3WA）
んー，，，，求める方法自体は素早く考えられたのに，なんでこれを回答した時点で1時間経過しているのか．

ちなみにこの辺りをツイッターで言ってた時は，ソートせずに考えていた時です．



以下，C++初心者の汚いコード．

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);
 
  int n, t;
  cin >> n >> t;
 
  int A[n];
  int B[n];
  vector< vector<int> > D(n);
  int sa=0, sb=0;
 
  REP(i, n) {
      int a, b;
      cin >> a >> b;
      A[i]=a, B[i]=b;
      sa+=a, sb+=b;
 
      vector<int> delem(2);
      int d = a-b;
      delem[0] = d, delem[1] = i;
      D[i] = delem;
  }
 
  if(sa <= t) {
      cout << "0" << endl;
      return 0;
  } else if(sb > t) {
      cout << "-1" << endl;
      return 0;
  }
 
  sort(D.begin(), D.end());
  int res = 0;
  int l = D.size() - 1;
  while(sa > t) {
      vector<int> t = D.at(l);
      int idx = t[1];
      A[idx] = B[idx];
      sa -= t[0];
      res++; l--;
  }
 
  cout << res << endl;
  return 0;
}

Pythonの回答はリンク先を見てください… 本質的にはアルゴリズム変わらないので．




D問題？ わかりませんでした．
見たことがあるタイプなんだけど，このタイプの問題に対する対抗策を持っていないのが問題でした．
復習します．



最後にもう一回．