ABC345挑戦記(C問題)

↓問題のページ↓

AtCoder Beginner Contest 345 C - One Time Swap

※本記事は0-indexedを前提として記載する。

 

<内容の振り返り・解法>

方針はすぐに思い浮かんだものの、C++の言語仕様を知らなかったために80分近く無駄に時間を失い、低いパフォーマンスに終わった。

単純に\(i\)と\(j\)を全探索するのでは\( \mathcal{O}(N^2) \)の処理となり、\(N\)が最大で\(10^6\)まで達する問題であることからTLEとなってしまうため工夫して高速化が必要となる。

\(0 ≤ i ≤ N -1\)なる\(i\)を1つ決めた時、\(i < j\)なる\(j\)の選び方は、全部で\( (N-1-i) \)通りだけある。公式解説の通り、全ての\( (i,j) \)の組について、\(S_i\)と\(S_j\)が異なるのならば、この\( (N-1-i) \)通りは全て元の文字列\(S\)とは異なる文字列を創り出す\( (i,j) \)の選び方となる。\(i < j\)かつ\(S_i\)と\(S_j\)が等しいような\(j\)が\(d\)通りある場合、元の文字列\(S\)とは異なる文字列を創り出す\( (i,j) \)の選び方は、\( (N-1-i-d) \)通りとなる。このように、それぞれの\(i\)に対する適切な\(j\)の決め方を単純な数式で表すことができるため、\(d\)の値を高速に求めることができれば制限時間内に正解を出力させる処理に仕上げられると分かる。

\(d\)の値を求めるために二分探索を用いる。より具体的には、\(S\)中に文字\(c\)が\(M\)回登場し、\(S\)中におけるそれらの添字を小さい方から書き並べたリスト\(L_c\)が\begin{align} L_c = ( c_0 , c_1 , \dotsc, c_{M - 1} ) \end{align} となっているとする。ここで、\(i < c_k\)なる\(k\)のうち、\(c_k\)の値が最小であるものに注目すると、 \begin{align} d =  M - k \end{align} と求められる。\(i < c_k\)なる\(k\)が存在しない場合は \begin{align} d =  0 \end{align} と分かる。また、2文字を入れ替える操作は必ず1回行わなければならず、操作を行った結果として\(S\)自身が現れた場合もその1通りを数え上げなければならないことを忘れないようにする必要がある。以上を踏まえて実装を記す。

 

<具体的な実装>

1)変数\(ans\)の値を\(0\)で初期化する。

2)\(i = 0, 1, \dotsc, N - 1\)について、\(S_i\)がaからzのうちのどれであるかを識別し、それぞれの文字用に用意した添字を記憶するリストに\(i\)を追加していく。

3)\(i = 0, 1, \dotsc, N - 1\)について、\(S_i = c\)として、\(S\)中における\(c\)の出現位置の添字を記憶したリスト\(L_c\)を対象に二分探索を実施し、\(i < c_k\)なる\(k\)のうち、\(c_k\)の値が最小であるものを求める。そのような\(k\)が存在する場合は\( d =  M - k  \)、\(i < c_k\)なる\(k\)が存在しない場合は\( d =  0 \)というように\(d\)の値を求める。\(ans\)に\(N-1-i-d\)の値を加算する。

4)手順2)で作り上げた26リストのうちいずれか1つでも要素数が2以上である場合は\(ans\)に\(1\)を加算する。

以上の4)までで計算した\(ans\)を出力すれば題意を満たす処理を実現できる。計算量は3)が最も重く、要素数\(N\)程度のリストを対象に\(N\)回の二分探索を実行することから、全体では\( \mathcal{O}(N\log N) \)の処理となる。

ABC335挑戦記(C問題)

↓問題のページ↓

AtCoder Beginner Contest 335 C - Loong Tracking

 

<内容の振り返り・解法>

更新クエリがやって来るごとに全パーツに対して座標の情報を更新する方針しか思い浮かばず、TLEしない解法を全く見出すことができず本番AC取得失敗に終わった。解説の内容を見ても理解できない箇所がなかっただけに頗る悔しい。

公式解説 に記載されている通り、添字による要素へのアクセスが可能なdequeを用いれば楽に実装できるが、最終的には配列をdeque擬きとして扱って実装した(Javaが標準でそのようなdequeを用意しているのか理解していないためであるが、そもそも自前で添字アクセス可能なdequeを作っておけよという話でもある)。

