2016-05-04

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました．（何やってんだか．）

解いた問題

Easyのみ.120点ぐらいでの提出だった．

問題概要

整数 $N$ と $K$ が与えられる．（ $1\le N\le 100, 1\le K\le 15$ ）

1 ~ 100 までの整数のうち， $K$ 個の数 $u_1, u_2, ..., u_K$ を選び，どのように $v\in \{-1,0,1\}^K$ を選んでも， $\sum_i u_i v_i$ が $N$ にならないようにする．

解法

等差数列 $a + d(i-1)$ でよさそう．

このように数列をとると，どう選んでも， $b a + c d$ （ $b,c\in \mathbb{Z}$ ）にしかならない．この形では， $\operatorname{gcd}(a,d)$ の倍数しか作れないということは一般常識．

よって， $a$ と $d$ を変化させて適当な数列を作る．

念のため， $N$ と $K$ を変化させて全通り試すと， $N=60$ ， $K=15$ でこの方法ではうまくいかない．最も長く作れて，14個（ $a=7,d=7$ とする)．よって，この時だけ1を追加すればよい．．．はずだった．

ミスしたところ

初項 $a$ ，公差 $d$ の等差数列の $a$ 以上 $e$ 以下の項の個数は， $\lfloor (e-a)/c\rfloor+1$ でえられる．

int k = (100 - a) / d ;

はい．見事に+1を忘れました．

解法では， $N=60,K=15$ がコーナーケースと言いましたが，これだと $K=14$ の場合もできないと判定してしまいます．

それだけだったらよかったのだが， $N=60,K\ge 14$ のときに，1と""2""を加えるようにしてしまった．この2つを足すと3になって， $-3 \equiv 60 \pmod{7}$ となってしまう．加えるのであれば，8（7を法として1と合同）とかにすべきだった．．．

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(c) (c).begin(),(c).end()

ll gcd(ll x, ll y){
    return y == 0 ? x:gcd(y, x % y);
}

struct WolfCardGame {
  int N;
  int K;
  vector<int> createAnswer(int _N, int _K) {
    N = _N, K = _K;
    for(int a = 1; a <= 100; ++a){
        for(int d = 1; d <= 100; ++d){
            if(N % gcd(a,d)){
                int k = (100 - a) / d; //ミス その1
                if(k >= K){
                    vector<int> ret(K);
                    for(int i = 0; i < K; ++i){
                        ret[i] = a + d * i;
                        if(ret[i] >= 100) cout << "oops" << endl;
                    }
                    return ret;
                }
            }
        }
    }
// ミス その2
    vector<int> ret(K);
    for(int i = 0; i < 13; ++i) ret[i] = 7 + 7 * i;
    ret[13] = 1;
    if(K == 15){
        ret[14] = 2;
    }
    return ret;
  }
};

// Powered by Greed 2.0-RC

実は，ミスその1については気が付いて，修正もすんでいたが，前のままでも問題ないと思って提出していなかった．出力判定関数も書いていたのに，そもそもその判定関数が間違っているという．．．

もっと落ち着いて問題を解こうな．

2016-05-01

TopCoder部のカレンダーをGoogleカレンダーで（そこそこきれいに）見る

カレンダーを公開しました．AtCoderのイベントはAtCoder社さんのカレンダーをお使いください．

githubにあげました． TopCoder部のカレンダーを開くのさえ億劫になってきている今日この頃．コンテストの予定がGoogleカレンダーに表示されるようになれば，コンテストにも出たくなるのではないかと考えた．

先駆者がいた． f:id:blue_jam:20160501101206p:plain

せっかく開始時間を明記してあるんだから，終日のイベントでなく，時間を決めうちしてほしいと思った．

サーバを持ってたら，cronでGoogleのAPIたたいてごにょごにょしたり，iCalendarの内容を再度編集したiCalendarを生成するのCGIプログラムを作ったりすれば何とかなるのかもしれないが，サーバを持ってない．

調べてみると，Google Apps Scriptでcronっぽいことができるらしい．（参考）

（JavaScriptほとんど使ったことない．．．）

最終的に，

TopCoder部のカレンダーをインポートしたカレンダーと，出力先のカレンダーを用意しておくと，
Google Apps Scriptで作ったプログラムが，TopCoder部のカレンダーを適切に編集し，出力先のカレンダーに書き込んでくれる

