Facebook hacker cup Qualification Round
問題3
非負整数列 aは以下の性質を満たす数列である。 「aの要素は、直前のk個の要素に含まれない最小の数である。」 最初のk項が与えられるので、n番目の要素の値を求めよ。
制約
解法
考察してみると, a[k]からa[k + k + 1]までの列が繰り返されていることがわかる。 その数列は、priority_queueを使えばO(klogk)で計算できる。
コード
int main(){ int T; cin>>T; REP(CASEN, T){ printf("Case #%d: ", CASEN + 1); int N, K; cin>>N>>K; ll A, B, C, R; cin>>A>>B>>C>>R; vector<int> use_cnt(2 * K, 0); queue<ll> M; for(int i = 0; i < K; i++){ if(A < 2 * K) use_cnt[A] += 1; M.push(A); A = (B * A + C) % R; } priority_queue<int, vector<int>, greater<int> > que; REP(i, 2 * K) if(use_cnt[i] == 0) que.push(i); if(N - K <= K + 1){ REP(iter, N - K - 1){ que.pop(); int f = M.front(); M.pop(); if(f < 2 * K && --use_cnt[f] == 0) que.push(f); } int ans = que.top(); cout<<ans<<endl; }else{ vector<int> a(K + 1); REP(i, K + 1){ a[i] = que.top(); que.pop(); int f = M.front(); M.pop(); if(f < 2 * K && --use_cnt[f] == 0) que.push(f); } int idx = (N - K - (K + 1) + (K + 1 - 1)) % (K + 1); cout<<a[idx]<<endl; } } return 0; }
SRM 567 参加記
250
問題文
かつ
が整数になるような組(A, B)の個数を求めよ。
制約
考えたこと
- はじめの5分ほど
と勘違いしていた
- 式を変形すれば
が整数であればよいことがわかる
- つまり平方数
- Aを固定して考えてみる
- う〜ん…
- ABを固定して考えてみる
- う〜ん…
- Aを固定してうまくいくアイデアを思いつく
- S * Aが平方数になるような最小の数Sを求めれば、Bは
の形で表せる。
- Sは素因数分解すればわかる
- 素因数分解で失敗しないように気をつけて書いた。
500
問題文
長い
考えたこと
- 手を動かしてみる
- 各アルファベットの個数だけ考えれば良さそう
- 表を作ってみる
- Aがどのアルファベットを先頭に選ぶのがよいか考えてみる
- 個数がどの文字列にも負けてないなら、その文字を選んで問題無さそう。
- その文字で勝った相手はそれ以後無視出来る。
- 貪欲っぽい
- 選ぶものがなくなるまで置き続けた
ステマ
はてなオリジナルTシャツ2012 - はてな
わああーこのTシャツかわいいー！
Userstreamを監視して，デリートされたつぶやきを出力する
tweepyのStreamを使った．かんたん．
使いどころは知りません．
#!/usr/bin/env python # coding: utf-8 from tweepy import OAuthHandler, Stream from tweepy.streaming import StreamListener CONSUMER_KEY = 'bigbig' CONSUMER_SECRET = 'hogehoge' ACCESS_KEY = "fuwafuwa" ACCESS_SECRET = "mofmof" class Listener(StreamListener): def id_search(self, status_id): for s in self.statuses: if s.id == status_id: return s return None def __init__(self, api=None): StreamListener.__init__(self, api) self.statuses = [] def on_status(self, status): self.statuses.append(status) if len(self.statuses) > 1000: p = self.statuses.pop(0) def on_delete(self, status_id, user_id): s = self.id_search(status_id) if s: print(u"@{name} {text}".format(name=s.author.screen_name, text=s.text)) auth = OAuthHandler(CONSUMER_KEY,CONSUMER_SECRET) auth.set_access_token(ACCESS_KEY,ACCESS_SECRET) l = Listener() stream = Stream(auth, l) stream.userstream()
blog移転
http://ichyo.jp/blogに移転するかもしれないしないかもしれない．
KUPC 2012
京都大学プログラミングコンテストにオンサイト参加した．
5時間の長丁場だけど，時間をフルに使えた気がするし，問題も楽しかった．ジャッジさんお疲れ様でした．
結果は703点で30位．欲を言えばあとK問題の60点は取りたかった…．
解法
A問題
x, 2*x, ... を E + Tを超えるまで計算する方法でやった．O(NT)?
B問題
１分ほどながめても全然わからんからとばした．開始三時間ぐらいで，左端に置く，右端に置く，パスを，頭から優先的に選ぶシミュレーションを書いたらなぜか通った．解説聞いてもよくわからんかった．
C問題
各うさぎについて，仲の悪いうさぎがいるかどうか計算するだけ．50*50の配列作ればいいところを，わざわざsetでやってしまった．反省．
D問題
最初，最小費用流で解ける問題だと勘違いしていて，ここでだいぶ時間を食ってしまった．最終的には貪欲的に解けると気づけた．
「1を含む範囲のなかで終点が一番大きいものを選ぶ→前回選んだ範囲の次の部屋を含む範囲のなかで終点が一番大きいものを選ぶ→」を繰り返せば良い．
E問題
最初は勝ちの数が多いほど手が出やすくなるようなランダム選択をした．1つのケースだけうまく行かなかったので，前半500と後半500に分けて，前半で得られたポイントの数を数えて，後半はポイントを得やすい手を選ぶようにした．
F問題
1日ごとの処理を頑張って速くする問題かなーと思った．サービスを復旧時間順にソートするとか，復旧した時点で，それ以降の復旧度の増加値を計算するとかをやったら，5秒制限を4.3秒で通った．やってることはO(Day * x)なので，最悪ケースだと計算量が10^10になってダメな解法(?)
G問題
xでソートして枝刈りをする嘘解法っぽいのを出したら，一個だけTLEになった．がんばって定数倍高速化してみたけどぜんぜん意味がなかったし，45度回転させたら通ったので最初からそれをやるべきだった．
H問題
読んでない
I問題
点を二つ選んで角度を求めると直線が二つ作れるので，その交点を選ぶようにした．ローカルのリアクティブプログラムだとE=0のときは常にACがでるのに，サーバー側だと1つのケースしかACが出なくて謎だった．いろいろごにょごにょやってたら通ったので多分誤差の関係．
J問題
読んでない
K問題
bfsでint memo[N][2^M] の配列を埋めるような解法で部分点取れるかと思ったが１個だけTLEが出てダメだった．O(N*N*2^M)なのでさすがにだめか…．
