ABC参加記 299
結果
A~Eの5完でした。
Fについてはコンテスト後に解説をみて解きました。
先週に続いてDDosの影響によってコンテストはUnratedに。運営さんがんばです。
A
キーワード
特になし
変数定義：
l, r := 二つの'|'のSにおけるインデックス( l < r )
x := '*'のSにおけるインデックス
アルゴリズム：
(x > l and x < r) ならば"in"、そうでなければ"out"
提出
B - Trick Taking
キーワード
map
概要
どちらの勝者判定法を利用しても、勝者となれるのは各色で最大の値を持つプレイヤーのみです。よって、keyに各色を、valueにkeyの色における最大のカードの値とその持ち主を表すpairとしたmapで必要な情報を管理する。
変数定義：
colour := カードの色
mp[colour] := (card_value, card_player)
アルゴリズム：
i = 1..Nに対して以下を繰り返す
- if(
R_{i} C_{i} C_{i} R_{i}
最後に,Tがあればmp[T].card_playerを、なければmp[
提出
ポイント(memo)
-
C_{i} <= 10^9
C - Dango
キーワード
逆順による単純化
概要
右から串がささっている団子については計算が簡単にできるため、Sを逆にして同様に計算することで左から串が刺さっているパターンも計算できる。
変数定義：
cnt := 現在の団子のストリーク数(初期値 0)
maxv := 団子の最大レベル(初期値 0)
アルゴリズム：
-
i = 1..Nに対して以下を繰り返す
- if (
S_{i}
else { maxv = max(maxv, cnt); cnt = 0}
- if (
-
Sを反転して, 1を繰り返す
求める解: maxv
提出
D - Find by Query
キーワード
二部探索,インタラクティブ
概要
たまに出るインタラクティブな問題。まだ慣れてなくて、出るとちょっとドキっとします(もしかしてこれが恋・・・?)
よって、
上記より、二部探索によってpがいる範囲を限定することができる。
変数定義：
l := 探索範囲の左端のインデックス( 初期値:1 )
r := 探索範囲の右端のインデックス( 初期値:N )
アルゴリズム:
- while( l+1 < r ) として以下を繰り返す
- if (
S_{mid}=1
else mid = l
- if (
求める解: l
提出
E - Nearest Black Vertex
キーワード
BFS(幅優先探索)
概要
コンテスト中の思考の流れは以下のようだった。
1.i = 1..Kに対して、条件をカバーするために１つ頂点を黒く塗らなきゃいけない
2.でも,「下手な頂点」をぬると条件を満たせなくなってしまう
3.「下手な頂点」とは、その頂点の各頂点への最短距離が、条件によって指定された距離より小さいもの
4.各頂点への最短距離は事前に計算できるため、下手な頂点かの判定は各頂点でO(N)でできる
5.i = 1..Kに対して「下手な頂点ではない頂点」から、最短距離が
変数定義:
d[i][j] := 頂点iから頂点jへの最短距離
is_ok[i] := 頂点iが「塗れる頂点(= 下手な頂点ではない)」である( 初期値：全要素 true)
coloured[i] := 頂点iが塗られているか( 初期値: 全要素 0)
アルゴリズム:
- d[i][j]を各頂点を始点としたBFS(幅優先探索)によって求める
- i = 1..Nに対して以下を繰り返す
- j = 1..Kにおいて if ( d[i][
p_{j} d_{j}
- j = 1..Kにおいて if ( d[i][
- j = 1..Kに対して以下を繰り返す
- i = 1..Nにおいて if ( d[i][
p_{j} d_{j}
- i = 1..Nにおいて if ( d[i][
- if ( sum(cloured) == 0 ) coloured[0] = 1
求める解: coloured
ポイント(memo)
- 最初の提出時にステップ4の処理を忘れてしまい、「1個以上の頂点が黒で塗られている」という条件を満たせていないケースが出てしまった。(反省)
- d[i][j] >
d_{p_{j}} p_{j} p_{j}
提出
F - Square Subsequence
後で書く
Discussion