というようになった．GASはトリガーという，一定間隔で決まった関数を呼び出す仕組み（？）があり，それを設定しておくと自動で追記を編集してくれる．

AtCoderはGoogleカレンダーを公開してくださっているので省いた． HackerRankにもGoogleカレンダーにインポートできるカレンダーがあったけど，いろいろなものが登録されすぎてて混乱するので保留．

結果はこんな感じ

f:id:blue_jam:20160501103040p:plain

コンテスト時間をまじめにとるなら，コンテストサイトのAPIをたたいたほうがよさそうだけど，怠けてる．

Googleカレンダーを公開したら，ほかの人も幸せになれると思ったけど，公開するとメールアドレスがさらされる問題を解決できてないので非公開のままにします．

スクリプトのプロパティにsrcCalendarIdとdstCalendarIdを追加し，それぞれにTopCoder部カレンダーをインポートしたもののIDと，出力先のカレンダーのIDを書き込む必要があります．スクリプトのプロパティにignoreAtcoderを追加し，空でない文字列を入れるとAtCoderのイベントは追加されなくなります．トリガーには，calendarUpdateを追加してください．

たぶんgithubにあげる．

function calendarUpdate() {
  // プロパティからIDを読み取る
  var scriptProperties = PropertiesService.getScriptProperties();
  var srcCalendarId = scriptProperties.getProperty("srcCalendarId");
  var dstCalendarId = scriptProperties.getProperty("dstCalendarId");
  // カレンダーの取得
  srcCalendar = CalendarApp.getCalendarById(srcCalendarId);
  dstCalendar = CalendarApp.getCalendarById(dstCalendarId);
  
  ignoreAtCoder = Boolean(scriptProperties.getProperty("ignoreAtCoder"));
  
  // 全部は見えないらしいので，先1か月のを調べる．
  var now = new Date();
  var oneMonthFromNow = new Date(now.getTime() + (30 * 24 * 60 * 60 * 1000));
  var srcEvents = srcCalendar.getEvents(now, oneMonthFromNow);
  
  // 各イベントについて処理
  var re = new RegExp("[0-9][0-9]:[0-9][0-9]");
  for each(var e in srcEvents){
    var date = e.getTitle().match(re);
    var title = RegExp.rightContext.trim();
    var startTime = new Date(Date.parse(e.getStartTime().toLocaleDateString() + " " + date));
    
    // AtCoderを無視する設定で，AtCoderのイベントならchokuDie
    var atcoder = isAtCoderEvent(title);
    if (ignoreAtCoder && atcoder) continue;
    
    // 終了時刻を計算
    var duration = getDurationByTitle(title);
    var endTime = new Date(startTime.getTime() + duration * 60 * 1000);
    
    // 重複チェック
    var res = checkDuplication(title, startTime);
    if (res == null) {
      dstCalendar.createEvent(title, startTime, endTime);
    }
    else {
      res.setTime(startTime, endTime);
    }
  }
}

/*
 * タイトルからコンテストの長さを適当に取得する．当然間違う．
 */
function getDurationByTitle(title) {
  durationDictionary = {
    "SRM":90,
    "AtCoder Regular Contest": 90,
    "AtCoder Beginner Contest": 120,
    "Codeforces": 120,
    "yukicoder": 120
  };
  for (var key in durationDictionary) {
    Logger.log(title.indexOf(key));
    if(title.indexOf(key) >= 0)
      return durationDictionary[key];
  }
  return 90;
}

/*
 * 登録が重複しているか確認する
 * 重複しているなら，そのインスタンスを返す
 */
function checkDuplication(title, startTime) {
  var events = this.dstCalendar.getEventsForDay(startTime);
  for each(e in events){
    if(e.getTitle() == title)
      return e;
  }
  return null;
}

/*
 * AtCoderのイベントかどうか
 */
function isAtCoderEvent(title) {
  return title.indexOf("AtCoder") >= 0;
}

更新情報

5月3日：Googleカレンダーを公開しました．（ついでに，ブログの文体も少し変わっている．）

2015-06-30

ACM-ICPC 2015 こくないよせんさんかき

ぼくはAもんだいをとおしました．

ぼくがAをとおしたあとは，くりんぺっとさんがB,Cをとおして，
しゅんかんてきにいちいになりました．

そのあと，EやFをおもにかんがえましたが，ほうしんがまとまらず，
すわっているだけになりました．