例えば\(N = 5\)の場合を考える。また、\(i\)番目のパーツの座標を\(P_i\)と表す。以上を踏まえ、更新クエリがやって来る度に全パーツの座標を愚直に更新する方針を選ぶ時の挙動を考える。初期状態で\begin{align} (P_1,P_2,P_3,P_4,P_5) = (a_1,a_2,a_3,a_4,a_5) \end{align}という値を取っているとする。1回目の更新クエリで\(P_1\)が\(b_1\)に変化するとして、\(i+1\)番目のパーツが\(i\)番目のパーツに追従して動くことを踏まえると、この更新クエリを実行した後の状態における各パーツの座標は以下のようになる。\begin{align} (P_1,P_2,P_3,P_4,P_5) = (b_1,a_1,a_2,a_3,a_4) \end{align}これを見ると、先頭が別の値に更新されている他は、1つだけ添字を隣に移すという操作をしているのと等価であると分かる。そこで、十分な長さを持つ座標の情報書き込み領域を予め確保しておき、「先頭の要素の添字を覚えておき、先頭から\(N\)要素分の領域しか参照しない」ことと定めれば、\(0\)回以上の更新クエリが実行された後の状態における\(i\)番目のパーツの座標を添字によるアクセスで瞬時に取得することができる。より具体的には、上記の例だと書き込み領域を\(8\)要素分確保しておき、ひとまず初期状態では\begin{align} (P_1,P_2,P_3,P_4,P_5) = (a_1,a_2,a_3,a_4,a_5) \end{align}という座標になっており、書き込み領域を\(B\)と命名して\begin{align} (B_1,B_2,B_3,B_4,B_5,B_6,B_7,B_8) = ( (0, 0),(0, 0),(0, 0),a_1,a_2,a_3,a_4,a_5) \end{align}であるとしておく。この時、先頭の要素の添字を\(head\)と名付けると、\(head = 4\)が成立している。この状況下において、\(head\)から\(N\)要素だけ切り出すと以下のようになる。\begin{align} (B_4,B_5,B_6,B_7,B_8) = (a_1,a_2,a_3,a_4,a_5) \end{align}先ほどと同様に「1回目の更新クエリで\(P_1\)が\(b_1\)に変化する」という情報を受け、「\(head\)の値を\(1\)だけ減算し、新しい\(head\)に対応する書き込み領域に\(b_1\)という座標を記録する」という操作を行うと、書き込み領域は以下のように変化する。\begin{align} (B_1,B_2,B_3,B_4,B_5,B_6,B_7,B_8) = ( (0, 0), (0, 0),b_1,a_1,a_2,a_3,a_4,a_5) \end{align}この時、「先頭から\(N\)要素分の領域しか参照しない」と定めていたことに従うと、\(B_3\)から\(B_7\)までが各パーツの座標ということになり、この部分のみ切り出すと\begin{align} (B_3,B_4,B_5,B_6,B_7) = (b_1,a_1,a_2,a_3,a_4) \end{align}であることから、確かにこの方針によって「更新クエリがやって来る度に、全パーツの座標を愚直に更新する」方針と同じ結果を効率良く取得できることが分かるので後は実装するだけとなった。

 

<具体的な実装>

1)\(Q\)個のクエリが全て更新である場合に書き込み領域の長さが最大となるため、予め\(N + Q\)以上に設定しておくと確実に配列外参照を防ぐことができる。

2)書き込み領域の長さを\(L\)とする(以下、0-indexedを前提として記載する)。また、\(head = L - N\)と初期化する。\(i = 0, \dotsc, N - 1 \)について、初期状態における座標の情報を書き込む(即ち\( B_{head + i} = (i + 1, 0) \)とする)。

3)更新クエリがやって来た場合、\(head\)をデクリメントし、その値を用いて\begin{align} B_{head} = 新しい座標 \end{align}とする。

4)出力クエリがやって来た場合、\(B_{head + p -1}\)の値を出力する。

※書き込み領域をリングバッファにすればもっとメモリ効率良く実装は可能であるが、今回の問題では些事であるため考慮は不要とした。

ABC332挑戦記(C/D問題)

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)上記の転倒数を求められるよう、 順列ライブラリ を修正。

ABC331挑戦記(C問題)

↓問題のページ↓

AtCoder Beginner Contest 331 C - Sum of Numbers Greater Than Me

ぱっと見ですぐには解法を思い浮かべられなかったので体感C問題にしてはやや難しい方かなと思ったが、AtCoder Problemsの統計を見ると灰色なのでさっさと解けなければならない問題だった。何とか本番中にACを獲得できて喜ばしいことこの上ない。

 

