mini-notes

競技プログラミングの解法メモを残していきます。

Indeedなう(予選B)D - 高橋くんと数列

問題:D - 高橋くんと数列

解答:Submission #11255665 - Indeedなう(予選B)

解法:数字xについて愚直に(l, r)の組を数えることを考える。lごとに該当するrの数を数えるとする。

  1. a[l] = x:r = l からnまでがxを含む部分列になる。
  2. a[l] ≠ x:l' > lかつ a[l'] = xなるl'があればr=l'からnまでがxを含む部分列になる。もしそのようなl'がなければ該当するrは存在しない。

上記より、あるxについてa[i] = x となるiを集めた集合をvとするとi< j, i∊v, j∊vである場合、lがiからjの間(excl.)の部分列の個数は一致することになる。よって、v = {i1, i2, ..., im}とすると、lが1からi1までの部分列の個数、lがi1の部分列の個数、lがi1からi2の部分列の個数、…、lがim-1からimまでの部分列の個数、lがimの部分列の個数を計算することで、計算が間に合う。

DigitalArts プログラミングコンテスト2012 B - Password

問題:B - Password

解答:Submission #11252972 - DigitalArts プログラミングコンテスト2012

解法:aもしくはz*20の場合は同じハッシュ値を持つパスワードがないのでNO。それ以外は次のように生成する。

①1文字でa以外:1文字をXとすると(X -1)aの2文字とする(例:d → ca)

②2文字から19文字で全部a:'a' + aの個数 - 1の文字(例:aaa → c)

③2文字から19文字でa以外がある:最小に現れるa以外の文字をXとするとその部分を(X-1)aにする。(例:abc → aaac)

④20文字で全部a:②と同じ

⑤20文字で④でない、かつ全部zでない:aでない文字Xを(X-1)にし、zでない文字Yを(Y+1)にする

⑤はコーディングによってはバグを埋め込むので注意。(最大の文字をX-1、最小の文字をY+1とした方がよかった)

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

問題:B - ヘイホー君と削除

解答:Submission #11251025 - CODE FESTIVAL 2015 あさぷろ Middle

解法:文字列sをある場所を区切って文字列aとbに分割する。aで平方の前半、bで平方の後半を作るとする。このとき作れる平方文字の最大長はaとbのLCS(最長部分文字列)の長さの2倍になる。よって区切り方をすべて試し、そのたびにlcsを計算すればよい。

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B - ディスコ社内ツアー

問題:B - ディスコ社内ツアー

解答:Submission #11247515 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選

解法:見ていく順番は一意に決まるので何周するかを求めればよいが、Nに関するループの繰り返しにするとTLE。

同じA[i]のもののインデックス集合を作り、aのループにする。

今いるインデックスを保持して置き、各aではその次のインデックスをupper_boundで探してあげる。この操作で最大O(logN)、次のインデックスはO(1)で探せるので、O(max_A * logN)で計算できる。

なお、周回数はendedフラグをもっておいて、終端まで達した状態でインデックスが1以上になったらカウントアップするとよさそう。

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 B - DDPC特別ビュッフェⅡ

問題:B - DDPC特別ビュッフェⅡ

解答:Submission #11246595 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選

解法:「時刻tで美味しさの総和がX以上になるか」という二分探索をする。二分探索内の条件判定では、時刻tからさかのぼって見ていって、その時点で期限が来ていない料理のうち、最もおいしいものを貪欲に選んだ時の総和で判定する。

ARC024 C - だれじゃ

問題:C - だれじゃ

解答:Submission #11167793 - AtCoder Regular Contest 024

解法: s[i : j]をsのi+1文字目からj文字目までの部分文字列とする。マッチングをチェックするのは以下の範囲。

  • s[k : 2k]はs[0 : k]をチェック
  • s[k+1 : 2k+1]はs[0 : k], s[1 : k+1]をチェック
  • ...
  • s[n-k : n]はs[0 : k], s[1 : k+1], ..., s[n-2k : n-k]をチェック

調査対象は先頭から増えてゆくものの、s[0 : k]が最初にチェックされるのはs[k : 2k]のときである。よって次のようなやり方でチェックを行うとよい。

  • チェック対象は文字列の順番が関係ないので、「各文字が何文字あるか」のvector自体をチェック対象にする
  • s[0 : k]から先にqueueに入れておき、調査対象となる文字列でqueueからsetに入れる
  • setに調査対象と一致するものがあればその時点でYESを出力