【AtCoder】ABC178参加記

競プロが久々になってしまいましたが参加してきました。全完84分+2ペナでした。

以下コンテスト中の思考

A - Not

https://atcoder.jp/contests/abc178/tasks/abc178_a

xor 1で答えになりそうだけどミスっても嫌なので素直に場合分けしました。

B - Product Max

https://atcoder.jp/contests/abc178/tasks/abc178_b

正負で場合分け色々するのも良いんですが、最大は端点になるはずなので、

ac, ad, bc, bdを計算して最大を出力すると楽だと思います。

C - Ubiquity

https://atcoder.jp/contests/abc178/tasks/abc178_c

ぱっと見るとまず包除原理が思い浮かび、0が無い、9が無い、どちらも無いを計算したら答えを計算できるような気がします。が、突然不安になって、今0, 9どちらもない、0が無い、9が無い、両方あるを状態に持ってDPしました。

dp[i+1][3] = dp[i][3]*10 + dp[i][1] + dp[i][2]
dp[i+1][2] = dp[i][2]*9 + dp[i][0]
dp[i+1][1] = dp[i][1]*9 + dp[i][0]
dp[i+1][0] = dp[i][0]*8

D - Redistribution

https://atcoder.jp/contests/abc178/tasks/abc178_d

項数が決まっていて、総和がsである数列の数は○と|を並び替えるよくある重複組合せになるので、項数を全探索した。

項数がi項の場合はsから3*i引いて上記の問題を解けばよくて、せいぜい1000項しかないので大丈夫

E - Dist Max

https://atcoder.jp/contests/abc178/tasks/abc178_e

マンハッタン距離といえばx, y = x-y, x+y

後は回転後の座標差の大きい方を選ぶと答え

F - Contrast

https://atcoder.jp/contests/abc178/tasks/abc178_f

反対から埋めれば真ん中らへんで1個被るから調整すればいい？と思うものの順位表からやたらペナ貰ってる人が多いことからもうちょっと複雑なんじゃないかと考える。

とりあえず同じ数字がn個超えてたら駄目。

ソートされてるのでなんかずらしたら行けそう？と思うもののそこからその方針で行けず。

A, Bの数字をあわせて大きい方からn個の数字を取って並べてA, Bにもう一回戻すと、残りの数字は適当に埋めれば良さそうだと考える。

もちろん、足が出る事があるので、その場合はソートされていることから埋まっていくなら回転させながらやれば良さそうだと思って両端キュー使ってぐるぐる回しながらかぶらないように埋めました。証明はちゃんとはしてないけどまあ合ってそうだとは思った（しそれが思いつくならずらすとかぶらない範囲を全部の数字で調べて共通範囲求めれば良かったねという話になってしまうね）

提出一覧

All Submissions - AtCoder Beginner Contest 178

感想

久々の黄パフォうれしい

Fなんとか実装しきれたけどもうちょっと考察詰めても良かったかも