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

ゆらのふなびと

競プロ, Python, C++

会津合宿2016Day2 会津セット A~L 解いた

会津合宿

振り返り。(2016/9/22 とりあえずA-Gだけup。Lまでは解く予定)

問題: http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day2

解説: (リンクに飛ぶと右側にばーっと出てくる)

www.slideshare.net

A: Plants

植物が植えられたマスに何回肥料がまかれたかをカウントするだけ。tは要らない。

gist.github.com

B : Potatoes

N_C_K全列挙→aの大きい方から貪欲に配る。

gist.github.com

C : Unhappy Class

シンプルなDP。(曜日, 時限)を時間軸で1次元化すると書きやすかった。

あんハピが見たくなった。

gist.github.com

D : One-Time Path

有向グラフがあるが、どの辺もある決められた時刻にしか通過できない。頂点1からスタートし最終的に頂点Nにいなければならないとき、頂点Nに着く時間の最大値を求めよ。

頂点で待つことは自由なので、頂点Nの一歩手前の頂点vまで行って、辺vNが通れるようになるまで待てばよい。そこで頂点1から各頂点vに到達できる最短の時間d_vをダイクストラで求め、d_v <= cost(e_vN) なる各頂点vについて cost(e_vN) のmaxを取ればよい。面白かった。

gist.github.com

E : Graph Making

参加記に書いた方法でほげった。実験したらなんかわかってきて面白かった。

pakapa104.hatenablog.com

gist.github.com

F : Curling Puzzle

感動。

2次元のマス目上にいくつかの石がある。石をカーリングのように滑らせたとき、ゴールのマスにストーンのどれかを止めることができるか判定せよ。

実はH > 1 && W > 1 && 石の個数N >= 3 のとき、常に答えはyes。snukeさんの動画がわかりやすい。

その他の場合は状態数が少ないので適当にメモ化再帰で解ける。

ストーンをある方向にはじく操作はマスをどんどんswapしていく操作であるということに気づくと実装が楽だった。

gist.github.com

G : Star

正N/K角形の面積を求めよという問題。

NとKは互いに素という制約なので必ず外側の頂点はN個になる。すると「∨」←こんなのをN個繰り返した図形になるので、1つの「∨」が求まればよい。円周上の点と内側の交点を求めれば外積で面積が求まる。

意外と簡単な幾何で解けて好き。

コードを見ると本番での混乱がうかがえる(ライブラリが間違っていると思い込んでいろいろ試していた)(結局ライブラリは正しかったことを後々納得した)

gist.github.com

H

Coming soon...