AtCoder Grand Contest 009 B - Tournament
問題概要
略
やや雑な解法メモ
次のようなデータ構造を考える。
child[i] = [人iに負けた人たち]
また、次のようなDPを考える。
DP[i] = 人iが勝ち進んだところまでのトーナメント表の最小の深さ
child[v] = [m1, m2, m3, m4]の時、
miを人vが直近に対戦した順にk1, k2, k3, k4とすると、vが勝ち進んだところまでのトーナメント表は次のようになる。
未定の部分は貪欲に決まる。
できるだけトーナメント表が浅くなるようにするためには、k1にmax(DP[mi]) (=トーナメント表が深いもの) を持ってきたほうがよいからである。
DP[mi]を降順にソートしたものを[d1, d2, d3, d4]とすると、max(di+i)がDP[v]になる。
これを深さ有線探索で再帰的に求める。
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007LL #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; #define MAX_N 100010 vector<int> child[MAX_N]; ll dfs(ll node){ vector<int> v; for(auto ch: child[node]) { v.pb(dfs(ch)); } sort(v.begin(),v.end(),greater<int>()); //N log N ll tmp=0; REP(i,v.size()){ tmp=max(tmp,1+i+v[i]); } return tmp; } int main(){ int N; cin>>N; REP(i,N-1){ int a; cin>>a; child[--a].pb(i+1); } cout << dfs(0) << endl; }
今年読んだ技術書
年末で会社が休みなので、自分のために今年読んだり読まなかったりした技術書を整理します。
目次
全部読んだ
オブジェクト指向でなぜつくるのか
評価: ★★★★☆
自分用メモ: もう一度読むなら9章から
概要・感想など:
平易でわかりやすかったので、腰を据えてやらなくても通勤電車で大体読めました。
オブジェクト指向の本ですが、13章「関数型言語でなぜつくるのか」で関数型言語について解説しているのでお得 (?) です。
本気ではじめるiPhoneアプリ作り Xcode 7.x+Swift 2.x対応 黒帯エンジニアがしっかり教える基本テクニック
評価: ★★★★☆
自分用メモ: もう読む必要はない
概要・感想など:
読んで手を動かせば、それほど規模の大きくないアプリケーションならインターネットを頼りに作れるようになったり、なぜか急にiOS改修案件をやらされてもインターネットを頼りになんとかできるようなったりするんじゃないでしょうか。(なった。) (インターネットがすごい可能性。) (しかし、インターネットはXcodeの使い方を包括的に教えてくれない。)
なお、3連休1回で読み切ることができました。
最近、Xocde 8対応版が出たようです。(リンクはそれ。)
Java言語で学ぶデザインパターン入門
評価: ★★★★★
自分用メモ: 定期的に読んでもいい
概要・感想など:
GoFの23種類のデザインパターンがJavaで解説されています。
23種類を500ページ程度で解説しているので、まあまあ丁寧です。
完璧には覚えてなくてもこういうパターンがあるんだな、というのが頭に入っていると、コードを読む時に「あっ、進研ゼミで見たことある」感があり、理解がしやすくていいです。
半分以上読んだ
Rubyによるクローラー開発技法 巡回・解析機能の実装と21の運用例
評価: ★★☆☆☆
自分用メモ: もう読む必要はない
概要・感想など:
3章まで読んだけど、自分がやりたいことに必要な部分は2章までで十分だったので、あとは興味のある部分を拾い読みして終えました。
もっというと、Open-URI, Nokogiri, Anemone, Capybaraなどのキーワードが知れればそれで十分だったかも。
また、クロール対象のサイトのコードが変更されたことなどが原因 (?) で、サンプルコードが結構な割合で動かなかったのが辛かった。
筆者は「Webサイトはナマモノなのでそれに対応するスキルも培うべき」という意見のようですが、1, 2章くらいまでの内容は、筆者がクロールの練習をさせるためのウェブサービス (=コードが変わらないのでサンプルが常に正しく動く) を一つ用意して、それを対象にクローリングをおこなうような形式がよかったなと思います。
なお本書とは関係ないですが、jQueryを多少触ったことがある人が簡単なクローリングをする場合はRubyよりNode.jsのcheerio-httpcliがjQueryライクに書けるのでおすすめです。
(でも、clickのエミュレートはhtmlをパースしてurl取得してGETなので微妙です。)
これについて書かれてるっぽい本 (読んでない) も貼っておきます。
サーバー/インフラを支える技術
評価: ★★★★★
自分用メモ: 最後まで読む / 2週目もあり
概要・感想など:
現在進行系で読んでいる本。
開発エンジニアもそれなりに運用の知識があった方が良いことがわかってきたタイミングで、たまたまインターネットで紹介されていたので購入。
学生時代はさっぱり運用に興味がありませんでしたが、この本は読んでいてあまりつらくないです。
色々な方法があるなか「なぜ、どういう場合にこの方法を使うのか」の部分についてわかりやすく書かれているからという点が大きな理由です。
なぜの部分が薄い本はわりとありますが、興味の薄い分野だとつらいですね。
コンピュータアーキテクチャ
評価: ★★★☆☆
自分用メモ: 70%くらいの理解度で最後まで読む
概要・感想など:
大学時代の教科書。
CPU, メモリの仕組、機械語の命令、アセンブリ言語、パイプライン処理など、低レイヤの話。
大学時代に使っていたから (所有しているから) と理由で選んだ本なので、他のそれっぽい本 (コンピュータはなぜ動くのかとか?) と比べてどうかとかは気になるところではあります。
140ページ程度で、内容が非常に難解というわけでもないので、手を出しやすいのは魅力かもしれません。
ネットワーク超入門講座
評価: ★★★★☆
自分用メモ: 3月くらいにもう一度最初から読む
概要・感想など:
あまりにもネットワークの知識に疎いので、流石にどうにかしないとと思って読みました。
最初「ネットワークはなぜつながるのか」を読んでいたけど、つらくてリタイアしてしまったので、もうワンランク下の本を募集しておすすめしてもらった本です。
たしかに「ネットワークはなぜつながるのか」より内容が易しく読みやすかったけど、モチベーションの問題であまり読んだ内容が定着していない感じがする…
通勤電車で読んでいたけど、英語イベントが発生しそうで通勤電車では英語をするようにしたので停止中。
英語イベントが終わる or なくなるしたら再度読む予定です。
半分未満しか読んでない
半分未満しか読んでないので評価などはできないし、感想のみにします。
Python機械学習プログラミング
各所でいいと言われていたので購入。
機械学習のアルゴリズムを手を動かして学べる良い本だと思います。
腰を据えてやらないと終わらないので、いつ時間を取るか考え中。
30日でできる! OS自作入門
本のとおりにすすめるにはWindows環境が必要だったので積んでいました。
最近、Macでできる環境を作ったので気が向いた時にぼちぼち進めています。
ネットワークはなぜつながるのか
上記のようにつらかったです。
UNIXシェルスクリプト マスターピース132
実用的なシェルスクリプトを集めた本ですが、目次を眺めて個人的に実用的なものが見つからなかったので積んでいます。 (なぜ買ってしまったのか。)
今では見方も変わっているかと思い、目次を眺めてみたらいくつか興味のあるものを見つけたので読んでみようと思います。
定期的に目次を眺めよう…
まとめと今後
今年は、必要なものや興味のあるものを節操なく読んでいたら上記のようになりました。
今のところこのスタイルに大きな問題を感じていないので、来年も節操なく読みたいと思います。
CODE FESTIVAL 2016 Final E - Cookies
問題概要
- りんごさんは1秒で1枚クッキーを焼ける
- りんごさんはA秒かけて今あるクッキーT枚を全て食べることができ、それによって1秒でT枚クッキーを焼けるようになる
- N枚以上のクッキーを最短何秒で焼けるか
部分点解法
N <= 106なので、O(N)かO(N log N)ならOK。
以下のようなDPテーブルを考える。
dp[i]:=i枚のクッキーを丁度焼き終わる、最短の時間。
この際、dp[i]は最大でもiであることがわかる (クッキーを食べずに黙々と焼けばいいので) ため、DPテーブルをdp[i]=iで初期化する。
※公式の解説ではdp[0]=0, それ以外は∞とあったけどそれだと永遠にDPテーブルが更新されないので注意。
クッキーを焼くスピードをj枚/sにして (j枚の時にクッキーを食べて) i枚までクッキーを焼く時、i枚焼くにはdp[j]+A+i/j秒かかる。
従って、DPテーブルは以下のように更新できる。
dp[i] = min(dp[i],dp[j]+i/j)
これを0<=i<=2N (j刻み) , 1<=j<=Nの範囲で回してdp[N]~dp[2N]の最小値を出力すればいい。
オーダーについて自分があとで、見直すようにかなり雑に説明する。
j刻みで回すループ1回の中で、N/j回更新処理が行われている。
それを何度か回すということはN×Σ1/jになるんだけど、
∫1/x = log x でΣ(1/j)は大体log(N)なのでオーダーはN log N。
満点解法
N <= 1012なのでO(N)でもNG。
log(10^12)≒40なので決め打ちして探索っぽい雰囲気がある。
では何を決め打ちするか。
クッキーを何枚食べるか、では調べるのにO(N)かかるし、そもそも食べるのは1回ではないので決め打てない。
クッキーを何回食べるか、ではどうか。
どう考えても、スピードが速くなる場合以外にクッキーを食べることはないし、スピードが速くなる時に必ずクッキーを食べていけば、スピードは以下のように遷移する。
1枚→2枚→4枚→8枚......
つまりクッキーはlog(10^12)回以上食べることはない。
クッキーを食べる回数を決め打ちすることにする。
決め打ちする値が決まった後に考えることは、クッキーを食べる枚数が決まっているときの最適な戦略である。
k回クッキーを食べる時、時間の流れは以下のようになる。
s0秒→A秒 (食べる) →s1秒→ A秒(食べる)→...→sk秒
そうすると、かかる時間はA*k+Σs, 焼きあがる枚数はΠsとなる。
Σsをできるだけ小さくしながらΠsをN以上にしたい。
これに関する最適な解はできるだけsを均等にすること、すなわち、sをNのk乗根にすることである。
僕は直感的に納得できたので証明をしてないけど、相加平均>=相乗平均とか使って証明できると思う。 (完全に適当)
k乗根は整数にならないので天井関数で調整する。
この値をmとし、全てのsをmすると、Πsはk乗根がぴったり整数だった場合を除き、確実にNより大きくなる。
これをΠsがNを下回らない範囲で、m-1に置き換えていき調整する。
- k乗根の導出にlog N
- mとm-1の置き換えにlog N
出力は、各ステップ (食べる回数) で求めた答えの最小値となる。
ソースコード
部分点
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007LL #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; #define MAX_N 2000100 ll N , A; ll dp[MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> A; if (N>=1000000+1) return 0; REP(i,2*N) { dp[i]=i; } FOR(i,1,N) { for( ll j = i; j <= 2*N; j+=i) { dp[j] = min(dp[j], dp[i]+A+j/i); } } ll ans = INF * INF; FOR(i,N,2*N) ans = min(ans, dp[i]); cout << ans << endl; return 0; }
満点
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007LL #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; ll N, A; ll check (ll m, ll eat){ ll cnt = 0; ll num = 1; REP(i,eat) { num*=m; } REP(i,eat) { // *mを*(m-1)に num/=m; num*=m-1; if (num>=N) { cnt+=1; } else { break; } } return cnt; } int main(){ ios::sync_with_stdio(false); cin >> N >> A; ll ans = N; FOR(eat,1,50) { // double lt = 0; double bt=INF*INF; double m = pow(N,1/(double)(eat+1)); ll mi = m; if (m>=mi) mi+=1; ll dec = check(mi, eat+1); //cout << A*eat+mi*(eat+1-dec)+(mi-1)*dec << endl; ans = min(ans, A*eat+mi*(eat+1-dec)+(mi-1)*dec); } cout << ans << endl; return 0; }
Dinic法
ライブラリとして持ってはいたけど、あまり理解していなかったDinic法について学び直したのでメモ。
Dinic法とは
Dinic法は、最大フロー問題を効率的に解くためのアルゴリズムである。
最大フロー問題については、蟻本第二版188ページ参照。
概要
N個のノードのうち、ノードsからノードtへの最大流を求める問題を考える。
エッジはM本あるものとする。
データ構造
Dinic法ではM本のエッジが与えられた時、反対方向に容量0のエッジを貼って初期化する。 これを逆辺と呼ぶ。 エッジの情報は
struct edge {int to, cap, rev}; vector<edge> G[MAX_N];
という形で保持する。
toは行き先のノード、capはエッジの容量、revは逆辺を特定するための情報である。
例えば、e = G[n][m]でeはノードnから伸びているm本目のエッジを表す。
この時、G[e.to][e.rev]はeの逆辺を表す。
処理の流れ
最大フローを求めるアルゴリズムは大雑把にいうと次のような流れで動作する。
- フローを流せるパスを適当に求めて、フローを流す。
- 流したエッジのcapを流した分だけ減らす。
流したエッジの逆辺のcapを流した分だけ増やす。
(capの増えた逆辺は通れるようになる) - 1, 2を流せるパスがなくなるまで繰り返す
これを効率的にやるためにDinic法では幅優先探索 (dfs) と深さ優先探索 (bfs) を使う。
Dinic法の処理の流れを以下に示す。
flowは求めるべき最大フローを示す。 level[t]は幅優先探索で求めたsからtまでの最短距離を示す。
以下、幅優先探索と深さ優先探索での処理について詳しく述べる。
幅優先探索
幅優先探索では始点sから各ノードまでの最短距離を求める。
配列levelの要素を-1で初期化する。
普通に幅優先探索をして、始点sからの最短距離を配列levelに格納する。
この際、(当然だが) cap > 0 && level[to] < 0となるエッジのみを遷移に使用する。
level[t]が-1のままの場合は、フローを流せるエッジが存在しないので終了。
オーダーはO(M)。
幅優先探索で求められるtまでの最短距離level[t]は毎ステップで必ず増加する。
従って、この処理は高々N-1回しか呼ばれない。
深さ優先探索
深さ優先探索では逆辺を含めたcap > 0 && level[to] < level[t]となるエッジを使ったsからtまでのパス (増加パス) を一つ見つけ、その流量を調べる。
そしてエッジを更新する。
この際、調べたエッジには印をつけておく。
あるパスを採用する時、使えなくなるエッジはcapが最小の1本だけである。
そのため、深さ優先探索をもう一度行うとその使えない1本までは同じパスを調べてしまう。
そのような無駄を省くために、調べたエッジに印をつけておく。
この操作を繰り返し、流せなくなったらbfsのステップに戻る。
オーダーはO(NM)。
オーダーに関しては以下が非常にわかりやすかった。
以上から、O(N2 M)で最大流を求めることができる。
実際にはそれより高速に動作することが多いようだ。
追記:
普通に写経しても効果が薄いと思って、pythonに移植した蟻本コードのお墓。
# coding: utf-8 import queue class Dinic: """Implementation of Dinic's Alogorithm""" def __init__(self, v, inf = 1000000007): self.V = v self.inf = inf self.G = [[] for _ in range(v)] self.level = [0 for _ in range(v)] self.iter = [0 for _ in range(v)] def add_edge(self, from_, to, cap): # to: 行き先, cap: 容量, rev: 反対側の辺 self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])}) self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1}) # sからの最短距離をbfsで計算 def bfs(self, s): self.level = [-1 for _ in range(self.V)] self.level[s] = 0; que = queue.Queue() que.put(s) while not que.empty(): v = que.get() for i in range(len(self.G[v])): e = self.G[v][i] if e['cap'] > 0 and self.level[e['to']] < 0: self.level[e['to']] = self.level[v] + 1 que.put(e['to']) # 増加バスをdfsで探す def dfs(self, v, t, f): if v == t: return f for i in range(self.iter[v], len(self.G[v])): self.iter[v] = i e = self.G[v][i] if e['cap'] > 0 and self.level[v] < self.level[e['to']]: d = self.dfs(e['to'], t, min(f, e['cap'])) if d > 0: e['cap'] -= d self.G[e['to']][e['rev']]['cap'] += d return d return 0 def max_flow(self, s, t): flow = 0 while True: self.bfs(s) # bfsで到達不可 if self.level[t] < 0 : return flow self.iter = [0 for _ in range(self.V)] f = self.dfs(s, t, self.inf) while f > 0: flow += f f = self.dfs(s,t, self.inf)
AtCoder Beginner Contest 041 D - 徒競走
問題概要
略
解法
コメント
#define MAX_N 16 int N,M; ll dp[1 << MAX_N]; bool edge[MAX_N][MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M; REP(i, M) { int x, y; cin >> x >> y;x--;y--; edge[x][y] = true; } // dp[mask]:=mask (2進数) が1のノードだけの並び替えパターン数 // 上記の並び替えの一番後ろにまだ使用してないノードを加えることができるかを考える dp[0] = 1; REP (i, 1 << N) { // j+1 bit目が0の時 REP(j,N) if (!( (i >> j) & 1)) { bool isOk = true; // k+1 bit目が1の時 j → k というノードが存在するならアウト REP(k, N) if ( (i >> k) & 1) if (edge[j][k]) isOk = false; // j+1 bit目 を立てた場合の数にプラス if (isOk) dp[i + (1 << j)] += dp[i]; } } cout << dp[int(1 << N)-1] << endl; return 0; }
POJ 3280 Cheapest Palindrome
POJは制約が多すぎる (unordered_mapが使えなかった)
問題概要
- N種類の文字で構成された長さMの文字列Sが与えられる
- この文字列にいくつかの文字を追加、あるいは削除して回文にする
- i番目の文字を追加するには、a_iのコスト、削除するにはb_iのコストがかかる
解法
- abbbbを回分にする時aを追加して、abbbbaとする方法と、aを削除してbbbbとする方法どちらでも可である
- 従って、追加 or 削除はコストの低い方を用いる
- dp[i][j]:=区間[i,j)を回文にするコストとすると
- ある、長さlenの区間について
- dp[i][j+1] = max(dp[i][j+1], dp[i][j]+S[j]のコスト)
- dp[i-1][j] = max(dp[i-1][j], dp[i][j]+S[i-1]のコスト)
- if (S[i-1]==S[j]) dp[i-1][j+1] = max(dp[i-1][j+1],dp[i][j])
- 以上のdpを区間lenが0 ~ M-1の間繰り返す
参考
AtCoder Regular Contest 056 B - 駐車場
問題概要
略
解法
- ある車xに着目する時、あるエッジの両端u,vについて、min(u,v) >= xの時、その道にまだ車が止まっていないため通行可能である
- 通行可能な道をUnion Findでマージし、same(S, x)がtrueとなれば到達可能である
- この制約はxが大きくなるほど厳しくなるため、エッジをmin(u, v)が大きい順にソートし、大きい車から順番に見ていく
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007LL #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; struct UnionFind{ vector<int> parents; vector<int> rank; UnionFind(int n){ parents.resize(n); rank.assign(n, 1); REP(i, n){ parents[i] = i; } } int find(int x){ if(parents[x] == x) return x; return parents[x] = find(parents[x]); } int unite(int x, int y){ x = find(x); y = find(y); if(x == y) return -1; if(rank[x] > rank[y]) parents[y] = x; else{ parents[x] = y; if(rank[x]==rank[y]) rank[y]++; } return 0; } bool same(int x, int y){ return find(x) == find(y); } }; #define MAX_N 200010 int N, M, S; p t[MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M >> S; S--; REP(i,M) { int u,v; cin >> u >> v; u--;v--; t[i].first=min(u,v); t[i].second=max(u,v); } sort(t,t+M,greater<p>()); UnionFind uf(N); int cur=0; vector<int> ans; for (int i = N-1; i >= 0; i--) { while(cur<M) { if(t[cur].first>=i) { uf.unite(t[cur].first, t[cur].second); cur++; } else break; } if (uf.same(S,i)) ans.pb(i); } reverse(all(ans)); for(auto x: ans) { cout << ++x << endl; } return 0; }
