Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ

AOJ 2382 - King Slime

問題文 : King Slime解いている人数が少ない問題はなんかドキドキする(小並)

AOJ 2170 - Marked Ancestor (ふたたび)

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

AOJ 2207 - Consistet Unit System

問題文 : 無矛盾な単位系

AOJ 0273 - Cats Going Straight II

解法 :双対グラフを作ってbfs すれば良い... が, グラフ構築バグりまくってます. 悲しい. (まだWA...) 朝にバグ取ります...コード : int main() { int N, M; while (scanf("%d %d", &N, &M) && N){ vector<Point> P(N); vector<int> to[128]; bool exist[128][128] = {0}</int></point>…

多角形に対する点の内外判定

問題文 : Polygon-Point Containment

AOJ 0283 - Study Session

問題文勉強会

AOJ 2510 - Twin Book Report

問題文 : 双子の読書感想文

AOJ 0132 - Jigsaw Puzzle

問題文 : ジグソーパズル

AOJ 2369 - CatChecker

問題文 : CatChecker概要 : 文字列$s$ が次のBNF に従っているか判定せよ.<cat> := "" | 'm' + <cat> + 'e' + <cat> + 'w'$1 \leqq |s| \leqq 500$</cat></cat></cat>

AOJ 1302 - Twenty Questions

問題文 : Twenty Questions概要 :長さ$m $ のビット列が$n$ 個ある. これらを一意に識別するために必要なビット数はいくらか? ただし, あるビットの情報を得た後に次の戦略を考えても良い.$1 \leqq m \leqq 11,\ 1 \leqq n \leqq 128$

AOJ 1176 - Planning Rolling Blackouts

問題文 : 輪番停電計画解法 :$dp[sy][sx][gy][gx] := sy \leqq y \leqq gy,\ sx \leqq x \leqq gx$ を満たす区間でのグループの数の最大値と, 供給力の最大値として, メモ化再帰を行うと楽. 列 or 行を降りていき, 分割が不可能な域に達したらimpossible を…

AOJ 0198, 0147, 0122, 0177

AOJ

AOJ 0198ものすごくめんどくさそうだと思っていたが実装に気をつければそうでもなかった. おなじ色の面をみつけて, まわりの4 面を回転させて一致するかを見ればOK. #include <cstdio> #include <string> using namespace std; int rot[6][4] = {{2, 4, 3, 1}, {2, 0, 3, 5},</string></cstdio>…

AOJ 0236 - Alien Messages

問題文 : 宇宙人のきまぐれメッセージ解法 : 6 つの接続可能性をすべてのマスについて試すO(6^(W*H)) 通りの探索と, それが終わったあとに接続関係が適切であるかをWF で確かめるO((W*H)^3)を掛け合わせてO(6^(W*H)*(W*H)^3) という絶望的な最悪計算量だが,…

AOJ 0247 - Arts and Crafts

問題文 : 図画工作解法 :$dp[i][j][k]$ : $i$ で表される道具の集合をを$j$ 日目に$k$ 個まで道具をかって実現することができるか, として事前にDP を行う.それで, 袋から完成状態へDP の結果をコストとする辺を貼り, 流量を$N$ とした最小費用流を行う.

AOJ 2457 - Adhoc Translation

問題文 : Adhoc Translation解法 : これがA 問題ってやべえなあ... 辞書に登録されている単語とネットで見た単語の間に, それぞれ編集距離をコストとした辺を張る. ネットで見た単語の数 ≦ 辞書に登録されている単語の数で, かならずネットで見た単語の数の…

AOJ 0091 - Blur

問題文 : Blur解法 : 基本的に枝刈り探索である. ・矛盾する状態(そこにインクを落とすと明らかに歪なインクの塊が残ってしまう)になったら探索をやめる ・インクの数を確定することが出来たら無闇にインクを落とすのをやめる ・探索に失敗したインクの集合…

AOJ 2142 - Bitwise Kingdom

問題文 : Bitwise Kingdom解法 : $n$ bit 中$k$ bit が$1$ の市民の人数は$_{n}\text{C}_{k}$ 人である. よって, $_{n}\text{C}_{k} \geqq m$ となるまで$m$ を減らす. あとは, 先頭に$1$ を入れたときに自分より速い組み合わせが幾つあるかをたどりながら$0…

AOJ 0187 - Stoning Fortune

問題文 : Stoning Fortune解法 : 線分の交差判定・交点判定がきちんとできていれば, 面積を求めて条件に合わせて出力を行う問題. ライブラリを頼りました.

AOJ 0237 - The Last Door

問題文 : 最後の扉解法 : つながる三角形を列挙したら, 強連結成分分解を行うだけ. JOI のAdvertisement という問題と全く一緒になります. 問題のつながる三角形の列挙ですが, 長方形と辺が重なる or 三角形の頂点が長方形にはいる or 長方形の頂点が三角形…

RUPC Day2 I - One

問題文 : One解法 :放物線の長さは, で求まる. (ここで, とおいた.)交点を列挙してこの関数を適用していけば良い. 誤差に気をつけて計算すべし...コード : #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; const long double EPS =</algorithm></vector></cmath></cstring></cstdio>…

AOJ 2269 - Traveling Salesman Problem

問題 : 巡回セールスマン問題解法 : 与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる. また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成で…

AOJ 1505 - Dungeon

問題文 : Dungeon (I)解法 : クエリでの求める距離fs_iと, スタートからの最短路についてソートし, BITで数え上げを行うと O(N log N)時間でこの問題を解くことが出来る. クエリや最短路は, 数に対し範囲が大きいので座標圧縮を行うと管理が楽になると考えら…

ファレイ数列のいろいろ

JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.・ファレイ数列とは? 約分された分数を昇順に並べた一群の数列であり、正の整数 n に対して、n に対応する (または、属する、深さn…

Matrix-chain multiplication problem

問題文 : n個の行列の連鎖 が与えられたとき、スカラー乗算の回数が最小になるように積A1A2A3...Anを完全に括弧付ける問題を連鎖行列積問題(matrix-chain multiplication problem)という。n個の行列について、行列Aiの次元が与えられたとき、積A1A2...Anの計…

AOJ 2333 - My friends are small

問題文 : ぼくの友達は小さい解法 : 友達を重さでソートし, "使わない友達"を決めると, いくつまでの重量の組み合わせをいれるかを決めることが出来る. この組み合わせを求める部分は, 典型的なナップサック問題を解くDPで求めることが出来る. よって、O(NW)…

AOJ 0553 - Dungeon

問題文 : ダンジョン解法 : 各階で回復出来る量を記録しながら, 実際にダンジョンを潜っていく. 体力が負になってしまった場合, 最も回復出来る地点で回復する.体力をセグメント木として持っておき, 区間に加算するクエリと区間の最大値を求めるクエリを実装…

AOJ 2412 - Village

問題文 : 村解法 : Rによってブロック分けをする. 近傍の8ブロックを1つのグループとみなして, このグループの数を幅優先探索で求める. setを使っているので, O(NlogN)時間で探索を終えることが出来る.コード : #include <cstdio> #include <cmath> #include <set> using namespa</set></cmath></cstdio>…

AOJ 2312 - Magical Girl Sayaka-chan

問題文 : 魔法少女さやかちゃん解法 : 問題文で示されている円環が直線だと考えると, ある音符とある音符の間は、昇順になっていることが望ましい. そこで、始点を音程のうちもっとも小さいもの, 終点を音程のうちもっとも大きいものとし, 始点->終点 にいく…

AOJ 2431 - House Moving

問題文 : 引越し解法 : 荷物を動かすために使う体力を最小化する、ということは 動かさない荷物の重量を最大化する、ということと等しい. ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.荷物の重さをkとし, dp[k] -> …

AOJ 0145 - Cards

問題文 : カード解法 :dp(l, r) -> 区間(l, r)のカードを併合するために必要な最小コストとすると, l番目のカードが最も上に, r番目のカードが最も下になるのは明らかなのでdp(l, r) = min(dp(l, r), dp(l, i) + dp(i+1, r) + a[l] * b[i] * a[i+1] * b[r]) …

AOJ 0235 - Sergeant Rian

問題文 : サージェント・ライアン解法 : 最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる. ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.コード : #include <cstdio> #include <cstring> #include <vector> #define INF</vector></cstring></cstdio>…

AOJ 0234 - Aizu Buried Treasure

問題文 : 会津の埋蔵金解法 : f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う. 状態空間が5*10^4になるため, 楽にメモ化再帰ができる. …

AOJ 0232 - Life Game

問題文 : 人生ゲーム解法 : dp(i, j) -> 場所iにいてj円を持っている確率, とし動的計画法を行う. int型にキャストして表示することに注意.コード : #include <cstdio> #include <cstring> #include <algorithm> typedef struct { int dx; int money; } State; using namespace std; int </algorithm></cstring></cstdio>…

AOJ 0224 - Bicycle Diet

問題文 : 自転車ダイエット解法 : ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う. "一度訪れたケーキ屋に再び訪れることができない"ということに注意.コード : #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cstring></cstdio>…

AOJ 1077 - The Great Summer Contest

問題文 : The Great Summer Contest解法 : 2つのペアをグループ化することが出来るので, 2つのペアをグループ化する. 4番目のタイプのコンテストは, 3つあると1 ~ 3番目のコンテストを1回ずつ開くのと同義になるので0回, 1回, 2回開く場合を考えて貪欲的にコ…

AOJ 0214 - Autumnal Illumination

問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…

AOJ 0246 - Bara-Bara Manju

問題文 : ばらばら饅頭解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).その後は, ナップサック問題を解く要領でメモ化再帰を行う. このように, 配列に値を持たせて行うDPをm…

AOJ 0247 - Ice Maze

問題文 : AOJ 0247解法 : 基本的には深さ優先探索を行う. ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う. 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めてい…