結構前のコンテストですが、G問題がシンプルだけどどこか新鮮で面白かったので紹介します Dashboard - 2016-2017 National Taiwan University World Final Team Selection Contest - Codeforces 概要 N個(値段:p_i)の空でない部分集合であってK番目に値段の…

問題: http://codeforces.com/contest/528/problem/D問題概要は省略します.典型なのかもしれないけど, あんまりこういうの解いたことなかったので面白かった解法:流石にまとめてマッチ箇所を求めるのは大変そうなので, 置く場所は全部試すことにする. そこで…

Problem - E - Codeforcessegment treeを使って頑張ると解ける(dfsしながらやると上手く行く系) #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define pb push_back #define mp make_pair #define fi first #define se second #define FOR(i,a,b) for(</int,></bits/stdc++.h>…

Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。b[n-1] = 0に気付けると、 dp[0] = 0, dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1) とすればO(N^2)で計算出来ることがわかる。 y = b[j] * x + dp[j]のa[i]での値であって、b[j]…

1~nを並び替えた数列があって、a番目とb番目を入れ替えるクエリがm個来るが、それぞれのクエリは1/2の確率でしか実行されない この時クエリをm個処理した後の反転数の期待値を求めよ p[i][j] : i番目 最後に足し合わせることで期待値が求まる。 Div1Dにして…

Div2だけど1位とれて嬉しい(小並感) Div2E本番中に通せたの初めてな気が。mathのおかげA. やるだけ __gcd()使おう int n; int a[100010]; int g; int main(){ cin >> n; rep(i, n){ cin >> a[i]; if(!i) g = a[i]; else g = __gcd(g, a[i]); } rep(i, n){ if…

期末が出来なさすぎて冷えきっています。 Div1復帰。Div1に残れる実力をつけなければ....A. 初め問題文間違っていてimfだった 適当に実装. なんでAでこんな書いたんだ... const int dx[] = {1,0,-1,0}; const int dy[] = {0,1,0,-1}; int x, y, k = 1, dir; …

今日は鉄緑会という塾の校内模試がありました. 鬱になったので出れなかった回のを解きました.solved5outof5になると緑になるらしくて達成感が少し a. やる int n, s, ret; int main(){ cin >> n; rep(i, n){ int tmp; cin >> tmp; s += tmp; } FOR(i, 1, 6) …

こどふぉってこんな人数多かったっけ・・・ ○○○×- 203位 (アカン)a. 実装 int y; bool check(int c){ bool f = true; set<int> u; while(c > 0){ int d = c % 10; if(u.find(d) != u.end()) return false; u.insert(d); c /= 10; } return true; } int main(){ ci</int>…

本選までにTopcoderとCodeforces両方Div1上がれたらしい。けどすぐ落ちそう。A. やる int n, ans; int h[50], a[50]; int main(){ cin >> n; rep(i, n) cin >> h[i] >> a[i]; rep(i, n){ rep(j, n){ if(i == j) continue; if(h[i] == a[j]) ans++; } } cout <…