2020/10/31、11/1に開催されたコンテストの感想

AtCoder Regular Contest 107

A

ΣΣΣabc

• ΣaΣbΣcに分解できる
• Σaは等差数列の公式からO(1)

B

1<=a,b,c,d<=Nかつa+b-c-d=Kの(a,b,c,d)の個数

• a+b-(c+d)=K
• Kは負もあるがK=abs(K)としてよい
• 和がxの2数とx+Kの2数の組み合わせの積の総和
• xはx+K<=2Nまで調べれば十分なのでまにあう

C

N*N行列の行同士また列同士は各要素の和がK以下のときのみswapできる。swapを0回以上行って得られる行列は何通りか

• 行と列は独立なので以下行で統一
• 明らかに入れ換えられる行以外にも入れ換えられるケースがありそう
• ある行a,b,cがあってswap(a,b)とswap(a,c)が可能なときswap(b,c)ができなくてもaとのswapを使ってswapできる
• Union-Findぽいのでする
• 入れ換えられる行同士のグループのsizeの階乗すべての積
• もちろん列も同様

D

N要素、総和K、要素は2^-x (0<=x)の多重集合の総数

• 解けず、DPの匂いはしたが
• 要素の再帰的な構造が見えなかった

AtCoder Beginner Contest 181

A

白と黒の服を交互に着る。今日は白、N日後は

• 偶奇
• N%2==0なら白、でなければ黒

B

Ai以上Bi以下の数を1個ずつ黒板に書く操作をN回行うと、黒板の数の和は

• 操作ごとO(1)で処理
• 公式忘れた
• AもBも小さいので累積和使う
• f(a,b)を[a,b)の和として
• [A,B]の和=f(0,B+1)-f(0,A)

C

同一直線上の3点の組み合わせはいくつか

• 制約的に全探索していい
• 3点あって、直線状の判定は
• 点a,b,cとしてa,bの差分dx1,dy1とb,cの差分dx2,dy2をみて
• dx1==dx2 && dy1==dy2ならよくて
• 例えば2==3 && 6==9もokにしたいので
• これが1==1 && 3==3になるように
• dx1とdy1をgcdで割っておくといい
• たぶん0が混じってもいい感じになるはず
• てか平行判定は外積やろがいと（コンテスト後）

D

数字列を並び替えて8の倍数にできるか 数字列に0は含まれない

• 8の倍数判定のときは
• 方法はあるけどめんどい
• 1000は8の倍数なので大事なのは下3
• 下3のパターン全部試して適合できるものがあればok
• 0,8,16,24,...,104,112,...,992
• 0があるような例えばパターン0や400とかは考えない 誤判定の原因になりそう
• 困るのは数字列/パターンが2桁や1桁のとき
• たとえばパターン016は数字列の要素が{1,6}の時しかダメ（余分なものがあるとダメ）
• 桁数も判定時に考慮しないといけない

E

N（奇数）人と自分のN+1人でペアを作る。身長差の総和を最小化したい。ただし、自分のみ身長をいくつかの値にできる。

• ともあれsort
• 自分はどの身長になるべきか
• 全部試す
• 自分が入ってもsortedな必要があるので入る場所は二分探索で定まる
• 自分に関係ないペアの身長差の総和は前計算を使って高速に求められる必要がある
• 二分探索でバグるとは…

F

区間を釘に引っかからないように通過できる円の最大直径は

• 解けず。時間もないし適当に書き始めたのも嘘
• dp[i][上/下]=i番目の釘の[上/下]を通過できるか
• 嘘で、直前の釘以外も考慮しないとダメ
• 正解は短いスキマから閉じていって区間が分断されたときのスキマの広さ

Codeforces Round #681 (Div. 2, based on VK Cup 2019-2020 - Final（過去問）

A

どれかとどれかのgcdは1でなく、どれかがどれかの倍数にならないようにn要素の数列を構築、使える数は1~4n

• デカいほうから使っておけばよさそう
• 4n, 4n-2, 4n-4...

B

bit列を全部0にしたい。操作aと操作bのコストが与えられるので最小コストを求めよ

操作a:1を0にする。1が隣接する限り0にする

操作b:0を1にする

• 0100010の000をどうするか
• 埋めてから一気に0にするか、順番に0にするか
• 前から最適なほうを選べばいい

C

出前だとai（並列処理される）、買いに行くとbi（直列処理される）の時間がかかる。全部入手する最小時間は

• 時間決め打ち二分探索
• 時間内に出前が間に合うなら出前、でなければ買いに行く
• 買いに行く時間の総和が時間に間に合うかで判定

D

非増加な非負整数列と非減少な非負整数列を足して数列Aをつくれるか

• 嘘にはまった
• 全部の要素に対して自分の左の最小要素と自分の右の最小要素の和が自分以上ならOKと書いたらWA
• 正解は前から愚直に非増加整数列をできるだけ大きくとっていって非負のままいられるかの判定

E

Fのほうが解かれてるのでpass

F

数列Aから数列Bを作るとき選ぶindexの組は何通りか

操作：あるindexの要素を消し、その隣どちらかの要素をBに加える

• 解説見てソース読んでやっとAC
• 加える要素は毎回決まっているので左を消すのか右を消すのかの話
• 後で使うのに消すとまずい
• そうでないものはどう消そうが構わない
• 追加する要素の両隣を見て、
• どっちも後で使う->0
• 片方だけ後で使う->ans×1、次へ
• どっちも今後使わない->ans×2、次
• 消すといっても実装上は数列Aから実際に消さなくていい、非自明な感じ