2020/12/13、19に開催されたコンテストの感想

めんどくて書いてなかったけど2021年には持ち越さないぞ2020大晦日スペシャル

AtCoder Beginner Contest 185

A

A~D問題の数から開催できる旧ABCの回数を求めよ

• min(A,B,C,D)

B

スマホの充電をシミュレーションして充電切れが発生するか答えてください

• やるだけ。0未満になったり容量超えたりしないように注意
• こういうバグはサンプル試す中で気づいた
• なにも言われなくても気にするようにしたいですね

C

L[m]の棒を12個に分ける方法の数

• L-1個の切れ目候補から11個選ぶので二項係数求める問題
• オーバーフローに気を付けないとこわい

D

任意の固定幅のハンコのみを使ってマス目をはみ出さないように塗るとき、最小押下回数

• 塗る連続したマスの最小幅のハンコが最適
• あとは塗るマスの長さとハンコ幅の商切り上げの和
• 最小幅を0にしないように注意
• 番兵を置くとうまくいく

E

文字列A,Bに対しペナ1で削除が可能 同じ長さに揃え、一致しない箇所の数×1ペナ、最小ペナはいくつか

• 動的計画法の5文字がよぎる
• LCSっぽい?空気感は似てるけど遷移は違うね
• DP[i][j]=Aのi文字目とBのj文字目までの最小ペナ
• DP[i+1][j+1]はDP[i][j]とAi,Bjの一致によって定まる
• DP[i+1][j]とかはDP[i][j]+1でいい
• 後者の遷移に気付くまで時間がかかった

F

range add queryのxorバージョンを処理してください

• BITを貼る
• ACLのやつを貼ろうとしてめんどいになった。タイムロス

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

A

トラックの積載量と荷物の重さが与えられる。いくつ載せられるか

• 積載量を重さで割って切り捨てる（当然、C++の整数型なら自動で切り捨てられる）

B

グリッドにAij個のブロックがあり、全部同じ数にするには何個取ればいいか

• 二次元グリッドの必要性は皆無なので一次元で受け取っていい
• 揃える先はmin(Aij)
• それをまず求めて、それとの差を取る

C

N以下の正整数に10進法でも8進法でも7を含まない数はいくつか

• 制約的に全部試して問題なさそう
• 進数変換は知らんが、変換すればto_stringで文字列に変換してfind関数で7があるか判定可能
• 8進変換はX mod 8を答えの文字列に足して8で割るを繰り返す
• 本当はreverseする必要があるけど今は関係ない

D

i<jの全ペアのabs(Ai-Aj)の総和

• 各Aiに対し式中の左にくる回数と右に来る回数は簡単にわかる
• 左にx個右にy個あるならans+=Ai*(y-x)
• あ sortしないとね
• 考察順がひどいのでちゃんと整理
• 全てのi<jについてAi>Ajならabsがいらなくて式を分解できる
• 降順sort
• Ai-Ajの総和だけど、AiとAjを分けるとどの数も何回か足され、引かれる
• その回数は左にある要素数、右にある要素数から決まる
• あとはそれを求めて足す

E

円形に並ぶN個の椅子がありS番目にいる。K個回る操作何回で0番に着くか、または永遠に着かないか

• Kx+S=0 mod Nなるxを求めよという問題
• x=-S/K mod N
• ググるっきゃない
• 非素数逆元のためのオイラーのφ関数とか使って解く
• うまくいかないケースがあるけど先にgcdで全部割っておくとうまくいった

F

障害物のある二次元グリッドで、飛車が二手で移動可能なマスの総数

• 解説AC.
• 各列で見て足していく
• それまでに障害物が出現した場所についての区間クエリが欲しくなる
• セグ木の匂いを感じる
• うるせえ平方分割で通す
• なんかあわない
• 一行目一列目の障害物の存在を忘れていた。そらばぐるわ
• 時間内に通せる人強いなぁ