読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AOJ

AOJ Sort II - Minimum Cost Sort

AOJ

学校の別のコースの人の授業でやった問題らしいので軽い気持ちでやってみたけど, 全然わからなかった… 問題 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge 解法 まず基本的な考察をします。例えば 10 7 8 9 といった数列を考えると, 最…

AOJ 2190:Angel Stairs

AOJ

問題 Angel Stairs | Aizu Online Judge 解法 後ろからたどっていけば良いです。 例えば, ひとつ目の入力例を見ていきましょう。C E D# F G A C E F Gまずそれぞれの配列を逆さまにします。A G F D# E C G F E Cまず G を作る必要があります。スタートが A …

AOJ 2546: Chocolate

AOJ

問題 Chocolate | Aizu Online Judge 解法 まず, チョコレートを取る順番は上の行から順番で良いとわかります。これは 2 行目以降のチョコレートは必ずそれより上にあるチョコレートを取らないと取ることが出来ないことからわかります。ということで, 一番上…

AOJ 1208 Rational Irrationals

AOJ

前のこどふぉの問題を解こうとしたら Stern-Brocot 木というのを考えるらしいので AOJ で練習してみました。 Spaghetti Source - Stern-Brocot 木既約分数を探索するのに都合が良さそうですね。 問題 Rational Irrationals | Aizu Online Judge 解法 Stern B…

AOJ 2335: 10歳の動的計画

AOJ

大学受験のとき使った参考書を引っ張ってきました。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335 解法 まず寄り道回数のうち左に移動する回数を i 回として横移動と縦移動を分けます。そして, 「横移動の場合の数」と「縦移動の場…

AOJ 0270 Modular Query

AOJ

問題 Modular Query | Aizu Online Judge 解法 配列 c をソートしておき, 各クエリ q について, c[n-1] から余りを求めていくと考えます。このとき, c[i] を q で割った余りが p であるとすると, c[i]-p から c[i] までの数字は, 余りが p よりも小さいこと…

AOJ 2255 6/2(1+2)

AOJ

9だと思います。 問題 6/2(1+2) | Aizu Online Judge 解法 今までのように返す値を単なるintみたいな感じにしても上手くいかないのでsetを返すようにする。式を分析するときはそれぞれのoperatorがどの順番で使われるのかをnext_permutationで調べていく(た…

AOJ 1155 Problem C: 如何に汝を満足せしめむ? いざ数え上げむ…

AOJ

題名長いっすね。構文解析の練習です。だいぶ慣れてきた。 問題 How can I satisfy thee? Let me count the ways... | Aizu Online Judge 解法 formulaにしたがって構文解析する。 typedef string::const_iterator State; int formula(State& begin, int s);…

模擬国内予選 E.サイコロスタンプ

AOJ

ACM-ICPCの模擬国内予選に参加しました。チーム(@haraduka_, @garasubo, @mayoko_)としてはA, B, Dの3問を解いてなるほど。といった感じでした。以前1年分やった感じでは4完はできると思っていたのでちょっと悲しいです。しかも僕が担当して解かれた問題は一…

AOJ 2401 恒等式

AOJ

デバッグに非常に時間がかかったけどなんとか出来た。 問題 Equation | Aizu Online Judge 解法 問題文中に最高のヒントが書いてあるのでそれを元に関数を作る。 <equation> ::= <formula> "=" <formula> <formula> ::= "T" | "F" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | </formula></formula></formula></equation>…

AOJ 109 Smart Calculator

AOJ

今日残りの国内予選の幾何問題を見てて察したのですが,幾何問題は面倒すぎて多分「普通だったら特に練習しなくても解けるし難しかったら解けない」という気がするので構文解析の技術を身につけるほうが良さそうな気がしてきました。ということではい。 問題 …

AOJ 1183 鎖中経路

AOJ

幾何むずい。 問題 鎖中経路 | Aizu Online Judge 解法 問題文中でご丁寧に示してあるように,最適解では円の交点を通りながらゴールに向かうことになります。円の交点を求める公式はこちらを参考にしました。 円と円の交点を求める - Shogo Computing Labora…

AOJ 1189 つながれた風船

AOJ

目からウロコおじさんだった。 問題 つながれた風船 | Aizu Online Judge 解法 風船のx, yの座標(X, Y)を一つに決めると,z^2の値としてありえるのはmin()(i = 0〜n-1)となります(はそれぞれ杭に繋がれた糸の長さ,杭のxy座標)。これはに関して上に凸な関数で…

AOJ 1188 階層民主主義

AOJ

ICPCに参加することになりました。よろしくお願いします。ということで少し練習しようかな,と。2013年 会津大会 の問題を解いてみましたが,問題Cと問題Dは無事正解できました。多分AとBはできると思うのでこの年だと(自分だけなら)4完ですかね。 問題 階層民…