PCK
時系列順に行きます/\_/\
つらつらと今年のPCK の事を記します.
問題文 : 鉄道路線
問題 : ザ・スクエアーズ
本戦出場チームP07 『Cmiz56』で後輩くんと出場します. 単位とるよ～～～
問題文 :平面上に与えられた$N$ 個の点から, ちょうど$k$ 個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成せよ. ただし, $N$ 個の点の座標を与えられた後, 質問として凸多角形の角の個数$k$ がいくつか与えられる.$N \…
7 完だよ～～. 一時期3 位になったし嬉しかったが, vector 使えなくて8 落とすって許されないですね...解法はおおざっぱに書きます(詳しく書くのはつらぽよ)
問題 : ダジャレ※Active Learning Studio にあがっているテストケースはvalid なものになっていました(確認済).
問題文 : 絵柄の一致
問題 : 魔方陣
問題文 : はじめてのロボット
問題文 : 宇宙人のきまぐれメッセージ解法 : 6 つの接続可能性をすべてのマスについて試すO(6^(W*H)) 通りの探索と, それが終わったあとに接続関係が適切であるかをWF で確かめるO((W*H)^3)を掛け合わせてO(6^(W*H)*(W*H)^3) という絶望的な最悪計算量だが,…
問題文 : 図画工作解法 :$dp[i][j][k]$ : $i$ で表される道具の集合をを$j$ 日目に$k$ 個まで道具をかって実現することができるか, として事前にDP を行う.それで, 袋から完成状態へDP の結果をコストとする辺を貼り, 流量を$N$ とした最小費用流を行う.
問題文 : Blur解法 : 基本的に枝刈り探索である. ・矛盾する状態(そこにインクを落とすと明らかに歪なインクの塊が残ってしまう)になったら探索をやめる ・インクの数を確定することが出来たら無闇にインクを落とすのをやめる ・探索に失敗したインクの集合…
問題文 : Stoning Fortune解法 : 線分の交差判定・交点判定がきちんとできていれば, 面積を求めて条件に合わせて出力を行う問題. ライブラリを頼りました.
問題文 : 最後の扉解法 : つながる三角形を列挙したら, 強連結成分分解を行うだけ. JOI のAdvertisement という問題と全く一緒になります. 問題のつながる三角形の列挙ですが, 長方形と辺が重なる or 三角形の頂点が長方形にはいる or 長方形の頂点が三角形…
結果 : ooo--o---- 4完 31点 3WAくらい. 9位でなみだらしい＞＜感想 : デバッグに2時間位費やした点以外はだいたい良かったと思う. 5は思いついていた解法の計算量を測り間違えて書かずに残念なことをしてしまった. 4も簡単な幾何だったので, ちゃんと読もう…
問題文 : スコーン配達計画(pdf注意, 28枚目-30枚目)解法 : 部分列 mod Mの最大値を求める問題である. 区間[i, j]の和 mod Mをすべて確かめると, 累積和を用いてもO(N^2)となってしまうため、セグメント木を使ってこの計算を高速化する. i jについてはループ…
問題文 : カード解法 :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]) …
問題文 : サージェント・ライアン解法 : 最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる. ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.コード : #include <cstdio> #include <cstring> #include <vector> #define INF</vector></cstring></cstdio>…
問題文 : 会津の埋蔵金解法 : f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う. 状態空間が5*10^4になるため, 楽にメモ化再帰ができる. …
問題文 : 人生ゲーム解法 : 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>…
問題文 : 自転車ダイエット解法 : ケーキ屋の数が少ないので, 訪れたケーキ屋の集合および今いる頂点を持ったダイクストラを行う. "一度訪れたケーキ屋に再び訪れることができない"ということに注意.コード : #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cstring></cstdio>…
問題文 : パチモンクリーチャー解法 : 最初に選ぶパチクリを決めると, 次に選ぶパチクリが決まっていく. このパチクリ同士の関係を線で結んでいくと, 必然的にグラフになっている. ゆえに, この問題はグラフの最短経路を求める問題に帰着できる. ここでは, …
問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…
問題文 : ばらばら饅頭解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).その後は, ナップサック問題を解く要領でメモ化再帰を行う. このように, 配列に値を持たせて行うDPをm…
問題文 : AOJ 0247解法 : 基本的には深さ優先探索を行う. ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う. 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めてい…
