ACPC 2019 Day3 B: パフェ
1 like215 views
2019/9/20 会津大学競技プログラミング合宿 Day3 (北大セット) B 問題 ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
ACPC 2019 Day3 B: パフェ
- 1. B : テトリス 会津合宿 2019 Day 3 原案: rsk0315 解説: rodea 問題文: rsk0315 解答: tsutaj, rsk0315, rodea
- 2. ? 問題概要 与えられた 4 つのテトロミノから 3 つ選んで、 ? 個の盤面について、 盤面全体にブロックが置かれた状態にできるか判定する。ただし、 ?ブロック同士が重なってはいけない。 ?与えられたテトロミノを回転させてはいけない。 ?各 ? (1 ≤ ? ≤ 4) について、テトロミノ ?? を二回以上使ってはいけない。 ?テトロミノの各ブロックは盤面の外に出てはいけない。 制約 ?1 ≤ ? ≤ 105 ?各盤面は 4 × 10 マスで表され、 ‘#’ はちょうど 28 個存在する。
- 3. ? 解法 盤面が与えられるたびに 4 つのテトロミノから 3 つ選んで判定する、 という処理をしていくと、TLE してしまいそう。 どうにか高速化できないか考える。
- 4. ? 解法 次のように前処理すると間に合う。 事前に 4 つのテトロミノから 3 つ選んで、どのような盤面だと盤面全体 にブロックが置かれた状態にできるかをすべて求めておく。 set<vector<string>> exist; とし、 exist.emplace(条件を満たす盤面); としていくイメージ。 その後、与えられた盤面について、exist.count() を用いて高速に判定 していく。
- 5. ? Writer 解と統計情報 ?tsutaj: 116 行 (C++) ?rsk0315: 83 行 (C++) ?rsk0315_nohash: 105 行 (C++) ?rodea: 130 行 (C++) Acceptance / Submission ?65.79 % (25 / 38) First Acceptance ?On-site: ACPC_sakenichia (14:44) ?On-line: face4 (21:03)