はじめに 2019/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group の参加記です。kazuma, nakano と SleepingDragon として出ました。 コンテスト内容 A を読む、やるだけなので投げる、WAになる 2回目のケースで1回目のテストケース結果提出してた（…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2691 解法 流量1ずつ流していったときの最小費用流のコストのグラフは、下に凸な折れ線グラフになる。 求める値は、このグラフと点 \((M, 0)\) との距離であり、グラフの形からこの距離も…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2202 解法 全長が小さいので DP する。 reach[i][j] := 船 i が位置 j に到達する最短時刻これはあくまでも「到達」時刻であり、その地点を出発できる時刻ではない（門の上下などで停泊す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 解法 こんなの積分するしかないでしょという気分になるので立式する。 とりあえずボロノイ図を考えると、凸多角形領域 \(D\) とその内部の1点に対する問題に帰着できる。 内部の点を …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2569 解法 線分の通り方を n! 通り全探索する。 ある線分を通る時に、その線分で点を鏡写しにしていけば、直線がそれらの線分を貫くかどうか、という問題になる。 この判定は角度（厳密に…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2164 解法 回転して同じものはとりあえず重複して数える。 というのも、もし周期 s の並べ方があったとしたら、回転して同じとみなせるものは s 通りだとわかるからだ。まず、先頭を A に…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343 解法 操作に必要な情報は、 鏡写しの状態になっているか 何回転しているか どこに何が書き込まれたか (WR, CP) 列 or 行の並びはどうなっているか だけなので、各操作に対し O(1) or …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2430 解法 やり方は2通りあるんですが、片方はちょっとメモリが厳しかった（通ったけど）。 メモリが厳しいほう dp[i][j] := i 個目までみて最大長さが j であるときの右端の min と定義。…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341 解法 動的2次元セグ木とかで解けそうだけど、ICPC でデータ構造の問題はチームメイトに投げるため違う解き方をする。 とりあえずソートができるので3次元 -> 2次元になる。 1次元のと…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2172 解法 ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。 これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい（どの問題…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2587 解法 桁DPしようと思ったが、遷移がうまく書けないので困った。 そこでオートマトンをイメージする。 結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 解法 普通のバックトラックで解ける。 バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。 今回なら、文字の種類数が多い方を先に考え…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307 解法 こういうのは確定できるところからさせるもの。 とりあえず一番遠いところは unique に定まるので確定させる。 次は、残ってる d の中で最も大きい値を選ぶ。 こいつは、明らか…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322 解法 今の左端と、上下の区間を持ちながら構文解析を書く。 base の位置は左から見ていって、初めて空白以外が現れた行としてよい。 分数表記のときに余計な space がたくさん入るこ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017 解法 行きの位置、向き、戻りの位置、向きを同時にもって遷移するだけなんだけど、結構めんどくさい。 一番楽なのは DFS で1マスずつ動かしていくのだと思う。 曲がれるタイミングは…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2623 解法 普通にαβ法をメモ化再帰でやるだけ。minimize も maximize も同じ。 dp[v][alpha][beta] := negamax(v, alpha, beta) で最善の選び方をした時の解子供の順番は next_permutation…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646 解法 全探索を考えるところから。 n が小さくで列を愚直に持てるとしたら、次の全探索を考えるはず。 res(l, r, rank) := 区間 [l, r) における勝者の最終順位が rank になるときの最…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2786 解法 Andrew's Monotone Chain を左右からやっていくだけ。 有名な（？）蟻本の実装だと多角形の表現にするために半時計回りにやっているけど、今回はそんなことせずに、上側も下側も…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2690 解法 各頂点について一番遠いところを貪欲に選ぶだけ。 一番遠いところへのパス以外はそこで切って、vector かなんかに突っ込んでおけばよい。 m がでかいけどどう考えても n^2 のオ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743 解法 全探索をちょっとだけ早くするだけ。 n n == 4 のときは、土地を使い切らない方法で最適なものがありうる。 具体的には螺旋っぽく配置するというもの。真ん中がぽっかり開いてる…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2692 解法 包除原理。 チームにしないといけない組は確定で組ませる。 また、チームにしてはいけない組のすべての部分集合に対して、その集合に含まれる組は確定でチームを組ませるとする…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1628&lang=jp 解説 実装するだけ。 仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。 a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。 それを今の値に足し…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2604\ 解法 変数は 10 個しかないので、それぞれの変数を何桁にするか最初に全探索する。 すると、変数の桁ごとに、どの桁と対応するかを決定できる。 対応する集合を union find 木かなに…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1388 解法 m つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。 よく考えると、次数が 2 以下の頂点…