Virtual Arenaで唐突に参加者募って練習した。 参加してくださった方ありがとうございます。 実装は比較的軽く教育的で良問だらけだった。
d[i] + e(i,j) >= d[j] というような形の式が何個か制約として与えられたとき、d[s]=0としてd[k]の最大値を求めましょうという話
FlickrやPanoramioといった画像投稿サイトには位置情報付きの画像が大量にアップロードされている。 この情報を分析することでどこで多くの写真が撮影されているかなどが分かる。 さらに画像に付けられたタグをテキストマイニングすることでその場所がどのよ…
初めてUSACOを解いたけどGold難しい。 問題文をよく読みたい。
ishikadoさんのチームの練習会がVirtual Arenaで開かれていたので勝手に参加させていただいた
いい感じの難易度だった
問題 0~9の数字が書かれたk個のダイアルがある鍵を考える。 連続するダイアルを同じ方向に同じ数だけ回す動作を１手とする。 このときダイアルを初期状態sから目標状態tにする手数を求めよ。 制約 1 解法 まず回す順番は関係がないので左から数字を合わせて…
問題 ２枚ずつのM種類のカードN(=2M)枚で１人神経衰弱をする。 今までに開けたカード全てを記憶出来るとき、ミスマッチする回数の期待値を求めよ。 制約 2 解法 カードを１列に並べたものをイメージして、左から順に開けていく。 今開けようとしているカード…
2月と3月にAOJ100問解くことを目標にした。 途中から何となくSRMも認めることに。 結果 AOJ:110問 SRM:15問 その他:71問（Live Archive,Codeforces） 計195問 となった。 AOJだけで100問いけた。 4月15日に応用情報技術者試験があるので過去問はお休みします…
問題 N種類のコインを使ってm円のお釣りを支払う。 違う種類のコインなら1つの操作で支払うことが出来る。 このとき操作の最小回数を求めよ。 制約 N M 解法 1回の操作での支払い方は2^N通りある。 2^N種類のコインがある場合の普通のお釣りDPをすればいい。…
問題 略 解法 文字列を引数とした再帰による構文解析を実装するのが楽。 優先順位が低い方から文字列を見る（同じ優先順位なら同時）（左結合なら右から、右結合なら左から）。 全体が括弧でくくられる式が来たら括弧をはずす。 ソース vector<vector<char> > g; vector<bool> t</bool></vector<char>…
5819 - Alphabet Soup 5820 - Coin Collecting 5821 - Cybercrime Donut Investigation 5822 - Distributing Ballot Boxes 問題 町がN個あり、各町は人口がa[i]人である。 B個の投票箱があり、それを各町に割り当てる。 各町における１つの投票箱に割り当て…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=397 4944 - Fair Division 問題 金額pをn人で払う。それぞれの人について出せる最大金額a[i]が与えられる。 払う金額の差の最大が最小になるように、n人が払う金額…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333 問題 略 解法 入力（a[i]とする）を降順でソートする。 a[i]までの合計をsum[i]とする。 答えを、 (a[n-1]まで全て使うときの解) + (a[n-2]まで全て使い、a[n-1]は使わないときの解) + ... +…
5983 - MAGRID 問題 R×Cのフィールドを左上から右下までいくことを考える（右または下にのみ移動可能）。 スタートするとき、ある値のパワーを持っている。 ある場所でのフィールドの数字をSとする。 S>0のときSだけパワーを得る。 S パワーが0以下になって…
前置き OpenCV 2 プログラミングブック OpenCV 2.2/2.3対応作者: OpenCV 2 プログラミングブック制作チーム出版社/メーカー: マイナビ発売日: 2011/12/27メディア: 単行本（ソフトカバー）購入: 2人 クリック: 61回この商品を含むブログ (9件) を見る昨年末…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2028 問題 １人用ゲームをする。 カードを表す数列が与えられるので、カードを円状に並べることを考える。 1. あるカードを選んで、そのカードを時計回りで次のカードの上に被せる。 2. このとき…
LiveArchive http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=395 解説 http://cepc10.ii.uni.wroc.pl/solutions.html 4973 - Ardenia 4974 - Beasts 4975 - Casting Spells 問題 文字列が与えられるので、その部分…
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408 4882 - Parenthesis 問題 括弧と足し算と掛け算からなる文が入力されるので、いらない括弧をはずせ。 解法 構文解析して、掛け算のオペランドが足し算のときだ…
応用代数学 群論面白い。 A3と同じでレポートの解答がアップされるのでそれで勉強すればいい。 教科書が指定されているが、何故この教科書が指定されているのか意味が分からない（授業では群論しか扱わないくせに群論の部分が少ない）。 http://siva.cc.hiro…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308 問題 ライツアウトで解法があるかどうか調べる。 普通のライツアウトはある点を押すとその点とマンハッタン距離１の点が反転するが、この問題ではその点とマンハッタン距離dの点が反転する。…
ICPC2010アジア予選の問題で、 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308 というものがあった。 普通のライツアウトはある点を押すとその点とマンハッタン距離１の点が反転するが、この問題ではその点とマンハッタン距離dの点が反転す…
OCaml演習 初めてOCamlを触った。 というか関数型プログラミング自体Scheme以来なわけで苦労した。 しかし実験資料が割と丁寧でそこまでつまづくことなくできた。 （SKIコンビネータと与えられた型を持つような関数の定義は思いっきりつまづいたが） インタ…
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1269 問題 n, kが与えられるので、nを異なる素数k個の和で表すときの表し方の数を求めよ。 ただし、順番を入れ替えただけのものは同じと考える。 解法 DP。 重複が許されないので、普通に考えると…
問題 車のレースをする。 １台の車だけを考える。 n個のチェックポイントでタイヤを交換するかしないか選ぶことができる。 ここで、n個目のチェックポイントがゴールである。 タイヤを交換した場所からの距離をxとすると、xからx+1まで走るのにかかる時間は…
valarrayは演算子がいろいろ定義されていて３次元幾何を扱うとき便利なのだが、手元では上手く動くのにオンラインジャッジではWAだったりREだったりすることがあった。 何故そうなってしまうのか色々試したり調べたりした結果、 「大きさが違うvalarrayにval…
最近パソコンを購入したので、何を買ってどれくらいの費用がかかったのかメモしておく。 本体 OS : Windows 7 Home Premium 64bit CPU : Corei7-2700K CPUファン : LGA 1155用 CPU FAN メモリ : 4GB×2 (DDR3 SDRAM PC3-10600) HDD : 1TB SATAIII 7200rpm マ…
11/3(木) 資料を読んでもどうにも分からなかったので、先生に歪み処理をどうすればいいのか聞き大体理解する。 11/4(金) 歪み処理の実装をする。 成功。 今までとは比べ物にならないほどうまく取得してくれて感動する。 11/10(木) レポートを半分くらい書く…
問題 さいころ27個を図のように並べる。このとき、合わさる面の数字同士の和は7になるようにする。 また、それを上から見たときの数字と前から見たときの数字が入力として与えられる。 ただし入力の数字が0ならばその位置の数字は何でもいい。 考えられる全…
問題 三角形の頂点の座標が与えられる。 三角形に図のように内接する３つの円の半径をそれぞれ求めよ。
