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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

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問題? わかりませんでした.
見たことがあるタイプなんだけど,このタイプの問題に対する対抗策を持っていないのが問題でした.
復習します.



最後にもう一回.