naoya_t@hatenablog

いわゆるチラシノウラであります

SRM579

Div1Easy過去問を1日1問解いてみるやつ
WAだったらもう1問、にしようか

Easy ("UndoHistory", 250)

さくっと書いてサンプルケース通ったやつを投げてWA
{"absolutely", "abs", "absolute"}で引っかかるし。
バッファの続きから行ける場合にバッファを使ってしまっていた(バッファの続きから行くかundoから行くかちゃんと判断してない)。駄目じゃん。

ACコード

cout.h はvectorとかsetとかをstd::coutに投げれるようにする自作ツール。
https://gist.github.com/naoyat/5830568

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

class UndoHistory {
  set<string> undoes;
 public:
  int longest(string& line) {
    int L = sz(line);
    for (int l=L; l>0; --l) {
      string su = line.substr(0, l);
      if (found(undoes, su)) return l;
    }
    return 0;
  }

  int minPresses(vector<string> lines) {
    int N = sz(lines);
    undoes.clear();

    string buf = ""; int B = 0;
    int press = 0;
    rep(i, N){
      string line = lines[i]; int L = sz(line);

      int e0 = INT_MAX, e0c = INT_MAX;
      if (B <= L && line.substr(0, B) == buf) {
        e0 = B;
        e0c = L - B;
      }
/*
      ここに else { e0 = longest(line); e1c = 2 + (L-e1); } 相当のコードを書いてたorz
*/

      int e1 = longest(line); // [0 .. L]
      int e1c = 2 + (L - e1); // これを使った場合のタイプ数 [2 .. 2+L]

      int e;
      if (e1c < e0c) {
// BEGIN CUT HERE
        cout << "CLICK: ¥"" << line.substr(0, e1) << "¥"" << endl;
// END CUT HERE
        press += 2;
        e = e1;
      } else { // e0 != INT_MAX
// BEGIN CUT HERE
        cout << "USING CURRENT BUFFER" << endl;
// END CUT HERE
        e = e0;
      }

      for (int l=e+1; l<=L; ++l) {
        undoes.insert(line.substr(0, l));
// BEGIN CUT HERE
        cout << "TYPING: " << line[l-1] << endl;
// END CUT HERE
        ++press;
      }
// BEGIN CUT HERE
      cout << undoes << endl;
// END CUT HERE

      buf = line; B = L;

// BEGIN CUT HERE
      cout << "TYPING ENTER" << endl;
// END CUT HERE
      ++press;
    }
    return press;
  }

};