東京工業大学プログラミングコンテスト2019
A. Next TTPC
はい
B. okyoech
sed
C. XOR Filling
貪欲ぽく
D. 素数取りゲーム
- $O(N^2)$ 愚直書いたら通るでしょ。見るの素数だけだし
- 微妙に間に合わない
- 分からないので埋め込み
メモ:
-
D: isprimeの配列を持っておいて、2を引いても素数であり続ける回数を求める
— %20｜1953 (+31) (@henkoudekimasu) August 31, 2019想定は偶奇性を使った貪欲らしい。「素数の差」「素数の和」はほとんど必ず偶数なの忘れないようにしたい
E. N法陣
-
剰余を取ったものを並べればよい
0321 1032 2103 3210とか
00000 11111 22222 33333 44444 -
同じ列同士での交換はある $2$ 行にしか影響しない
例:
00004 11111 22222 33333 44440 - そんな感じでやればできる
- https://atcoder.jp/contests/ttpc2019/submissions/7224168
F. Road Construction
- Kruskal ぽく貪欲？ → 嘘っぽい
- 要件を強連結成分分解する？ → してどうなる
- あっ 誤読 (要件は $w \to x$ と $y \to z$ のふたつだけ)
- それぞれ独立に移動する / 途中のある区間が重なる で場合わけする典型
- 各点で $w, x, y, z$ との距離を持ち、そこから最適に $x, z$ の両方へ移動するときのコスト、$w, y$ の両方から移動してくるときのコストをいい感じにやればよい
- https://atcoder.jp/contests/ttpc2019/submissions/7224908
メモ:
- 誤読したままでも解けるのかな？ $Q$ 個の要件 $s_i \to t_i$ ($i \lt Q$) が与えられるのですべて繋がないとだめな場合
- こういうときはまず各点 Dijkstra して、その和を初期値にして再度 Dijkstra すればよい。一般に $k$ 点でこれをやるときは合流の順序の全探索が必要で $2^k - 1$ 回の Dijkstra が必要そう。Bellman Ford とかをしてもどうせ現在の状態を持つ必要があって $2^k - 1$ はかかる
-
Fのs_i < t_iは虹色にして動かしてほしかった
— 衛藤渚 (@eto_nagisa) August 31, 2019これ気付いてなかった
メモ
- 遅刻参加したのでぜんぜん解けず