競プロっておいしいの?(仮)

DDCC 2017 予選 参加記録

DDCC 2017予選に出たよ

DISCO presents ディスカバリーチャンネル コードコンテスト2017

という名前のコンテストですね。で、私はなかなかない好成績を(大嘘)出しました。

10分三完は頑張った!!!

231位ですね。

では解法の話をね

 

A問題:DDCC型文字列

substr(0,2)==substr(2,2)?Yes:No;

1WA!!!!

問題をよく読みましょう

substr(0,2)==substr(2,2)&&S[1]!=S[2]ですね

B問題:鉛筆

鉛筆 1 ダースは 12 本、 1 グロス144 本、 1 グレートグロス1728 本です。

1728*A+144*B+C*12+D

終わり。

C問題:収納

二分探索とか言う強い人もいますが...私は断然ソート+貪欲です。

見てみましょうか。

問題概要

  1. a+b+1<=Cなら2本それ以外なら1本入る棒がある
  2. 箱少なくしよう!!!
  3. (詳しくは読んで...)

私の解法

  1. sortします。
  2. 後ろから要素を見ます
  3. L[i(N-1~0まで回す)]+L[prev]+1<=Cなら
    F[prev]というもうすでにしまったことを表すフラグをtrueにします。
    でprev++します。
  4. F[i]はtrueに。
  5. ans++
  6. このループを繰り返します。終了条件はi=0まで行くか、F[i]==trueになるかのどっちかです。
  7. 詳しくはソースをご覧くださいな
  8. Nafmo's submission

感想。

いや、貪欲が秒で実装できてよかった。

あと本選辞退する人が100人ほど現れないかだけ期待しています。

それでは。今回はここらで