概要 最大全域木を求める． 解法 辺の正負を反転して最小全域木を求める． struct UnionFind{ vector<int> parent, rank; UnionFind(int n) : parent(n,-1), rank(n, 0) { } int find(int x){ if(parent[x] == -1) return x; else return (parent[x] = find(paren</int>…

概要 最小全域木を求める． typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; bool operator< (const Edge &a, const Edge &</edges></edge>…

概要 有向グラフと目標頂点が与えられる． 目標頂点への往復経路が最も大きい頂点を探す． 解法 Dijkstraやるだけ． 復路の計算は与えられたグラフに対してDijkstra法を使えば簡単に求まる． 往路の計算は与えられたグラフの辺を逆向きにしたグラフにDijkstr…

蟻本の問題番号と，問題名の対応が間違ってた． 概要 負閉路検知やるだけ． const int INF = 100000000; typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> </edge>…

概要 無向グラフが与えられるので，他のすべての頂点への距離の平均が最も小さい頂点を探す． 解法 Warshall-Floydやるだけ． const int INF = 100000000; int N, M; int d[310][310]; int c[310]; int main(){ scanf("%d%d", &N, &M); for(int i = 0; i <= …

概要 2種類の集合があって，2つの要素が異なる集合に属しているという情報と，2つの要素が同じ集合に属すかどうか問うクエリが来る． 解法 蟻本の練習問題と同様の考え方を用いる．要素vについて，集合Aに属している事象Avと，集合Bに属している事象Bvを用意…

概要 コストa[i]と評価値s[i]の組の列がある． この中から，N（奇数）個の要素をコストの合計がFを超えないように選び，メディアンを最大化したい． 解法 メディアンはソートしたときの中央値であり，中央の値以外には影響をうけないことを利用する． N = 2K…

概要 100個以下の要素からなる(S[i],F[i])の列がある．(-1000 この列からいくつかの要素を選び，S[i]，F[i]の総和をとる． S[i]の総和とF[i]の総和が0を下回らないという条件のもとで，S[i]とF[i]の総和を最大にする． 解法 S[i]について降順にソート． dp[i…

蟻本の練習問題を消化中 概要 K種類のブロックがあって，i番目のブロックは高さhiであり，ci個だけある．また，ブロックの一部がhiを超えるとまずい． ブロックを積み上げていくとき，到達できる高さの最大はいくつか． 解法 ブロックを高さ制限でソート． d…

7月11日のICPC国内予選にチーム"Takoyaki-man"として参加してました．結果は，4問完答ミスなしで39位でした．事故がなければ予選通ってます． チーム編成 メンバー 学年 役割 備考 僕 大学4回生相当 C以降を解く ぺろぺろキャンディグラフ 後輩A 大学2回生相…

ポスターを作るのに，せっかくだからLaTeXを使おうという気分になって，LaTeX使ってポスター作製していた．（LaTeXを用いたポスターの作成方法はこちらを参照）自分で校閲の真似事をやっているといくつか字下げが行われていない段落を発見した．jarticleなの…

インターンシップも終わって姉の寝顔をこっそり鑑賞しながらTwitterやってたらこんな記事を見つけた．高専はすごいかも知れないが行くのは止めておいたほうがいい - 下林明正のブログ僕は別に高専が大好きというわけではないが，7年間高専に通う（予定）の僕…

一昨日は参議院選挙で，世の中はその話題で持ちきりだった．3月末頃が誕生日の僕は，初めて国政選挙に参加できると楽しみにしていた．（同級生のほとんどは昨年末の衆議院選挙に対して投票権を持っていた．）しかし，悲劇は起きたのである．若干の覚え間違い…

TeX．．．いい響きです．3年ほど前からずっと使えるようになりたかったのですが，触らずにここまで来てしまった．すると，インターン先の先生から「レポート書くとき何使いたい？Word？TeX?」と聞かれたのでつい「TeX使ってみたいです．．．」と言ってしまっ…

概要 論理式が与えられるので，その式を真にするような変数の値の組合せが何通りあるか計算する． ただし，同じ変数は1回しか登場しない． 解法 同じ変数は1回しか登場しないという制限により，式をいくつかの区間（演算）に分けて考えることができる．組合…

永続データ構造とやらが使いたくなったので解いた．でも，正直それ以外の部分で時間を食いまくった． 概要 各ノードに値が与えられている木が与えられる． 2つのノード間の初等的な経路の中でL番目に小さい数を出力するクエリにいっぱい答える． 解法 iwi先…

問題文が「これ木構造だから！木構造だからね！そこんとこよろしく！」と語りかけてくる問題． 概要 N個の星があって，それぞれの星は1つの宇宙船を保有している．ある星aが保有している宇宙船を別の星bに向かわせるとき人を乗せていくことができるが，帰り…

LinkCut木について勉強する機会があったので@iwiwi先生のスライドと，Tarjanの本(邦訳は絶版っぽい．そして原著高いので誰か買ってください)を参考に実装してみた．LinkCut木は，木をパスに分解して木にして，それに含まれるパスをSplay木で管理するというよ…

憧れの「東大男子」を落とす方法・7選 | ハウコレを見てついカッとなってやった． 文句を言われたら削除する． 高専生・・・なんと素敵な響きでしょうか． 将来有望な彼らと一生に一度は付き合ってみたい！と思っている女子も多いはず．そこで今回は，現役高…

情報オリンピック予選の季節ですね．情報オリンピック予選突破を目指して頑張る人達のために，予選の問題の解法に使えそうなアルゴリズム・データ構造・アドバイスを適当にまとめておきます． なし＝やるだけ空欄はうまい説明が思いつかないか，AOJで通して…

この記事はComputer Vision Advent Calendar 2012の12/6の記事兼sakanazensen先輩への誕生日プレゼントとして書かれました． 高専プロコンとは 全国高等専門学校プログラミングコンテスト（ぜんこくこうとうせんもんがっこう─、プロコン）は、高等専門学校連…

この記事はCompetitive Programming Advent Calendar Div2012 12/4の記事として書かれたものです． この記事では僕が高専でやってきた競技プログラミングの活動を淡々と書いたものです．過度な期待はしないでください． アルゴリズム系の話題を読みたかった…

情報交換会とかで説明する時間がなかったので書きます． 実は徳山の解法は久留米高専の劣化コピーを少し改良したもので，まだ久留米高専の解を超える解を出したことはありません; プロコンの決勝後に司会，解説の方の質問に久留米高専の学生が答えていました…

8月末以来かよ．．． 1月,2月 特に何があったか覚えていない．2月はコンフェスの準備をしていた気がするけど，記憶に残っていないということは特に活動していないということなので，反省． 3月 コンフェスで競技部門3位．30分でアルゴリズムを改良して1位を…

渋谷で開催されたNVIDIA CUDA サマーキャンプに参加してきました．部活を卒業した先輩がテスト前ぐらいにつぶやいていたのを見つけての応募． 親戚の家に泊めてもらっています．ついでに，いくつか大学の周辺を見てから帰る予定です． 経過 親戚宅から自転車…

Easyに時間かかりまくった上にFailedSystemTestなうえに，Ratingが100以上下がるというトラウマ回．反省は，「制限ちゃんと見て，オーバーなコード書かないようにしようぜ」．Easyの嘘解法（その時は正解だと思っていた）を書いた後に，Medium開いたら「あれ…

最近プログラミングHaskellを読んでる．（写経している）専門書は持っていても，マンガとかにどうしても気が向いてしまう＋新しいのを買ってしまうので，全部読んだことが少ない．全部読んだのは，"プログラマが知っておくべき97のこと"ぐらい．明らかにお金…

ICPCの国内予選を突破できなかったので悔しくてねむれない．それはともかくとして，とりあえずといたのでメモ程度に． 問題概略 n個の奇数と1個の偶数から構成される配列aがあるよ．配列の中から2つ選んで積をとって配列bの要素にするよ．配列aを求めてちょ…

きました．公式さんはこちらです． http://comfes.windyakin.net/ http://twitter.com/computer_fes概要は公式さんを見ていただくとして，参加記録を書いておきます． 1日目 移動 13時30分に学校に集合，14時出発．準備は滞りなく進み，ほぼ時間通りにバスが…

シュターン-ブロコ木とか，スターン-ブロコット木とか読むらしい．やっぱりアルファベットで書いてある方がかっこいい．AOJ Problem 1208: Rational Irrationals で使ったのはいいものの，なんか忘れそうだったので，備忘録代わりに． 僕の勝手な解釈とかが…