AtCoder ABC178 参戦記

AtCoder の ABC178

atcoder.jp

に参加しました。

結果は 62 分全完 (1 WA) 134 分でパフォーマンス2275でした。ここ三回連続黄パフォを出せているので、この調子でがんばっていきたいと思います。

感想

A 問題

(1 - x) でよい。業務でも時々書く。

B 問題

(a * c) or (b * c) or (a * d) or (b * d) のどれかが最大値を与えるので全部実行して max を取る。

C 問題

DP に訴える。各桁を見て行ったときに以下のように状態を割り振れば遷移は簡単に書ける。

• dp[i][0] : (0, 9) もない
• dp[i][1] : 0 がある
• dp[i][2] : 9 がある
• dp[i][3] : 0 も 9 もある

D 問題

これまた DP。dp[i] を s = i のときの個数とすると以下のようになる

• 

E 問題

• y で降順ソート
• 左候補と右候補をトラッキングしながら各点を処理
  • 点と左候補、点と右候補の距離を計算
  • 左候補に対して diff(-x) >= diff(-y) なら左候補を置き換え
  • 右候補に対して diff(x) >= diff(-y) なら右候補を置き換え

典型っぽいので "点群 マンハッタン距離" で検索したくなった。

F 問題

A と B に同じ数値が n 個よりおおくある場合は NG (無証明)。構築は以下のようにして行う

• 数値が入っていないポジションを set で管理
• A にある数値のうち (A での個数 + B での個数) が多い順から処理
  • • A でのポジションの直後から数値を入れられるポジションに B の個数分数値を入れる
• B にしかない数値をあてはめていく