• 作成:

競技プログラミングのコンテストに初参加して, 調子に乗って初参加なのにAtCoder Regular Contest 097の方に参加したら見事爆死しました

AtCoder Regular Contest 097 - AtCoderに参加しました.

競技プログラミングのコンテスト初参加です.

BeginnerではなくRegular Contestの方に参加したら最初の問題すら解けずに無事死亡しました.

C - K-th Substringをずっとやっていました.

最初にHaskellで書きました.

import           Data.List

main :: IO ()
main = do
    s <- getLine
    k <- read <$> getLine
    let subs = sort $ nub $
            concatMap (\size -> map (\from -> take size $ drop from s) [0 .. length s - size])
            [1 .. length s]
    putStrLn $ subs !! (k - 1)

無事TLEしたのでとりあえずC++に切り替えることにしました.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  string s;
  int k;
  cin >> s;
  cin >> k;
  vector<string> substrs;
  for (size_t size = 1; size <= s.size(); ++size) {
    for (size_t from = 0; from <= s.size() - size; ++from) {
      substrs.push_back(s.substr(from, size));
    }
  }
  sort(substrs.begin(), substrs.end());
  auto u = unique(substrs.begin(), substrs.end());
  substrs.erase(u, substrs.end());
  cout << substrs.at(k - 1) << endl;
  return 0;
}

私の提出はこちら

もちろんこのような愚直なコードではTLEしてしまい, 残りの時間でずっと悩むことになります. というかTLEの他にREも起きてるんですけどこれはスタックオーバーフローとかなんですかね?

1<=K<=51 <= K <= 5であることから特定の文字列は切り捨てても良いんだろうなあということはわかりましたが, 具体的な切り捨てて良い条件を詰められませんでした.

コンテスト中に調べて気がついたことは, kmyk/online-judge-tools: Tools for online judge services. Downloading sample cases, Testing/Submitting your code, and various utilities. は超便利ということです. ページに載ってないテストケースもtestディレクトリ以下に自分で書き込めば実行してくれるし, 実行時間も取れます.

順位は768, 得点は200点でした.

順位

次回からはおとなしくBeginner Contestの方に参加しようと思います.

競技プログラミング強い人ってすごい, 改めてそう思いました.