パフォーマンス:1607相当
レーティング:1818→1799 (-19) :(
#AtCoder #ABC485
atcoder.jp/users/mjtai/...
パフォーマンス:1607相当
レーティング:1818→1799 (-19) :(
#AtCoder #ABC485
atcoder.jp/users/mjtai/...
5完でした
A: 符号のみに着目して比較
B: 行または列でxが揃っている場所を探す
C: 連続する色の距離をまとめて計算
D: 中央の区間について左端を定めたときの最小区間を尺取り法で求め、最大区間と比較
E: 各頂点について最大2色の最小コストを保持する幅優先探索
5完でした
A: 符号のみに着目して比較
B: 行または列でxが揃っている場所を探す
C: 連続する色の距離をまとめて計算
D: 中央の区間について左端を定めたときの最小区間を尺取り法で求め、最大区間と比較
E: 各頂点について最大2色の最小コストを保持する幅優先探索
A 珍しく掛け算が使える
B 難しすぎるのでサンプルエスパー
C 座標をstd::setに入れて1色ずつ削除求解追加
D しゃくとり法(30分もかかった)
E 辺を頂点として見たらTLE、辺が多すぎたので同じ辺をO(1)回しか見ないように改造
A 珍しく掛け算が使える
B 難しすぎるのでサンプルエスパー
C 座標をstd::setに入れて1色ずつ削除求解追加
D しゃくとり法(30分もかかった)
E 辺を頂点として見たらTLE、辺が多すぎたので同じ辺をO(1)回しか見ないように改造
パフォーマンス:1571相当
レーティング:1242→1279 (+37) :)
#AtCoder #ABC485 atcoder.jp/users/doDayl...
あったまった
パフォーマンス:1571相当
レーティング:1242→1279 (+37) :)
#AtCoder #ABC485 atcoder.jp/users/doDayl...
あったまった
E:何度となく見た各頂点2回ずつやるやつ
F:使う個数とコストをキーにDPする。DPテーブルを使い回してc降順に商品を処理する。各商品を処理する際はいったん橋の使用回数が c_i - 1 だとしてコストを求めると、橋使用回数 [c_{i+1}, c_i - 1]の範囲の答えが求められる
E:何度となく見た各頂点2回ずつやるやつ
F:使う個数とコストをキーにDPする。DPテーブルを使い回してc降順に商品を処理する。各商品を処理する際はいったん橋の使用回数が c_i - 1 だとしてコストを求めると、橋使用回数 [c_{i+1}, c_i - 1]の範囲の答えが求められる
A a*b>0
B 横全部xか縦全部xか
C 近所の同じ色を飛ばしたいのでランレングス圧縮
D インデックスを雑にsetに突っ込んで「少なくともこのインデックスまでは必要」を区切り更新しながら確認
E 似たようなの解けずに放置してるから今回も解けないんでしょうね
F jの大きい順にしてDPの添字を有料の商品の個数分ずらしていけばDP配列を使い回せそうだけどまとまらず
A a*b>0
B 横全部xか縦全部xか
C 近所の同じ色を飛ばしたいのでランレングス圧縮
D インデックスを雑にsetに突っ込んで「少なくともこのインデックスまでは必要」を区切り更新しながら確認
E 似たようなの解けずに放置してるから今回も解けないんでしょうね
F jの大きい順にしてDPの添字を有料の商品の個数分ずらしていけばDP配列を使い回せそうだけどまとまらず
A問題は !(a..=b).contains(&0)
B問題は縦と横をそれぞれチェックするだけ
なんだけど、s.iter().position(...).unwrap_or(...) が引数を先に評価することを知らなくてなかなかサンプルが通らず、16分以上溶かす
C問題は苦手なタイプの問題
サンプル1を見ると規則性が見えたので、そのまま提出して通る
D問題はDP
「dp[i個目の部分文字列][出現した文字のフラグ]=そこまでの答え」としたらなんか通った
過去に似たようなのを解いた事があって、すぐ思い出せたのが良かった
A問題は !(a..=b).contains(&0)
B問題は縦と横をそれぞれチェックするだけ
なんだけど、s.iter().position(...).unwrap_or(...) が引数を先に評価することを知らなくてなかなかサンプルが通らず、16分以上溶かす
C問題は苦手なタイプの問題
サンプル1を見ると規則性が見えたので、そのまま提出して通る
D問題はDP
「dp[i個目の部分文字列][出現した文字のフラグ]=そこまでの答え」としたらなんか通った
過去に似たようなのを解いた事があって、すぐ思い出せたのが良かった
C run-length圧縮するとわかりやすい
D ややこしいがA,B,Cそれぞれ出現数を累積和して、二分探索すればほしい位置がわかる。基本は最も左の点を決め打ちすると、真ん中の区分がABCを含んでいるか?を確かめる感じ。ABCを含まないパターンの方を確かめて全パターンから引く。
E 解けない... BFSやDijkstraを単純にやろうとすると色が多すぎる。気持ち的にはある点から次の点に行く時は、前の辺の色と同じでなければいいので情報を圧縮してもてそうだけどそれは何ですか?( 配列に入れてソートして上位を見ようとしたけど壊れた )
C run-length圧縮するとわかりやすい
D ややこしいがA,B,Cそれぞれ出現数を累積和して、二分探索すればほしい位置がわかる。基本は最も左の点を決め打ちすると、真ん中の区分がABCを含んでいるか?を確かめる感じ。ABCを含まないパターンの方を確かめて全パターンから引く。
E 解けない... BFSやDijkstraを単純にやろうとすると色が多すぎる。気持ち的にはある点から次の点に行く時は、前の辺の色と同じでなければいいので情報を圧縮してもてそうだけどそれは何ですか?( 配列に入れてソートして上位を見ようとしたけど壊れた )
ABCDE(3) 5完 3ペナ
ESCAPEできずに泥の沼
A:掛けて正か?
B:縦か横にXが続くのが正解
C:近い色TOP2を持って置いて、違う法との距離を採用。右と左で一回ずつ。
D:DP[i文字目まで見た][左からjブロック目][見つけた{A,B,C}の集合]で見ていく。端っこに気をつけてりゃ何とかなる。
E:各点ごとにステップ数と通ってきた橋の色を2番目まで管理。1番目は自分以外の色、2番目は1番目の色を通ってダイクストラ。
1番目と2番目が同じ時とかこまごまとした考慮漏れであえなく3ペナ
(続く)
ABCDE(3) 5完 3ペナ
ESCAPEできずに泥の沼
A:掛けて正か?
B:縦か横にXが続くのが正解
C:近い色TOP2を持って置いて、違う法との距離を採用。右と左で一回ずつ。
D:DP[i文字目まで見た][左からjブロック目][見つけた{A,B,C}の集合]で見ていく。端っこに気をつけてりゃ何とかなる。
E:各点ごとにステップ数と通ってきた橋の色を2番目まで管理。1番目は自分以外の色、2番目は1番目の色を通ってダイクストラ。
1番目と2番目が同じ時とかこまごまとした考慮漏れであえなく3ペナ
(続く)
パフォーマンス:1215相当
レーティング:1694→1654 (-40) :(
#AtCoder #ABC485 atcoder.jp/users/kobosh...
パフォーマンス:1215相当
レーティング:1694→1654 (-40) :(
#AtCoder #ABC485 atcoder.jp/users/kobosh...