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

Lilliput Steps

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

PCK2013 本選 (問題の部)

PCK

時系列順に行きます/\_/\

PCK2013 本選

PCK

つらつらと今年のPCK の事を記します.

AOJ 0275 - Railroad

問題文 : 鉄道路線

AOJ 0210 - The Squares

PCK

問題 : ザ・スクエアーズ

PCK 2013 本戦

本戦出場チームP07 『Cmiz56』で後輩くんと出場します. 単位とるよ~~~

PCK 2013 予選問9 - ハッピーエンド問題

問題文 :平面上に与えられた$N$ 個の点から, ちょうど$k$ 個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成せよ. ただし, $N$ 個の点の座標を与えられた後, 質問として凸多角形の角の個数$k$ がいくつか与えられる.$N \…

PCK 2013 予選

PCK

7 完だよ~~. 一時期3 位になったし嬉しかったが, vector 使えなくて8 落とすって許されないですね...解法はおおざっぱに書きます(詳しく書くのはつらぽよ)

PCK 2011 本選 - ダジャレ

問題 : ダジャレ※Active Learning Studio にあがっているテストケースはvalid なものになっていました(確認済).

PCK 2011 本選 - 絵柄の一致

PCK

問題文 : 絵柄の一致

PCK 2011 本選 - 魔方陣

問題 : 魔方陣

PCK 2011 本選 - はじめてのロボット

PCK

問題文 : はじめてのロボット

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 0091 - Blur

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

AOJ 0187 - Stoning Fortune

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

AOJ 0237 - The Last Door

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

パソコン甲子園2012 本選

PCK

結果 : ooo--o---- 4完 31点 3WAくらい. 9位でなみだらしい><感想 : デバッグに2時間位費やした点以外はだいたい良かったと思う. 5は思いついていた解法の計算量を測り間違えて書かずに残念なことをしてしまった. 4も簡単な幾何だったので, ちゃんと読もう…

PCK-2012 問9 - スコーン配達計画

問題文 : スコーン配達計画(pdf注意, 28枚目-30枚目)解法 : 部分列 mod Mの最大値を求める問題である. 区間[i, j]の和 mod Mをすべて確かめると, 累積和を用いてもO(N^2)となってしまうため、セグメント木を使ってこの計算を高速化する. i jについてはループ…

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 0215 - Pachimon Creature

問題文 : パチモンクリーチャー解法 : 最初に選ぶパチクリを決めると, 次に選ぶパチクリが決まっていく. このパチクリ同士の関係を線で結んでいくと, 必然的にグラフになっている. ゆえに, この問題はグラフの最短経路を求める問題に帰着できる. ここでは, …

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を増やすという事を行う. 下界から決めてい…