解法:

1)入力される数列\(A\)と全く同じ項を持つ数列\(B\)を用意する。

2)数列\(B\)を昇順に並べ替える。

3)\( i = 1, \dotsc, N \)について、各項の値を以下のように定義した数列\(C\)を用意する。

\begin{equation} C_i = B_1 + \dotsb + B_i \end{equation}

4)\( i = 1, \dotsc, N \)について、二分探索を用いて\( A_i < B_j \) なる最小の\(j\)を求める。そのような\(j\)が存在する場合は\( C_N - C_{j-1} \)を、存在しない場合は\(0\)を出力する。

 

計算量の考察:

1)で\( \mathcal{O}(N) \)の処理、2)で\( \mathcal{O}(N\log N) \)の処理、3)で\( \mathcal{O}(N) \)の処理(漸化式のように計算すれば可能)、4)では二分探索を\(N\)回実行するため\( \mathcal{O}(N\log N) \)の処理を行う。最も重い\( \mathcal{O}(N\log N) \)が全体としての計算量となり、制約で示された\(N\)でも間に合う。

ABC326挑戦記(D問題)

↓問題のページ↓

AtCoder Beginner Contest 326 D - ABC Puzzle

最終的にはこの問題に敗北し、終了後に kyopro_friends氏による公式解説 の通りに実装した(これに伴い、 既存の順列全探索用ライブラリ を改良し、複数の順列に対しても全探索を実行可能とした)。

各行について、書き込まれる列が4か所以上になると第1の条件を満たし得なくなることを見出し、bit全探索を利用して3か所のbitのみが立っている状態についてのみ、各行について[A, B, C]の3文字からなる順列に応じて書き込み、書き込み完了後、3つの条件に適するかを検査し(第1の条件に関して、各行については書き込んでいる3か所が[A, B, C]の順列になっているため列に関してのみ再確認すればよい)、適切なものが見つかればそれを出力すると解けると本番中に考えたものの、探索範囲の広さを考慮すると、各行についてbitの状態数だけで

\begin{align} (2^N)^N \end{align}

通り存在し、さらに、各行に対して[A, B, C]の順列を書き込む場合の数が

\begin{align} (3!)^N \end{align}

通り存在する。Nの値は最大で5なので、探索範囲は最大で

\begin{align} (2^5)^5 \times (3!)^5 =260919263232 > 2.6 \times 10^{11} \end{align}

に及ぶためTLEし、このアルゴリズムではダメだと分かった。公式解説に書かれている通り、各行各列にAが1個ずつ配置されるようなAの書き込み方は

\begin{align} N! \end{align}

通りである(例えばNが5の時ならば、[0, 1, 2, 3, 4]の並べ替えに対し、「y番目の値がxならば、y行目のx列目にAを書き込む」と定めれば、それぞれの順列が前述のようなAの書き込み方と1対1に対応する。Nが他の値であっても同様)ため、B, Cについても書き込み方を同様に考えると、各行各列にA, B, Cがそれぞれ1度ずつ登場するような書き込み方は、最大で

\begin{align} (5!)^3 = 1728000 < 1.8 \times 10^6 \end{align}

程度にまで抑えられるため、最初の手法と同様、全マスに書き込んだのちに条件を満たすかを検査するというように処理させれば十分間に合う。

2つ以上の順列に対する全探索を実行可能なライブラリを事前に用意しておかなかった点、および赤い太字の部分を見出すことができなかった(経験不足)点が明確な原因だったと思われる。まだ手が届きそうな問題だと初見で直感的に感じたため悔いの残る結果となった。

Java向け競プロライブラリ(構成文字で並べ替えた文字列)

以下の問題を解くための手法として「2つの文字列S, Tについて、Sの各文字を並べ替えてTに一致させられるかを考える場合、SとTの各文字を昇順に並べ替えてできる文字列どうしを比較して一致しているかどうかを判定する」と公式で解説されており、ライブラリを用意していなかったので作成しました

AtCoder Beginner Contest 324 D - Square Permutation

import java.util.Arrays;

public final class DigitSorter {

