ACM-ICPC 2016 Asia Tsukuba Regional 参加記

チームcatsatmatで出場してABCDEFGの7完11位でした。真面目にUSキーボードの練習をしたので今度はJISがわからなくなって困っています。しかし環境に慣れていなかったのはアレかなあ 自分はgeditで頑張りましたまずコンテストパートについて自分はパソコン操…

SA-IS

Suffix Arrayを空間・時間計算量共に線形で構築出来るというアルゴリズムSA-ISを, 以前ふわっと読んだことはあったけれど真面目に読みなおしました. よく出来過ぎだと思う. 細かいところの理解が間違っていたら教えて下さい. ざっくりとした流れしか書きませ…

JAG夏合宿2016参加記

参加記を書き書き(典型)去年に引き続きJAGの夏合宿に参加してきたので感想を書きます(合宿代安くて有り難すぎる)ICPCアジア地区のチーム(catsatmat)のうち自分だけの参加となりました(悲しい)・day1 合宿初日、コンテストは無し。懇親しなかったのでtozangez…

Atcoder Grand Contest No.2

コンテストを寝過ごしたので解いた. Dの一般的なテク感すき. きれい. Bが面白い感あったEはとりあえずグリッド上を動くゲームなことまではわかったけどあんま考えてない. Fの方針が解説と少し違ったので書いておこう.1~Nの1番左のもの(0は無視)がこの順番に…

Codeforces #296 Div1 D. Fuzzy Search

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

SRM456 Div1 hard FunctionalEquation

rngさんの問題表を適当に解いていたら聞いたことあるのが出てきたので解いた. 自力で解けて嬉しいというか実質初めて解いたhardがこんな重いのになってしまった(平均的難易度を知らないのでなんとも言えない, hardは怖い)関数方程式という問題名, 一体競技プ…

AOJ2636 Distance Sum

問題: Distance Sum | Aizu Online Judgeブログ書くのめんどくさい. 問題文はとても読みやすいので読んでください. 解説:普通に順番に1からNまで追加してシミュレーションします.まず, i番目を追加した時, i-1番目の時和を最小化する頂点(vとする)とのパス上…

AOJ-ICPC-favorite

好みが普通すぎて面白く無いかもしれません 現在の難易度でsortします・5002333 My friends are small My friends are small | Aizu Online Judge・6002439 Hakone Hakone | Aizu Online Judge2336 Spring Tiles Spring Tiles | Aizu Online Judge2256 Divid…

AOJ2453 Presentation

AOJ

問題: Presentation | Aizu Online Judge概要: 二分木をコピペして作る 解法: 面白かったけど構文解析パート必要ない。あと配列サイズ難しい。重要なのは, 切り貼りすると1番深いところの深さが元のやつより増加するので,最終的に1番深いところ(どれでもいい…

AOJ2338 よくわかる二重魔法

AOJ

問題: Intelligible Double Magic | Aizu Online Judge要約すると、N頂点M辺の無向グラフが与えられるので好きに辺を有向にして(u,v)...uからvにいける ような組を多くせよ、という問題(N lowlinkを使って二重辺連結成分分解し重みつき木にしてdpすれば求め…

AOJ2377 ThreeRooks

AOJ

これで1200+以外は1問以上解いた事になった 概要X*YのマスにK匹のうさぎがいる。互いに攻撃できないように3個のルークを置く場合の数をmod 10^9+7で求めよX,Y 解法 3個同じ所に並んでいる場合 2個並んでいて1個はその範囲にはない 3個が直角に並んでいる場合…

AOJ2603 Time Table

AOJ

バスをm本走らせてn人拾う時の待ち時間の和の最小値を求める問題 とりあえずバス停の場所を時間からひくといつ出発するとちょうどかがわかるので、それをsortしてTiとおくまず何も考えずに愚直なdpの式を立てると dp[i][d] = min{0dp[i][d] = i * t[i] - Si …

AOJ2445 MinimumCostPath

AOJ

MinimumCostPath | Aizu Online Judge まあまあ面白かったn * n (nどう見てもスカスカで、殆ど邪魔されずに行けそうだけど左下と右上付近は混雑するかもしれないので、近くだけbfsして後はdp(経路を最初に通る障害物で区別したりするとなんとかなる)

New Year Contest 2015

rng_58さんのコンテスト。まだあんまり解けてないけど面白かった。 とりあえずコンテスト中に通った分だけA : 愚直にやればよい(vectorは比較出来るらしい) #include <bits/stdc++.h> using namespace std; #define pb push_back int n; vector<int> a,b; int main(){ cin>>n; wh</int></bits/stdc++.h>…

Pokemon Advent Calendar 2014 11日目

この記事はPokemon Advent Calendar 2014 - Adventarの11日目の記事として書かれたものです。最近はポケモンから遠ざかっていましたが、主催者のkagamizさんが辛そうだったので書くことになりました。ご確認ください。エンジョイ勢なので育成論とかは置いて…

AOJ2439 Hakone

AOJ

箱根駅伝。問題概要は略。 解法が面白かったのでメモdp[i][j] : 現在i位まで見てj個unmatchedな場合の数 として、 i番目が-ならそのまま, Dならi番目をそれまでの空いているところに入れるのでj通り, またi番目にそれまでのを入れる.... dp[i+1][j-1] += dp[…

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…