2023-07-18

AtCoder Beginner Contest 310に参加した

競プロアルゴAtCoder

ABC310の参加記．

7月15日に開催されたfreee プログラミングコンテスト2023（AtCoder Beginner Contest 310）に参加した．ABCDEの5完で541位，復帰後はじめてレートが上がった．

A - Order Something Else

問題文

定価 $P$ 円の商品があり，定価で買うか，割引券を使って $Q$ 円で買う代わりに他の商品を追加で買うかの2種類の選択肢がある．他の商品は $N$ 種類あって商品 $i$ の値段が $D_i$ 円であるとき，支払う金額を最小化する問題．

割引券を使う場合は最も安い商品を選べばよく，そもそも定価で買ったほうが安い場合は割引券を使う必要がない．よって ${\rm min}(P, Q+D_{\rm min})$ が答え．

提出：https://atcoder.jp/contests/abc310/submissions/43582896

B - Strictly Superior

問題文

$N$ 個の要素からなる数列 $P=(P_i)$ および集合の列 $F=(F_i)$ が与えられるので，ある条件を満たすような $1\leq i,j\leq N$ が存在するかを判定する問題．

制約が小さいので愚直に条件をチェックするだけだが，条件の内容がやっかいで実装が大変だった．条件の形が「AかつBかつC」のような形になっているので，「Aでない場合はcontinueして次のループへ移動する」という実装にすると比較的楽……と思いきや，Aの否定を考えるのが面倒．「任意の○について△」の否定は「ある○が存在して△でない」になることなどを頭の片隅に呼び出しつつ，頑張った．

提出：https://atcoder.jp/contests/abc310/submissions/43590208

C - Reversible

問題文

英小文字からなる文字列が $N$ 個与えられる．文字列を逆順に読んで一致するものを区別しないとき，異なる文字列は何個あるか？　という問題．

文字列を順に走査しながら，すでに出現した文字列の集合を更新していく．文字列 $S$ が登場したとき， $S$ だけではなく $S$ を逆から読んだ文字列も集合に追加することにすれば，最終的に集合の要素数の半分が答えになる．

ただし，上のアルゴリズムは回文があるときに壊れるので，回文がきたときには回文にならないように適当な文字（英小文字以外ならなんでもいい）を末尾に挿入してから集合に放り込む．

提出：https://atcoder.jp/contests/abc310/submissions/43592997

D - Peaceful Teams

問題文

区別のつく $N$ 人を区別できない $T$ チームに分ける方法を答える問題．ただし，「相性の悪い」ペアが $M$ 組あり，各ペアについて，2人は別のチームに入れなければならない．

制約が $1\leq T\leq N\leq 10$ と小さいので全探索ができそう．ざっくり状態数を見積もると， $N$ 人それぞれに対してどのチームに入れるかが $T$ 通りあるから大体 $N^T$ 通りとなって，最大で $10^{10}$ 程度になる？　実行時間制限に間に合わないじゃんと一瞬思うが，チームは区別しないので実際には $N^T/T!$ 程度にしかならないことに気づく．結局全探索で良さそう．

「何人目まで決めたか」と「チーム割り当て」を状態に持ちながらDFSをすればよいが，重複をせずに数え上げるのが少し面倒．実装の便宜上チームに番号を割り当てたいが，重複があってはいけないので「まだ誰もいないチームに新たに人を割り当てるときには，まだ使われていない番号のうち最小となるように付番する」ことに気をつける．

提出：https://atcoder.jp/contests/abc310/submissions/43602429

E - NAND repeatedly

問題文

$0$ と $1$ からなる数列 $A=(A_i)$ が与えられるので，区間 $[l,r)$ に対して $A_l,\cdots, A_{r-1}$ の累積NANDを計算したものを，すべての $l,r$ の組について足し合わせたものを求める問題．ただしNANDは結合則を満たさないので，計算は左から行うとする．

愚直に計算すると $\Omega (N^2)$ かかってしまうので高速化する方法を考える．よく考えると，区間NANDを計算していく過程で，次の値は直前の値だけで決まる．よって，

${\rm dp}[i][j]$ ： $i$ 番目の要素までみたとき，区間 $[l, i]$ の累積NANDの値が $j$ であるような $l$ の個数

というDPテーブルを更新していくことができ，最終的な答えは

\sum_i {\rm dp}[i][1]

となる．

$j$ のとりうる値は $0$ と $1$ しかないので状態数は $O(N)$ ，遷移は $O(1)$ なので全体として計算量は $O(N)$ になって間に合う．

提出：https://atcoder.jp/contests/abc310/submissions/43617977