読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#009

- A問題「引っ越し作業」

(http://abc009.contest.atcoder.jp/tasks/abc009_1)

問題概要:
ダンボールを片手に一つ持って家からトラックに運びます。
最大1000個のダンボールとは超豪邸ですね。うらやましい限りです。

解法:
Nが偶数であるならばN/2
奇数ならばN/2+1でOKです。

ソースコード:
https://abc009.contest.atcoder.jp/submissions/175016


- B問題「心配性な富豪、ファミリーレストランに行く」

(http://abc009.contest.atcoder.jp/tasks/abc009_2)

問題概要:
ファミレスで2番目に高い品物の額をこたえよという問題です。
ファミレスで高い品物というとやはりステーキとかその辺になってくるのですかね。

解法:
O(N)で全探索をして上から2番目までの大きい値を保持すればOKです。
コーディングをするならalgorithmをインクルードしてソートしたほうが早いし見やすいでしょう。
過去の自分への戒め。

ソースコード:
https://abc009.contest.atcoder.jp/submissions/175107


- C問題「辞書式順序ふたたび」

(http://abc009.contest.atcoder.jp/tasks/abc009_3)

問題概要:
多分D問題より難しいです。
文字列長Nの文字列SのうちK個以下の文字の位置を入れ替えてできる文字列の辞書順最小のものを求めよ。組み合わせ最適化問題ですね。
例)N=10,K=3 S=「helloworld」
=dehloworll(d,h,lの3つの文字を入れ替えてできたものが辞書順最小)

解法:
全探索は最悪で2^{100}通りとなるので諦めましょう。
5回ぐらいWA吐いてからようやくAC出したんですが模範解答見たら全然解法が違いました。
方針は以下の通りです。
暫定の辞書順最小文字列をT,残り変更可能な文字列をkとします。
(初期状態:T=S,k=K)
(k>=2のとき)
Tの任意の位置i,jについてT[i]とT[j]をスワップしてもkは0未満にはならない。
任意の位置でスワップできる場合は辞書順の小さいものを先頭に来るようにスワップすればよい。
スワップする文字の選び方に注意。
1.Sをソートした文字列IDを用意し、TとIDの最初に違う文字がスワップ対象の一つ。T[i]とする。
2.ID[i]と同じ文字をTから探すT[j]とする。

T[i]を入れ替える時、T[0]からT[i-1]の部分は確定済みで入れ替えてはいけない。したがってj>i
また、既に入れ替え済みであるT[j](ID[i]==T[j],j>i)がある場合、それを優先して入れ替える。(できるだけkが減らないように入れ替える)
また、入れ替え候補が複数存在する場合、後ろにあるものを優先して入れ替える。

3.T[i]とT[j]を入れ替える。kを更新する。
kが2以上なら再び1へ、kが1なら残り1文字の入れ替えを全探索。
特に2の入れ替えの優先度が肝です。
計算量は1,2,3の一連の流れがO(N)(ループするごとにiの値が増えていくため)。
1,2の探索がともにO(N)、O(N^2)

ソースコード:
https://abc009.contest.atcoder.jp/submissions/343493


- D問題「漸化式」

(http://abc009.contest.atcoder.jp/tasks/abc009_4)

問題概要:
K項間漸化式を解く問題です。一般的なm項間漸化式とこの問題の違う点は演算子がビット演算であるという点です。
M項目の値を出力せよという問題ですがMの最大が10^9であるため注意が必要です。

解法:
漸化式といえばまず動的計画法を思い浮かべます。
しかし通常の動的計画法ではO(KM)で時間内に最悪のケースを解ききることができません。
ここでABC#006のB問題で紹介した方法が役に立ちます。
ABC#006 - 競技プログラミングをするんだよ
コンパニオン行列、きたまさ法などの2進数展開を利用した演算子が有効です。
これを使うことでO(K^2*logN),O(K^3*logN)で解くことができ、時間内に解くことができます。
演算子法を使う上で注意点があるのでここに記述しておきます。
m項間漸化式を演算子法を用いて解く場合、演算子群が半環である必要があります。
半環の説明については割愛させていただきます。wikipedia等に詳しい定義が載っているのでそちらに。
今回のケースでいくと、各ビットはどのような演算を行っても他のビットの影響を受けることはありません。
したがって、1ビットだけについて考えればXORは加算に相当、ANDは乗算に相当するため、XOR,ANDの組み合わせは半環の関係が成り立つことがわかります。したがって演算子法の加算、乗算部分をXOR,ANDに変えてやるだけでこの問題は解くことができます。
1ビットごとの演算と考えているため、乗算の単位元は各ビット1です。つまり、
A_{m}=(c_{1}A_{1}) xor (c_{2}A_{2}) xor ...(c_{K}A_{K})としたとき、
A_{1}=(111111111...(B))A_{1}、他の係数は0
であることに注意してください。

ソースコード:
https://abc009.contest.atcoder.jp/submissions/343281