きょすくんが「Hがやるだけにみえる」といったあと，
くりんぺっとさんが「ざあつ，だいくすとら，やるだけ」とつぶやいたあと，
じっそうしてとおしていました．
くりんぺっとさんは，かみだとおもいます．

15いでよせんはつうかしましたが，ぜんぶ，ほかのふたりのおかげです．
ぼくはずっとすわっているだけで，とってもつらいおもいをしたので，
アジアちくよせんでは，もっとチームにこうけんしたいです　まる

ごめん

2014-10-21

ACM-ICPC 2014 アジア地区予選東京大会参加記

日記

オリセンで開かれたICPCアジア地区予選に参加してきました．アジア地区予選に出場するのは個人でも学校でも初の経験でした．
結果は4完29位(大学別24位)でした．29位だったのでリクルートさんからNiku Awardをいただきましたありがとうございます．

チーム編成

僕(よわいソルバ)
たこくん(ソルバ)
マスコット(vimrc，テンプレート打ち込み，目diff，お茶くみ)

大体の流れ

開始前

前日からわかっていたことだが，周りが強豪ばっかでこわい．向かいがkatou(東工大)，斜め前がprimasta(京大)，右隣がnekonyaso(筑波)，右斜め後ろがUTouto@Kyoto(東大)とかどんないやがらせですか．．．本番中みじめになる予感しかしない．

開始～AB解くまで

マスコットにvimrcとテンプレートを打ち込んでもらう．たこくんと一緒にA問題を読み，方針の確認．どうやら，前の方から詰めていくだけっぽい．たこくんに書いてもらうことにし，僕はB問題を読み始める．．．紙って配られないの？

B問題は構文解析しないといけない可能性も考えたが，左側から順番に計算する方法は単純なループで計算でき，掛け算を優先する方法は先に掛け算記号の処理をすればいい．結局その方針で解くことに．

A問題をたこくんがサブミット→WA．ちょっと時間がかかりそうだったので印刷して代わってもらう．Bを実装し提出，AC．たこくんが条件のミスを発見．訂正し提出→AC．

FとCを解くまで

AB正解したので僕はCを読み，たこくんには後ろの方からざっくりと問題を読んでもらうように指示を出す．
ここでC問題の読み間違えが起こり，依存関係が入口に遠い方から，入口に近い方にしかない（c < d)という条件を忘れてしまう（僕のミス1回目）．「他のチームがいっぱい解いているのに，こんなに難しいの？」とか思ってた．ここでだいぶ時間を使ってしまう．

スコアボードを確認すると，Fを解いているチームが結構ある．詰まってしまったのでFを読んでみる．グラフっぽい問題，クラスカル＋橋の列挙でいけるなぁと思い，たこくんにライブラリの打ち込みを頼む．（僕のミス2回目．マスコットにやってもらうべきだった）

たこくんがライブラリの入力を終了し，実装に移る．ここでふと気が付く．
「この二辺連結成分のライブラリ．．．どうやって使うんだっけ？」
幸い，うろ覚えの使い方でよかったのだが，ここで一気に混乱してしまい，実装がうまく進まない．
一端PCから離れて考え直したり，冷静になろうと思ってペットボトルで頭を殴ったりしてた．
ぐだぐだ悩みながら実装を行い，何とかAC．この段階でC問題を他のチームがかなり解いてる．

やっぱりCって簡単なんだよなーと思い，問題を読み直す．しばらくして，c < dの条件に気が付く．なんだC問題簡単じゃん→実装→AC．

後でコーチに聞いた話だと，Cを飛ばしてFを解き最下位争いをしている僕らのチームが一瞬取り上げられたらしい．

終わりまで

「軽食食ってきまーす．」と言って問題とともに去る．Gを解いているところが結構あったので，Gの解法を考えてみる．なんだかSegment Tree使いそうな気配がビンビンする．でもよくわからないなぁとか思ってた．
階乗に戻ると，たこくんがD問題をやっている．いろいろ質問されたが，変なことを言ってしまう（僕のミス3回目）．ここでちゃんと対応していれば，5完できていたのですごく失敗だったと思う．
終了間際に，たこくんがDの実装を完了し，提出→WA．これは直せないかなーと思いながらも最後まであがくがACできず．

反省

初の参加で，かつ，全員開催日前後に何らかのタスクを抱えていて練習できてなかったのがつらかった．
そして，僕のワンマンチームだとずっと思い込んでいたのが失敗だった．たこくんをもっと有効活用してあげられたらもっと上を狙えたのかなぁと．完全に采配ミス．

