AGC002 D. Stamp Rally
問題
やること
- 二分木探索で, 最大のスコアを探索する
- midまでの辺のfromとtoのノードを, union_findでuniteする
- union_findでは同じグループの数をuniteするときに一緒に計算しておく
- を含むグループの数と, を比較し, high, lowを更新する
これを 回処理すると, 間に合わないので並列に行う.
以降実装とコツ
- 多分再帰で実装したほうが良い.
- f(depth, low, high, その範囲で計算する人たち) みたいな感じで実装する
- depthがなぜ必要なのかは後で
- と が同じグループに属している時, 片方のグループのみで数える
- 重複は数えないため
- カウントして, 同じグループに属していたら2で割るみたいな処理をすれば良い
- 0人のグループになれば, 計算をしないようにする(1敗)
- union_findは, あらかじめ個作っておいて, 再利用する
- コンストラクタもかかるためかかる時間がバカにならない
- 再帰をかける順番を工夫して, midが小さい方から探索するようにする
- それぞれの深さで使用するunion_findを分ける. 深さはくらいなので, それをあらかじめ用意しておく
ソースコード
今回のソースコードは特にやばい
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <stack> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <cmath> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define INF INT_MAX/3 #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define pii pair<int,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define MIN(a,b) (a>b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define in scanf #define out printf #define ll long long #define ull unsigned long long #define eps 1e-14 #define FST first #define SEC second class union_find { private: vector<int> par; vector<int> rank; vector<int> count; public: union_find(int N):par(N), rank(N, 0), count(N, 1) { for (int i = 0; i < N; ++i) { par[i] = i; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { count[y] += count[x]; par[x] = y; } else { count[x] += count[y]; par[y] = x; if (rank[x] == rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int getCount(int x) { return count[find(x)]; } void clean() { par = vector<int>(par.size()); } }; struct Edge { int from; int to; Edge(int f, int t) :from(f), to(t) {} }; vector<int> res; vector<Edge> e; int memo_f[100001] = {}; int N, M, Q; vector<tuple<int, int, int> > q; vector<pair<int, union_find> > uf; void f(int depth, int low, int high, vector<int> people) { if (depth == uf.size()) uf.push_back({ 0,union_find(N) }); if (depth < uf.size()) assert(1); if (high - low <= 1) { for (auto &p : people) { res[p] = high; } return; } int mid = (high + low) / 2; FOR(i, uf[depth].first, mid) uf[depth].second.unite(e[i].from, e[i].to); vector<int> OKPeople; vector<int> NGPeople; for (auto &p : people) { int x, y, z; tie(x, y, z) = q[p]; int div = (uf[depth].second.same(x, y) + 1); if ((uf[depth].second.getCount(x) + uf[depth].second.getCount(y))/div >= z) OKPeople.push_back(p); else NGPeople.push_back(p); } uf[depth].first = mid; if(not OKPeople.empty()) f(depth+1, low, mid, OKPeople); if(not NGPeople.empty()) f(depth+1, mid, high, NGPeople); } int main() { memset(memo_f, -1, sizeof(memo_f)); cin >> N >> M; REP(i, M) { int a, b; cin >> a >> b; --a; --b; e.emplace_back(a, b); } int Q; cin >> Q; res.resize(Q); REP(i, Q) { int x, y, z; cin >> x >> y >> z; --x, --y; q.push_back(make_tuple(x, y, z)); } vector<int> people; REP(i, Q) people.push_back(i); f(0, 0, M, people); for (auto &a : res) { cout << a << endl; } return 0; }
感想
最近はあまり時間がないので解けた問題+1って感じだけどこの問題を解いた
永続配列を使ってunion_find解もあるらしく, 研究が辛くなったら実装しようと思う
東プレ REALFORCE 108UBK 変荷重キーボード/静電容量無接点/108キー/USB SJ08B0 レビュー
買ったやつ
東プレ REALFORCE 108UBK 変荷重キーボード/静電容量無接点/108キー/USB SJ08B0
- 出版社/メーカー: 東プレ
- 発売日: 2008/02/01
- メディア: Personal Computers
- 購入: 11人 クリック: 1,063回
- この商品を含むブログ (22件) を見る
使った感想
非常に日本語にしにくい 総じてすごく良い感じだった
日本語にできる範囲では…
- 音が静かになった ガチャガチャではなく静かになった
- 変荷重とやらを買ってみた リアルフォースといえばALL30gの印象が強く, 最初はfキーとかが少し重い印象だったけどすぐに良い感じになった
- 小指キー相当のものが30gになっているので, ぼーっとしていたらキーが入っていることがそこそこにあった(押し込まなくても反応するため)
- 押し込んだ位置ではなく, (多分)押した瞬間に反応するので, 入力したいキーの前後が入れ替わる的なことは起きなくなった(気がする)
- 少しキーが浅いキーボードでなれていたので, 深い気がする これも慣れた(きちんと押し込まなくても反応するし)
- 重いので, 安定感がある でもちょっと移動させたい時に少ししんどい
- 字が薄い(特殊な印刷方法をしているらしい? でも黒いやつは消えるらしい)
- かな入力用の文字が印刷されていない(悲しい)
- 普段触ってる1000円キーボードがおもちゃって感じるようになった
ALL30gのやつも試してみたい
LOGICOOL ワイヤレストラックボール M570t レビュー
久々のレビュー記事 マウスをトラックボールにしてみました。
他でもよく書かれていることとあまり書かれてないことを書きたいと思います。
買ったやつ
- 出版社/メーカー: ロジクール
- 発売日: 2013/08/02
- メディア: Personal Computers
- この商品を含むブログ (28件) を見る
使った感想
- 噂通り, 手を動かさないのでアームレストを最大限に機能させて使って手に優しいって感じだった(実際マウスだこが軽減できた)
- マウスホイールで横にスクロールできると勝手に思い込んでいたが, このトラックボールではそんなことはなかった
- サイドボタンが地味に便利
- サッーとボールを弾くように回せば, 24インチドュアルディスプレイ端から端までサーっと移動してくれる(どうやら回転速度が速かったら同じ回転量でも遠くに移動するようになってるらしい)
- 思ったより精密に動いてくれる(どうやら回転速度が遅かったら同じ回転量でも短く…)
- クリック(特にミドル)が斜めになっているので力の加え方に少しコツがいる
- ThinkPadのトラックポイントと慣れるのに同じくらい時間がかかった(2,3時間くらい いまだに超精密な動作とCAD用には使えていない)
- 2日に一度くらいボールをとってゴミを取らなければならない(使用頻度, 手のコンディションによると思う 人、ロットによっては全然らしい)
総じて, 前のマウスとは値段が高いが、十分良いと思う。 マウスよりダイナミックに動けるのが意外
昔のやつに比べて劣化してるらしいが昔のやつを知らないのでよくわからない
現在は研究室でマウス, 家ではトラックボール, (ノートPCはトラックポイント)を使っているが, 特にマウスに違和感を感じるということはない 長年扱ってきたものだからだろうか
いずれは研究室もトラックボールにするよてい
あとこれも気になってる
ELECOM マウス トラックボール ワイヤレス 6ボタン ブラック M-XT3DRBK
- 出版社/メーカー: エレコム
- 発売日: 2015/10/17
- メディア: Personal Computers
- この商品を含むブログ (1件) を見る
Codeforces #367 Div.2 C. Hard problem
problem
問題要約
コスト
と
文字列
が与えられる。
をするために, コスト がかかる
うまいことをして, 文字列を辞書順に昇順()となるようにしたい.
昇順にできるとき, 最小の総コストを求めて, どう頑張ってもできない時は-1を出力する
解き方
dpを使う
: 番目の文字列までを昇順にするときに必要な最低のコスト
ここで, の時, n番目をひっくり返すときを意味し, の時, n番目をひっくり返さないことを意味する.
更新式は数式で表記すると面倒なので, ソースコード参照
事前処理として, を反転させた配列を用意しておく
注意事項
がやたらでかいので, オーバーフロー, infの定義に注意する
最終的な出力の最大値は,
SourceCode
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define linf 0x3f3f3f3f3f3f3f3f #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define pii pair<int,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define MIN(a,b) (a>b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define in scanf #define out printf #define ll long long #define ull unsigned long long #define eps 1e-14 #define FST first #define SEC second // n次元配列の初期化。第2引数の型のサイズごとに初期化していく。 template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } int main(void) { int N; cin >> N; vector<int> C(N); for(auto &a:C) cin >> a; vector<string> S(N); for(auto &a:S) cin >> a; vector<string> revS = S; REP(i,N) reverse(ALL(revS[i])); ll dp[100001][2] = {}; REP(i,100001) REP(j,2) dp[i][j] = (ll)(1e14); dp[0][0] = 0; dp[0][1] = C[0]; FOR(index, 0,N-1){ if(S[index] <= S[index+1]) dp[index+1][0] = min(dp[index+1][0], dp[index][0]); if(revS[index] <= S[index+1]) dp[index+1][0] = min(dp[index+1][0], dp[index][1]); if(S[index] <= revS[index+1]) dp[index+1][1] = min(dp[index+1][1], dp[index][0]+C[index+1]); if(revS[index] <= revS[index+1]) dp[index+1][1] = min(dp[index+1][1], dp[index][1]+C[index+1]); } ll res = min(dp[N-1][0], dp[N-1][1]); cout << (res>=1e14?-1:res) << endl; return 0; }
Codeforces #366 Div.2 C. Thor
Question
問題要約
個のクエリが渡される クエリは以下の書式で渡される
t x
ここで,
- の時: アプリケーションが通知を生成する
- の時: アプリケーションが生成した通知をすべて読む (過去に読んだやつももう一度読む)
- の時: 生成された通知を, アプリケーション関係なく, 最初から数えて回目までのものをすべて読む.
各クエリ毎に, まだ読んでいない通知を出力する.
やること
以下の4つを用意する(少し冗長な気がする)
(は, アプリケーションの個数)
- app[アプリの番号]: 何個未読の通知を持っているか
- queue addedTime[アプリの番号]: いつ通知されたか
- memo[生成された順番]: なにが生成されたか
- sum: 現在の個数
この4つを実装し, 問題文のとおりに書くだけ 時間がギリギリなので.at()とかでアクセスしたらTLEした.
SourceCode
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> #include <array> #include <cmath> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define uinf 0x3f3f3f3f3f3f3f3f #define CLEAR(a) a = decltype(a)() #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define pii pair<int ,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define VVI vector<vector<int>> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define pi 2*acos(0.0) #define INFILE() freopen("in.txt","r",stdin) #define OUTFILE() freopen("out.txt","w",stdout) #define ll long long #define ull unsigned long long #define eps 1e-14 #define FIN std::ifstream cin("D:\input.txt") const int MOD = 1e9 + 7; signed int main(void) { ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<int> app(N + 1); vector<queue<int>> addedTime(N + 1); vector<int> memo; memo.reserve(Q+1); int readtime = 0; int sum = 0; REP(i, Q) { int t, x; cin >> t >> x; if (t == 1) { memo.push_back(x); app[x]++; addedTime[x].push(memo.size()-1); ++sum; } if (t == 2) { sum -= app[x]; app[x] = 0; while (not addedTime[x].empty()) { int que = addedTime[x].front(); addedTime[x].pop(); memo[que] = 0; } } if (t == 3) { for (; readtime < x; ++readtime) { app[memo[readtime]]--; if(memo[readtime] != 0) --sum; } } cout << sum << endl; } return 0; }
感想
基本的にはやるだけ… のはずだった WAWAWAWAWA....
C++で書いたけど結構時間ギリギリになってしまった
2完で終わる悲しい結末になった
Undertale ubuntuのsaveファイルの場所
Gルート後、Gルート用のsaveファイルになってしまうらしい
とにかく, saveファイルをリセットしたい時がある
ところで, このゲームすごいストーリーが面白くて、英語が難しい
英語の勉強に使っているのだがかれこれ12時間英語漬け
いい英語の教材を買ったかもしれない
場所は
.config/UNDERTALE_linux_steamver
ABC042 D いろはちゃんとマス目
Question
やること
Abstruct
長方形の通れない場所の右の部分と上の部分の2つに分割して、
の経路の数を, すべてので計算して, sumすればよい。(上下にわけられた長方形の間の移動は, 1通りの経路のみ)
へ移動する経路の数は,
で求めることができる。
これは、 で前処理をしておいて, 後でで求める
その具体的な方法は http://hos.ac/slides/20130319_enumeration.pdf この記事を参照するとわかりやすい.
ここでは深く言及しない。
SourceCode
const int MOD = 1e9 + 7; // x^n % mod // O(log n) template<typename T> T mod_pow(T x, T n, T mod) { T res = 1; while (n > 0) { if (n & 1) res = res * x & mod; x = x*x %mod; n >>= 1; } return res; } // fact(n)%MOD, invFact(n)%MOD, inv(n)%MOD, nCk // Constructor O(N) // other O(1) template<typename T, int MOD> class Choose { public: vector<T> fact, inv, invFact; Choose(T N):fact(N), inv(N), invFact(N){ inv[1] = 1; FOR(i, 2, inv.size()) inv[i] = MOD - (MOD / i) * inv[MOD%i] % MOD; fact[0] = invFact[0] = 1; FOR(i, 1, fact.size()) { fact[i] = fact[i - 1] * i % MOD; invFact[i] = (invFact[i - 1] * inv[i]) % MOD; } } //Get nCk T operator () (T n, T k) const { if (not ((T)0 <= k and k <= n)) return 0; return (((fact[n] * invFact[k]) % MOD)*invFact[n - k]) % MOD; } }; ll f(ll x , ll y, const Choose<ll, MOD>& c) { return c(x + y, x); } signed int main(void) { ll H, W, A, B; cin >> H >> W >> A >> B; Choose<ll, MOD> c(H + W); ll ans = 0; FOR(i, B, W + 1) { ans += f(H - A - 1, i, c) * f(A - 1, W - 1 - i, c); ans %= MOD; } cout << ans << endl; return 0; }