この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の16日目の記事です。 データ構造の話です。 地区予選の過去問を解いているときに、以下のような問題を見つけました。 【問題…

インストール 最新版はhttp://orgmode.org/ja/で確認する wget http://orgmode.org/org-8.2.tar.gz tar -zxf org-8.2.tar.gzhttp://d.hatena.ne.jp/buzztaiki/20100201/1265031994を参考にしてorg-table.elを修正する *** lisp/org-table.el 2013-10-01 11:0…

前回のSRMでレッドコーダーになりました！ レッドコーダーな人達というのはそうそうたる人々で、ずっと憧れていたので仲間に入ることが出来て非常に嬉しいです。 グラフを見るとここ半年くらい妙に上がり調子なのでキープできるか非常に不安ですが、出来るだ…

[twitter:@titleReplaceBot] 概要 「○○のタイトルの一部を△△に変えると××」という形式のハッシュタグに対して、 データベースに保存された○○のタイトルの一部を△△に変えて15分おきにつぶやく。 詳細 タイトルデータベース 現在、{アニメ,小説,ゲーム,映画}の…

http://acm.timus.ru/contest.aspx?id=153 ロシアの怖い合宿で出題されたセットらしい。チームで解いたが10問あって2完という怖いセットだった。 本番ではC,Iを解いて後でA,Fを解いた。 A - Complex Root 問題 x^n = a+bi x^m = c+di を満たすような複素数x…

japljさんが幾何の問題集をVirtual Arenaでセットしていたので、最近ちょこちょこやっている。 まだ途中だけど、とりあえずまとめる。 http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=1178&active=status AOJ 2045 - Turn Polygons 多角形の中にある多…

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=381 A - Balanced Number 問題 [x,y]に含まれるbalanced numberの数を求めよ。 Balanced Numberとは、ある桁を中心として他の桁の値を重さと見たときのモーメントが…

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=520 A - Alice and Bob B - Break the Chocolate 問題 N*M*Kの板？チョコレートがある。 これを1*1*1のピースに分けたい。 分け方には手を使う方法とナイフを使う方…

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=518 Binary Matrix 問題 要素が1,0のみのN×M行列が与えられる。 隣接する要素同士をスワップするという操作のみ認められる。 ただし、1行目とN行目のスワップや、１…

Strongly Connected Chemicals 問題 (V=L∪R,E)な2部グラフGが与えられる。 L'⊂L,R'⊂R（|L'|>=1, |R'|>=1）なL',R'を選んで、 全ての(i,j)∈L'×R'の間に辺があるようにしたい。 このとき|L'|+|R'|の和の最大値を求めよ。 制約 1 ≤ m, n ≤ 50 解法 L'=Φもしくは…

3/11~3/13に立命館で行われたプロコン合宿に行って来ました。 主にコンテストの反省書きます。 1日目 チーム名はevisuto、チームメイトはevimaさんとtokoharuさん 結果は3位 感想 強いお二人と組めてとても楽しかった。 びっくりするくらい楽しかった。 Fは…

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=362 A - 4609 - An Industrial Spy 篩＆全探索という日本のICPCによくありそうな問題 B - 4610 - Common Subexpression Elimination 問題 二分木を縮約する。 文字…

昨日発表してきました 疲れた↓頻出順（適当） この研究のポイント（困難な点、自分がやった点、工夫点、新規性）は？ （参考文献を見て）本当にちゃんと調べた？ 何がしたかったの？（目的が分からん、目的と手法があってない、目的と評価方法があってない）…

再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。 再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。 典型的…

フィボナッチ数をまとめてみた。 「AOJ2372 - IkaNumber」の解説も入ってる。https://www.dropbox.com/s/6nx2f9htpfyvnkv/fibonacci.pdf競技プログラミングと関係のありそうなフィボナッチ数の話題があったら教えて下さい。とりあえずProject Eulerまわりを…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 ICPC Asia Tokyo 2012 Problem I 問題 図1のようにN個の単語を配置する。 1行にはスペースを含めW文字入る。 入力としては、i番目の単語の長さがxiとして与えられる。 以下良い配置の条件 入…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 頂点数Mの多角形領域の中に，N個のシェルターがある。 多角形領域の中に等確率で位置すると考えたとき、最も近いシェルターまでの距離の期待値を求めよ。 制約 M,N -1000 解法 あるシェ…

現実逃避の続き http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2211 問題 略 解法 答えについて二分探索。 答えをk以下に出来るかどうかを判定したい。 猫と餌入れはx座標でソートしておく。 解説スライドの通り dp[i] = i番目に餌を置いた時に…

現実逃避 問題 n個の椅子がある円卓がある。 ここに8人の王子が座る。 ただし、王子が隣り合ったり、ちょうど向かい合ったりしてはいけない。 このとき、何通りの座り方があるか。 回転したり反転したりして同じになるものも区別して数える。 制約 答えは10^…

しゃくとり法 POJ 2566 - Bound Found 問題 要素数nの数列aが与えられる。 各クエリでtが与えられるので、連続する部分列の中で、和の絶対値がtに最も近いものを求めよ。 制約 n ai t クエリの数やデータセットの数の制約は書いてない 解法 しゃくとり法で各…