C問題の実装に若干手間取ったのと1か所の考慮漏れにより1WAを食らったことが大きく響いた。解説で示された内容自体は比較的容易に理解できるものだっただけに、本番中にD問題でACを獲得するための勉強が足らず4000位代という結果に終わったのが頗る悔やまれる。
【C問題】
↓問題のページ↓
AtCoder Beginner Contest 332 C - T-shirts
問題文が長めで情報の整理にやや手間取るものの、要は「ロゴ付きのシャツを最低で何着購入する必要があるか」を求める問題である。この答えを\(x\)着とする時、状況の設定から「\(x\)着以上購入すれば十分足り、\(x\)着未満の場合は不足する」と結論付けられる。このような構造に対しては二分探索が非常に有効なので採用することにした。最大で何着購入しなければならないかを考えると、\(N\)日間全てが「競技プログラミングのイベント」の予定である場合に、\(N\)着のロゴ付きシャツが確実に必要となると分かるため、探索範囲の最大値を\(N\)として二分探索を実行すれば答えを導き出すことができるという結論に辿り着く。
解法：
1)入力される文字列\(S\)をランレングス圧縮し、その結果を\(T\)として取得する。
↓
2)探索範囲の下限\(l\)を\(-1\)、上限\(u\)を\(N\)で初期化して二分探索を行う。繰り返し実行の度に \begin{equation} k = \frac{l + u}{2} \end{equation} で求められる\(k\)着だけ購入するものとして、これが十分であれば\(u\)の値を\(k\)に、不足する場合は\(l\)の値を\(k\)に更新する（十分足りているか不足するかの判定方法は下記を参照）。\begin{equation} l + 1 = u \end{equation} となったら繰り返しを終了する。
※足りるか不足するかの判定方法：
\(T\)が\(C_T\)個の成分（それぞれを\(T_i\)と表す）を持つものとする。残りの無地シャツの数\(R_P\)を\(M\)で、残りのロゴ付きシャツの数\(R_D\)を\(k\)で初期化する。
\( i = 1, \dotsc, C_T \)について、\(T_i\)の予定が「なし」の場合、\(R_P\)の値を\(M\)に、\(R_D\)の値を\(k\)に更新する。予定が「競技プログラミングのイベント」の場合、\(T_i\)の連続長の値を\(Q\)とすると、\(R_D\)から\(Q\)を引く。予定が「食事」の場合、同じく\(T_i\)の連続長の値を\(Q\)とすると、\( Q ≤ R_P \)であれば\(R_P\)から\(Q\)を引き、そうでなければ\(R_D\)から\(Q - R_P\)を引くとともに\(R_P\)の値を\(0\)に更新する。この繰り返しの途中で\(R_D < 0\)となった場合は不足し、最後まで\(R_D ≥ 0\)を満たしていれば足りていると判定結果を返す。
↓
3)答えは\(u\)の値そのものであるため、これを出力する。
計算量の考察：
1)で\( \mathcal{O}(N) \)の処理、2)では\(T\)の成分が最大で\(N\)個となること、および二分探索の探索対象範囲が\(N + 2\)であることから\( \mathcal{O}(N\log N) \)の処理を行う。最も重い\( \mathcal{O}(N\log N) \)が全体としての計算量となり、制約で示された\(N\)でも間に合う。
【D問題】
↓問題のページ↓
AtCoder Beginner Contest 332 D - Swapping Puzzle
解き方の方針を全く見いだせなかったため、とりあえず各行および各列の番号を最大で1回選択するものとし、bit全探索を利用する方針で実装したが、入力例4で明らかに出力例とは異なる値を出力したため間違っていたと判明し結局最後まで分からずこの問題に敗北して終わりとなった。
公式解説 の通り、「2つの行または2つの列を入れ替える」という操作を0回以上実施した後の状態は、行番号・列番号それぞれの順列で表すことが可能であるということを理解していればその通りに実装するのみであったため、実際はこけおどしでしかない問題であり、自分の勉強不足だったと結論付けざるを得ない。
※入力例1のように\(H = 4, W = 5\)の場合を例にする。\(A\)の隣り合う2行または2列を入れ替えるという操作を何度か行った後、行番号、列番号それぞれを表す順列\(P, Q\)の中身が \begin{equation} \left( P_1,P_2,P_3,P_4 \right) \end{equation} \begin{equation} \left( Q_1,Q_2,Q_3,Q_4,Q_5\ \right) \end{equation} となっているとして、\( i = 1, \dotsc, 4 \)および\( j = 1, \dotsc, 5 \)について、\begin{equation} B_{ij} \neq A_{P_iQ_j} \end{equation}であるような\(i,j\)が1つでも存在すれば不適な状態、そうでなければ適切な状態であると分かる。
【今後に向けた情報整理】
1)「2つの行または2つの列を入れ替える」という操作を0回以上実施した後の状態は、行番号・列番号それぞれの順列で表すことが可能。
2)最小の順列 \( \left( 1, 2, \dotsc, N \right) \) を \( \left( P_1, P_2, \dotsc, P_N \right) \) へと変えるために必要な、隣接する2つの値を入れ替える操作を実行する最小の回数は、順列の転倒数（定義は以下参照）に等しい。
\( 1 ≤ i < j ≤ N \)および \( P_i > P_j \)を満たす\( \left( i, j \right) \)の組の個数
3)上記の転倒数を求められるよう、 順列ライブラリ を修正。
