AtCoder Beginner Contest 178 感想
奇跡のカンスト
総括
結果がすべてじゃ！60位2400パフォサイコー！！！！
Problem A
xは0か1である。そっちじゃないほうを出力
考えたこと
- まあやればいい
- x-1でいけるわ
- 1 xor xとか使っても行けそう まあいいや
ひとこと
not xでもいいね。テストケースが10個ぐらいあるけど重複ケースが入っててランダム出力を振るい落としてるみたい。
Problem B
の範囲で
を最大化せよ
考えたこと
- 負数があるから面倒
- 負数になりうるけど、でも絶対値が大きいものが有利
- どうせ端っこでしょ
- 4パターン試せばいいや
Problem C
要素が0～9、長さNの数列のうち0と9を両方1個以上含むものはいくつか
考えたこと
- 包除というやつのにおい
- 全パターン-0がない-9がない+0も9もない
- 全パターン=10N
- なんかがない=(10-(なんかの種類数))N
- 10N-9N-9N+8N
ひとこと
包除じゃない方針で行けそうじゃない？をしてしまい、ものすごいごちゃついた。おとなしくやろうな
Problem D
全ての要素が3以上の数列で総和がSのものはいくつか
考えたこと
- 最大長はざっくりS/3ぐらい
- DPっぽい
- dp[i][j] = i項からなる総和jの数列の個数 とおけそう
- dp[i][j] = dp[i-1][x]たちをうまいこと足したやつっぽい
- 1項足すと総和が3以上増える
- dp[i-1][0]からdp[i-1][j-3]の和が欲しい
- 遷移時全てのjについて毎回Σx:0~j-3 dp[i-1][x]を求めるのは愚か
- jの下から更新していくので、累積和的にやるとdpテーブル埋めと平行して計算できる
- あとはiを回してdp[i][S]の総和
ひとこと
解説の遷移、数学的かつ賢いね
Problem E
2次元座標上のN個の点のすべてのペアのうち最長のマンハッタン距離は？
考えたこと
- パッとはいい解法が思いつかない
- 問題文がシンプル過ぎる
- 既出に賭けて検索
- HIT
- max(max(x+y)-min(x+y), max(x-y)-min(x-y))
- いつもの座標45度回転ね
Problem F
ソート済みの数列A,Bがある。Bを並び替えてAi=BiとなるiをなくせるBがあれば構築せよ
考えたこと
- むずい 厳密な証明をして通せる問題ではなさそう
- 既出な気もするけど検索ワードが思いつかない
- ありそうな並び替え方を全部試してダメなら諦める戦略で通ることを祈るか
- なんか、ある程度ずらすといけそう
- AAAAAABBB AAAAAABBB みたいのはどうやってもかぶるのでダメ
- サンプル見た感じ、半分ぐらいずらすと大抵うまくいきそう
- リバースも戦略の一つとして考えられる
- じゃあそれでいくか
- 長さNにたいしてN/2ずらし(N+1)/2ずらし、reverseを検証していく
- 通るんかい
- 通るんかい
- 通るんかい
- 60位かよ しかもノーペナだよ
- reverse消すとWA。おお…
- (N+1)/2は消しても大丈夫だった。
- 嘘くさ。
結果
https://atcoder.jp/contests/abc178/standings?watching=pointN
https://atcoder.jp/users/pointN/history/share/abc178
ひょえ～
