AtCoderのコンテストは初めての参加ですが、結果は、C,D解けて、E,F解けず。1回しか参加してないのでまだ灰色ですが、5回コンテストに参加するとちゃんとレーティングが算出され見合ったカラーになるようです。

C - K-th Substring

Sの部分文字列から辞書順でK番目に小さい値を探す。

部分文字列を総当りしていくと日が暮れるので制約の小さいKに着目。K文字以上は探索しなくて良いので後はささっと実装する。

int main(int argc, char *argv[]) {
  string s;
  int k;
  cin>>s>>k;
  int now=0;
  set<string> ststr;
  for (int i=0;i<30;i++){
    char c = 'a' + i;
    for (int j=0;j<s.size();j++){
      if (s[j] == c){
        for(int j2=1;j2<=5;j2++){
          if (j+j2>s.size())break;
          ststr.insert(s.substr(j, j2));
        }
      }
    }
    if (ststr.size() > k)break;
  }
  string ans=*std::next(ststr.begin(), k-1);
  cout<<ans<<endl;
  return 0;
}

本番では律儀にaから順番に探索していた。

D - Equals

交換可能なindex、値をUnionFindでつないでいく。操作回数は無制限なので、値と目的のindexが同じツリーにいるものをカウントしていく。 indexはそのままいれると値とバッティングするので200000とか足しておく。

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool connect(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool isSame(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

UnionFind uf = UnionFind(400030);

int main(int argc, char *argv[]) {
  int n,m;cin>>n>>m;
  for(int i=0;i<n;i++){
    int t;
    cin>>t;
    uf.connect(t, i + 200000);
  }
  for(int i=0;i<m;i++){
    int t1,t2;
    cin>>t1>>t2;
    uf.connect(200000 + t1 -1, 200000 + t2 -1);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(uf.isSame(i+1, 200000+i))ans++;
  }
  cout<<ans<<endl;

  return 0;
}

最初、UnionFindの確保サイズ小さすぎてRuntime Errorが起きてしまった。+5分のペナルティ。

E - Sorted and Sorted

なんか蟻本に似たようなのあったな〜と思いつつ解けずに死亡。

F - Monochrome Cat

そっ閉じした。

感想

問題自体がかなりシンプルでわかりやすく、それでいて奥が深いので練習にも最適な感じがしました。使える言語多いし、日本語の問題だし、日本語の解説もあるし、AtCoder最高じゃないかと思った。

2018-02-11

SRM 729 div1 easy MagicNumberThree - 久々の競技プログラミング

競技プログラミング

久々にTopcoderに参加しようと直近の問題を練習がてら解いてみました。まずはeasyから。ちなみにGreedというプラグインをいれてみましたがかなり使いやすくておすすめです。

さて問題は、"303049"みたいな文字列が渡されるので、3で割れる部分文字列の数を数えるというものでした。何文字目まで使ったとき、1余る、2余る、3で割れる文字列がいくつあるかを保持するという感じで、動的計画法で解きました。

class MagicNumberThree {
    public:
    int countSubsequences(string s) {
        int a[55][4];
        for (int i = 0; i < 55; i++)
          for (int j = 0; j < 4; j++) a[i][j] = 0;

        long long res = 0;
        for (int i = 0; i < s.length(); i++) {
          int si = s[i] - '0';
          if (si % 3 == 0) {
            a[i + 1][0] = a[i][0] + a[i][0] + 1;
            a[i + 1][1] = a[i][1] + a[i][1];
            a[i + 1][2] = a[i][2] + a[i][2];
          } else if (si % 3 == 1) {
            a[i + 1][0] = a[i][2] + a[i][0];
            a[i + 1][1] = a[i][0] + a[i][1] + 1;
            a[i + 1][2] = a[i][1] + a[i][2];
          } else {
            a[i + 1][0] = a[i][1] + a[i][0];
            a[i + 1][1] = a[i][2] + a[i][1];
            a[i + 1][2] = a[i][0] + a[i][2] + 1;
          }

          a[i + 1][0] %= 1000000007;
          a[i + 1][1] %= 1000000007;
          a[i + 1][2] %= 1000000007;

          res = a[i + 1][0];
          res %= 1000000007;
        }
        return res;
    }
};

2017-11-28

Ruby: splitで分割対象を残す

Ruby

こんな感じ。

普通のsplit

"090-1234-5678".split("-")
# => ["090", "1234", "5678"]

splitしたものを結果に含める

"090-1234-5678".split(/(-)/)
# => ["090", "-", "1234", "-", "5678"]

改訂2版パーフェクトRuby

作者: Rubyサポーターズ
出版社/メーカー: 技術評論社
発売日: 2017/05/17
メディア: 大型本
この商品を含むブログ (1件) を見る

2017-11-24

Ruby: 配列で重複してるものを探す

Ruby

一部の値が重複してる配列があるとする。この中から重複しているものを取り出したい。

ary = [1, 2, 3, 4, 5, 5, 6, 6, 7, 7]

こんな感じ

ary.select{ |e| ary.count(e) > 1 }.uniq
# => [5, 6, 7]

速い方法

ハッシュを作るので使うメモリは増えるが、先程の方法と違ってループアンドループしないのでこっちの方が速い。

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)
# => [5, 6, 7]

単に重複があるかどうかチェックしたい場合

(ary.count - ary.uniq.count) > 0
=> true

配列の積集合や和集合

ary = [1, 2, 3, 4, 5, 5, 6, 6, 7, 7];
ary2 = [1, 2, 3];

ary & ary2
# => [1, 2, 3]

ary | ary2
=> [1, 2, 3, 4, 5, 6, 7]

参考

https://stackoverflow.com/questions/8921999/ruby-how-to-find-and-return-a-duplicate-value-in-array

プログラミング言語 Ruby

作者: まつもとゆきひろ,David Flanagan,卜部昌平(監訳),長尾高弘
出版社/メーカー: オライリージャパン
発売日: 2009/01/26
メディア: 大型本
購入: 21人クリック: 356回
この商品を含むブログ (129件) を見る

2017-09-06

JavaScript: 行の先頭にマッチする正規表現

JavaScript

改行含む文字列の各行についてマッチさせたいとき。

mフラグをつけると各行の先頭にマッチします。 gフラグをつけると全てのマッチする文字列を探索します。

var str = "abcd1\nabcd2\nabcd3";
var regexp1 = new RegExp(`^abcd2$`);
str.match(regexp1); // null mフラグなしだと文字列全体の先頭/終端のみ

var regexp2 = new RegExp(`^abcd2$`, 'm');
str.match(regexp2); // ["abcd2"] mフラグをつけると各行にマッチする

var regexp3 = new RegExp(`^a.+$`, 'gm');
str.match(regexp3); // ["abcd", "abcd", "abcd"] mフラグとgフラグをつけると全ての行についてマッチさせます

詳説正規表現第3版

作者: Jeffrey E.F. Friedl,株式会社ロングテール,長尾高弘
出版社/メーカー: オライリージャパン
発売日: 2008/04/26
メディア: 大型本
購入: 24人クリック: 754回
この商品を含むブログ (87件) を見る

余談

rubyだと^$はデフォルトで各行にマッチするので、文字列全体にマッチさせたいときは、\A\zを使ったりしますね。

2016-11-21

Swift3でのNSBundle.mainBundle

iOS

なんか変わってた。

let url = Bundle.main.url(forResource: "test", withExtension: "txt")
print(url)
let data = try! Data(contentsOf: url!)

2016-11-21

Karabinerの代替品

Mac

みんな大好きKarabiner（旧 KeyRemap4MacBook）。macOS Sierraでは現状動かないみたいなので、代替品を探さなくてはならない。

とはいえKarabinerのライトユーザーだったので必要だったのは、以下のところだけ。

英語キーボードなので、

command（左） -> 英入力
command（右） -> かな入力
コロンとセミコロンの入れ替え

あとは、

キーリピートを速くする

代替手段

キーの入れ替え系は ⌘英かなでなんとかなった。 Karabiner-Elements とかも使えるのかも。

キーリピートに関しては、Macのキーボードの設定からでもいけるけど、ターミナルを開いて以下のコマンドを打つとさらに速く。

defaults write -g InitialKeyRepeat -int 10 # 通常だと15（225ms）まで
defaults write -g KeyRepeat -int 1 # 通常だと2（30ms）まで

宇宙船サンドボックス

ARC097の振り返り