目標の4完は達成できたのでよかった．しかし，順位では下から数えた方が圧倒的に早いので悔しい．
唯一の救いはリクルートさんがNiku Awardをくれたこと．

僕のわがままに付き合ってくれた，たこくん，マスコット（あおこ）さん，先生，ありがとうございました．肉がもらえるらしいので許してください．

来年からは，九大から参加することになる予定なので，足を引っ張らないように頑張りたいと思います．それまでにいっぱい練習しておかないと．

2014-09-16

ICPC-JAG Day4 Problem F

ICPC JAG

解説では，Suffix Array + Range Minimum Queryでの解法が紹介されていましたが，僕はクエリ先読み + Aho-Corasick法で通しました．というか，Suffix Arrayよくわかってない．

ある人には，「クエリ先読みするなよ」と言われました．

概要

文字列SとQ個のクエリが与えられる．
i番目のクエリは2つの文字列x[i], y[i]で表現され，クエリに対してSの部分文字列の中でx[i]で始まりy[i]で終わるものを探す．

方針

クエリを先読みし，オートマトンをつくり，Sの中でx[i]が初めに出現するところと，y[i]が最後に出現するところを探す．
Sと全てのy[i]を前後逆にしてしまえば，両方とも全く同じアルゴリズムでよい．

Aho-Corasick法のマッチングを全部取っていくのは無駄．例えば，a, aa, aaa, ... みたいなケースが来たときに，aの判定を真面目にやると計算量が大きくなって時間的にもメモリ的にもつらい．これを改善するため，各状態について受理された文字列の判定は1回だけしか行わない．その時点で受理された文字列があるかの判定は，失敗したとき用のリンクを使って根か，既に判定済みの状態に到達するまでさかのぼることで行う．

ライブラリ写して，ちょっと手を加えて，簡単な実装やるだけだった．ライブラリになっているとはいえ，そこそこ実装コストがある．ただ，聞いた話だとSuffix Arrayも似たようなぐらいの実装量が必要になるらしい．そこにRMQの実装も加わるので，実装コストはこっちの方が若干軽いのかもしれない．

#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

string S;
int m;
vector<string> vx, vy;

struct PMA{
    int id;
    PMA *next[30];
    vector<int> accept;
    bool flag;
    PMA() { fill(next, next+30, (PMA*) NULL); flag = false; }
};
void buildPMA(const vector<string> &words, vector<PMA*> &vp){
    int n = words.size();
    PMA *root = new PMA();
    root -> id = 0;
    vp.push_back(root);
    int count = 1;
    for(int i = 0; i < n; ++i){
        PMA* v = root;
        int m = words[i].size();
        for(int j = 0; j < m; ++j){
            int c = words[i][j] - 'a'+1;
            if(v->next[c] == NULL){
                v->next[c] = new PMA;
                v->next[c] -> id = count++;
                vp.push_back(v->next[c]);
            }
            v = v->next[c];
        }
        v->accept.push_back(i);
    }
    queue<PMA*> Q;
    root->next[0] = root;
    for(int c = 1; c < 27; ++c){
        if(root->next[c] != NULL){
            root ->next[c]->next[0] = root;
            Q.push(root->next[c]);
        } else root->next[c] = root;
    }
    while(!Q.empty()){
        PMA *v = Q.front(); Q.pop();
        for(int c = 1; c < 27; ++c){
            if(v->next[c] != NULL)
                Q.push(v->next[c]);
            PMA *r = v->next[0];
            while(r->next[c]==NULL) r = r->next[0];
            if(v->next[c] != NULL)
                v->next[c] ->next[0] = r->next[c];
            else
                v->next[c] = r->next[c];
        }
    }
}
void searchfirst(const string &s, const vector<string> &word, vector<int> &r){
    vector<PMA*> vp;
    buildPMA(word, vp);
    PMA *p = vp[0];

    for(int i = 0; i < s.size(); ++i){
        p = p->next[s[i]-'a'+1];
        PMA *q = p;
        while(!(q->flag)){
            EACH(j, q->accept){
                r[*j] = i-word[*j].size() + 1;
            }
            q->flag = true;
            q=q->next[0];
        }
    }
}
int main(){
    cin >> S >> m;
    for(int i = 0; i < m; ++i){
        string x, y;
        cin >> x >> y;
        reverse(ALL(y));
        vx.push_back(x);
        vy.push_back(y);
    }
    vector<int> rx(m, -1), ry(m,-1);
    searchfirst(S, vx, rx);
    reverse(ALL(S));
    searchfirst(S, vy, ry);
    for(int i = 0; i < m; ++i){
        int idx = S.size()-ry[i];
        if(idx < rx[i]+vx[i].size() || rx[i] < 0 || ry[i] < 0){
            printf("0\n");
        }
        else{
            printf("%d\n", (S.size()-ry[i])-rx[i]);
        }
    }
    return 0;
}