	/**
	 * 整数の各桁を昇順に並べた文字列を返す
	 * @param n 文字列として取得したい整数
	 * @param minLen 並べ替え後の文字列の最小長
	 * @return 最小長を持つよう0埋めにより正規化された、整数の各桁を昇順に並べた文字列
	 */
	public static final String sortByDigits(long n, int minLen) {
		final String nAsString = String.valueOf(n);
		final int appCnt = Math.max(0, minLen - nAsString.length());
		StringBuilder sb = new StringBuilder(appCnt + nAsString.length());
		for (int i = 0; i < appCnt; ++i) {
			sb.append(0);
		}
		return sortByDigits(sb.append(nAsString).toString());
	}

	/**
	 * 構成する各文字を昇順に並べた文字列を返す
	 * @param str 各文字を並べ替える前の文字列
	 * @return 構成する各文字を昇順に並べた文字列
	 */
	public static final String sortByDigits(String str) {
		char[] strAsCharArray = str.toCharArray();
		Arrays.sort(strAsCharArray);
		return String.valueOf(strAsCharArray);
	}

}

Java向け競プロライブラリ(一致文字列長)

以下の問題を解くための手法として「2つの文字列を順方向・逆方向それぞれに走査し、一致する部分の最大長を求める」というものが公式解説に用意されており、ほとんど典型手法と見なされている(諸説あり)にもかかわらず、ライブラリを用意していなかったので作成しました

AtCoder Beginner Contest 324 C - Error Correction

※該当問題ではcountDifferenceIfSameLengthメソッドを利用することはありませんでしたが個人的な判断で残しているだけなので不要ならば削除でOKです。個人的にはこのクラスに対して最良の命名をできてはいない感覚でいますが、これ以上に良いクラス名を思いつくことができませんでした

public final class StringScanner {

	/**
	 * 2つの文字列を順方向に走査し、一致する文字数を返す
	 * @param s1 1つ目の文字列
	 * @param s2 2つ目の文字列
	 * @return 2つの文字列を順方向に走査した時、一致しない文字が初登場するまでの長さ(先頭が不一致の場合は0)
	 */
	public static final int countSameCharactersForward(String s1, String s2) {
		if (s1.length() > s2.length()) {
			return countSameCharactersForward(s2, s1);
		}

		int res = 0;
		for (int i = 0, f = s1.length(); i < f; ++i) {
			if (s1.charAt(i) == s2.charAt(i)) {
				++res;
			} else {
				break;
			}
		}

		return res;
	}

	/**
	 * 2つの文字列を逆方向に走査し、一致する文字数を返す
	 * @param s1 1つ目の文字列
	 * @param s2 2つ目の文字列
	 * @return 2つの文字列を逆方向に走査した時、一致しない文字が初登場するまでの長さ(末尾が不一致の場合は0)
	 */
	public static final int countSameCharactersBackward(String s1, String s2) {
		if (s1.length() > s2.length()) {
			return countSameCharactersBackward(s2, s1);
		}

		final int offset = s2.length() - s1.length();
		int res = 0;
		for (int i = s1.length() - 1; i >= 0; --i) {
			if (s1.charAt(i) == s2.charAt(offset + i)) {
				++res;
			} else {
				break;
			}
		}

		return res;
	}

	/**
	 * 2つの文字列を走査し、各インデックスに対応する文字列中の文字のうち一致しないものの数を返す
	 * @param s1 1つ目の文字列
	 * @param s2 2つ目の文字列
	 * @return 2つの文字列の長さが等しい場合、一致しない文字数を返し、等しくない場合は-1を返す
	 */
	public static final int countDifferenceIfSameLength(String s1, String s2) {
		if (s1.length() != s2.length()) {
			return -1;
		}

		int res = 0;
		for (int i = 0, f = s1.length(); i < f; ++i) {
			if (s1.charAt(i) != s2.charAt(i)) {
				++res;
			}
		}

		return res;
	}

}

 

<余談>
countSameCharactersBackwardメソッドに関して、最初は以下のような実装でしたが、String.formatを使用して文字列長を揃えるように正規化させる処理の実行回数が多くなると急激に実行速度が落ちてTLEの原因となるようなので上記のように修正しました

	static final int countSameCharactersBackward(String s1, String s2) {
		if (s1.length() > s2.length()) {
			return countSameCharactersBackward(s2, s1);
		} else if (s1.length() < s2.length()) {
			return countSameCharactersBackward(String.format("%" + s2.length() + "s", s1), s2);
		}

		int res = 0;
		for (int i = s1.length() - 1; i >= 0; --i) {
			if (s1.charAt(i) == s2.charAt(i)) {
				++res;
			} else {
				break;
			}
		}

		return res;
	}