Codeforces #157 Div1 E Little Elephant and Tree

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>…

gcc4.9 インストール(OS X Yosemite)

C++

珍しくパソコン系かつ問題系でない話題。(メモ)#include<bits/stdc++.h> は前準備禁止なIOIとかICPCで特に役に立つ気がする(あとはテンプレート使わないで毎回0から書いてる人)— hogloid (@hogloid) 2014, 11月 12を見てbits/stdc++.hの存在に気付く > 試す > コンパイル</bits/stdc++.h>…

Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry

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]…

夏模試

夏休みに受けた模試3つが全部返ってきた(呟く気にはあまりならないのでここに載せることにした)受けた順に 東大オープン(河合) 英語の採点辛すぎるし数学はそこそこ大変だったのでこんなもん(理科悪すぎ)東大実戦(駿台) 英語(簡単) 数学(高1模試) 国語(puke)…

USACO 2014 January Contest, Gold

今月と見せかけて先月のGoldを解きました。Problem 1. Cow Curling N点から3点選んでできる三角形の領域の和集合が凸包になっていることがわかるので、凸包を作る。 N 外積を使って三角形の内外判定をすると判定できる。 これはテストケースがもっと強いと落…

JOI 2013-2014予選

JOI

予選敗退したのでソースだけ貼っておきます.1. 読む int ret; int main(){ rep(i, 5){ int t; cin >> t; ret += max(t, 40); } cout << ret / 5 << endl; return 0; } 2. 制約緩いし普通に上から見ればいいです int n, m; int piv, now; int v[1010]; int c[…

JOI 模擬予選

JOI

期末とはなんだったのか. 500/600点でした. 6の部分点取りに行かなかったのは良くない....1. 平均*5 - 残り. int s, a; int main(){ rep(i, 4){ int t; scanf("%d", &t); s += t; } scanf("%d", &a); printf("%d\n", a * 5 - s); return 0; } 2. 素直に計算…

USACO 2013 November Contest

BronzeとSilverを解きました.まずBronzeCombination Lock全部調べるだけ //include //------------------------------------------ #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include </numeric></functional></algorithm></bitset></stack></deque></set></map></list></vector>

SRM593 Div1

easyだけ通ったeasy : 絵を書くと、N * N全てを塗る場合でも3色で済むことがわかるので、二部グラフ判定するだけ. 六角座標はクソ(確信) const int dx[] = {-1,0,1,1,0,-1}; const int dy[] = {1,1,0,-1,-1,0}; class HexagonalBoard{ public: int n; vector<string></string>…

JOI春合宿 倉庫番(Sokoban)

JOI

グリッドグラフだ〜〜〜という気持ちになって頑張る. コードだけ上げておきます O(MN) #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (int)n; ++i) const int dx[4] = {1, -1, 0, 0}; co</cstring></algorithm></cstdio>…

PKU 3177 Redundant Paths

PKU

無向グラフが与えられて辺を追加して、各点間に二通りの経路ができるようにする時(その経路は同じ辺を使わってはいけない) 追加する辺の個数を最小化 二重連結であれば2通り経路があるのでlowlinkを用いて適当に現在のグラフの二重連結成分を頂点にしたグラ…

USACO 2012 December Contest Gold, Running Away From the Barn

N頂点の木が与えられるので各点について、距離がL以下かつ部分木に含まれる点の個数を出力せよ (N 各点について距離L以内でどこまで上に上がれるかわかればimos法するだけになるのでダブリングで処理 //include //-----------------------------------------…

JOIss2013

参加記です. JOIssは8/26~30に準山奥で開催されました.怖い本ばかりに見えて怯えながらコンピュータ・ジオメトリを選択しました. (指圧マットさんとhogloidさんと同じ班, チューターは藤原さんでした) 講義寝まくってすみませんでした..セミナーも楽しかった…

SRM585 Div1

コーナーケース氏死んでくれ〜〜 ちゃんと制約読もうeasy まあ色んな方法あるが自分は下から取っていくイメージ #define MOD (1000000007LL) ll p[1000010]; ll r[1000010]; class TrafficCongestion{ public: int theMinCars(int treeHeight){ int h = tree…

SRM583 Div1

1331->1501 初めての黄色!Med通せて嬉しみ。(遅いけど)Easy TravelOnMars 環状な路線での最短距離問題。bfsやるだけ modを取って負の値になることがあるので落ちまくっていたらしい int n; int d[60]; class TravelOnMars{ public: int minTimes(vector <int> ra</int>…

Codeforces Round #157 (Div. 1) D. Little Elephant and Broken Sorting

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

SRM578 GooseInZooDivOne

マンハッタン距離がdist以下のやつをunionfindでくっつけてから偶奇を見るだけ。 偶数のやつは何個使っても良くて、奇数のやつは偶数個使わなければいけないけど、 偶数のやつをP個, 奇数のやつをQ個とすれば Q >= 1の時 2 ^ (P + Q - 1) - 1, Q = 0の時 2 ^…

連結リスト

ポインタ難しいけどこの際listぐらいは実装できるようになろうと思ったら簡単だった(小並)こんな感じでいいのかな? #include <cstdio> #include <cstdlib> using namespace std; struct Node{ Node *prev, *next; int val; }; Node *head, *tail; void init(){ head = tail =</cstdlib></cstdio>…

Croc Champ 2013 - Round 2 (Div. 2 Edition)

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…

PKU 2777 Count Color

PKU

板があって、ある区間に色を塗るクエリとある区間の色の種類を数えるクエリが来るので高速に処理しろという問題です。 どうでみてもsegment treeだが区間の左右が逆なこともあるよとか言う制約読んでいなかった... #include <cstdio> #include <algorithm> using namespace std;</algorithm></cstdio>…

PKU 3269 Building A New Barn

PKU

要約 : 牛が二次元にn頭生えているので、全ての牛からのマンハッタン距離の和が最短となるような点は何個あるか??ただし牛がいるところは除く。どっかのJOIで見たサンタもどき。中央値を適正に考えると解ける。 隣接する点に牛がいないという制約のおかげで…

air-春合宿2013day1

JOI

本選落ちのガチクズなので家でまったりオープンコンテストに出ました。 起床に失敗して絶望。 130点でした。合宿行けててもだめだったなあ 1日目だけを見ると去年より適正な難易度に見えるBus tour -- バスの経路の交点(交線なら両端)、始点、終点を頂点にし…

Codeforces Round #171 (Div. 2)

期末が出来なさすぎて冷えきっています。 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; …

Codeforces Round #167 (Div. 2)

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

SRM 570 Div1

○-- +0/-0 164.02pt rate: 1467 -> 1472 easy解くの遅すぎて死んでしまいます 今回Challenge出来そうになかったし諦め。 med, 木dpなのはわかるがバグるし知らない。dp苦手すぎる... まあ550だし仕方ないねeasy - 周期4に気付いて適当に処理。よく見るとrep(…

Codeforces Round #166 (Div. 2)

こどふぉってこんな人数多かったっけ・・・ ○○○×- 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>…

JOI2012-2013本選参加記

JOI

プラクティスの日はそれなりに交流できて楽しかった。 結論から言うと2, 3がバグって1完しかできませんでした。去年と違ってそれなりに頑張っていたので無念な気持ちに..萎えてコード回収しなかったのでさっき書いたコードを貼っておきます。 合宿行ける人は…

AOJ0548 Reindeer with no sense of direction

全探索系苦手なので放置していたが本選前なのでやってみた。 教会から逆向きに探して、使ってない家があったら必ず配るをすると良いことに気付くだけ。TL緩いしあんまり工夫していない.... #include <cstdio> #include <cstring> using namespace std; #define rep(i, n) for(</cstring></cstdio>…

Bookshelf

JOI

こどふぉなんてなかったんや....あのDiv1Bとかbookshelfやってたら絶対解けたよね。 考えると重みが付いた最大増加部分列を求めると良いことがわかって、segtreeを使って処理。 (重さが全部1の時はよくあるやつ)重さの入力のが、並んでる順番に与えられてる…

Codeforces #164 div2

本選までに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 <…