2014-09-10

POJ 2441: Arrange the Bulls

POJ 蟻本

概要

牡牛がN頭いて，M個のコートに1頭ずつ割り当てたい．
牡牛はそれぞれ好むコートが決まっている．
割り当て方は何通りあるか．

解法

bitDPやるだけ．
ただし，愚直に実装するとMLEを起こすはずなので，配列の再利用をする．

int N, M;
int P[30];
int B[30][30];
int dp[2][1 << 20];
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d", P+i);
        for(int j=0;j<P[i];++j){
            scanf("%d", B[i]+j);
            --B[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    int *prev = dp[0], *next = dp[1];
    prev[0] = 1;
    for(int i = 0; i < N; ++i){
        memset(next, 0, sizeof(dp[0]));
        for(int s = 0; s < (1 << M); ++s){
            if(!prev[s]) continue;
            for(int j = 0; j < P[i]; ++j){
                int f = 1 << B[i][j];
                if(!(f & s)){
                    next[s | f] += prev[s];
                }
            }
        }
        swap(prev, next);
    }
    int res = 0;
    for(int i = 0; i < (1 << M); ++i){
        res += prev[i];
    }
    printf("%d\n", res);
    return 0;
}

2014-09-09

POJ 2886: Who Gets the Most Candies?

POJ 蟻本

POJ100問AC記念．

概要

N人の子供が一枚ずつカードを持っていて，輪になって並んでいる．
K番目の子供からスタートする．まず，現在選んでいる子供を輪から除外する．除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ．これを繰り返す．
i番目の操作で除外された子供は，iの約数の数だけキャンディをもらえる．
一番多くキャンディをもらえる子供は誰か．

解法

約数の個数は篩みたいにするとうまく計算できる．
子供を除外してずれる番号は，BITをうまく利用して管理する．
次に選ぶ子供はBIT上で二分探索をして求めることができる．

注意

同じ個数を得る子供は，先に輪の外に出た方を出力．
カードの番号が負の時の扱いに注意

const int MN = 500010;

int N, K;
int A[500010];
char name[500010][16];
int bit[500010];
bool isPrime[500010];
ll F[500010];

void update(int i, int v){
	++i;
	while(i <= N){
		bit[i] += v;
		i += i & -i;
	}
}
int get(int i){
	++i;
	int res = 0;
	while(i>0){
		res += bit[i];
		i -= i & -i;
	}
	return res;
}
int find(int num){
	int lb = -1, ub = N;
	while(ub - lb > 1){
		int mid = (ub + lb) / 2;
		if(get(mid)-1 < num){
			lb = mid;
		}
		else{
			ub = mid;
		}
	}
	return ub;
}
void solve(){
	memset(bit, 0, sizeof(bit));
	for(int i=0;i<N;++i)update(i,1);
	int mx = 0, ridx = 0, idx = --K;

	for(int k=0;k<N;++k){
		if(F[k+1] > mx){
			mx = F[k+1];
			ridx = idx;
		}
		update(idx, -1);
		if(k == N - 1) break;
		int num = N - k - 1;
		if(A[idx] > 0){
			K = (K + A[idx] - 1) % num;
		}else{
			K = (K + A[idx]) % num;
		}
		if(K < 0) K += num;
		idx = find(K);
	}
	printf("%s %d\n", name[ridx], mx);
}
main(){
    for(int i = 0; i < MN; ++i) F[i] = 1;
    for(int i = 2; i < MN; ++i) if(!isPrime[i]){
		for(int j = i; j < MN; j += i){
			int k = 0;
			for(int l=j; l % i == 0; l /= i, ++k);
			isPrime[j] = true;
			F[j] *= k + 1;
		}
    }
	while(~scanf("%d%d", &N, &K)){
		for(int i=0;i<N;++i){
			scanf("%s%d", name+i, A+i);
		}
		solve();
	}
	return 0;
}