AtCoder Beginer Contest 303~350 D or E までの要点・解答(Go)
next: AtCoder Beginer Contest 351~400 D or E までの要点・解答(Go)
※ 個人的なメモ。コードは比較的読み易いと思います。
※ そのトピックにおいて典型的な問題の場合、問題タイトルの後ろにトピックを記載。
350
A - Past ABCs
- 愚直
B - Dentist Aoki
- クエリが少ないので愚直にループ
code
C - Sort / Sort
-
未ソート配列について、正しいソート順がわかっていれば最大でも N-1 回のスワップ操作でソートすることができる。
- 一つづつ正しい位置にスワップしていけばいい。
-
各数字のインデックスを記録する。1~N の数字について、実際のインデックスと期待するインデックス(num-1)と一致するかみて、一致していなければスワップし、インデックスの記録を更新していけばいい。
-
自前でソートを実装し、スワップ操作にコールバックを挟むようなやり方は厳しい。純粋なスワップ操作をするようなソートアルゴリズムはバブルソートなどだが、計算量が N^2 なので間に合わない。
code
D - New Friends / Union Find、連結成分
-
友達の友達も友達にする。これをできなくなるまで繰り返す。これは、グラフの連結成分について、完全グラフ(全ての頂点から他の全ての頂点への変が存在する)にするということ。
-
完全グラフの辺の数は
\binom{N}{2} -
Union Findを用いて、各ノードを連結する。ルートノード毎のサイズから、各連結成分(辺で行き来的る範囲)の完全グラフになった時の辺数の和を求めていく。最初に存在していた辺数 M を引けば、答えになる。
code
349
A - Zero Sum Game
- 愚直
B - Commencement
-
マップに文字種ごとの出現回数を記録。そのマップをもとに、出現回数毎の文字種の数を別のマップに記録。
-
1~N までの数字について、後者のマップからその出現回数の文字種の数が 0 か 2 であるかを調べる。
code
C - Airport Code
-
T = strings.ToLower(T)
で T を小文字に合わせる。 -
T = strings.TrimSuffix(T, "x")
で末尾に x があれば取り除く。(x は S に含まれていても含まれていなくてもどちらでもいい。) - Ts をループし、中で Ss を最後に見たインデックス+1 から現在探している文字が見つかるまでループし、最後に見たインデックスを更新する。
code
D - Divide Interval / 数列の分割、セグメント木
-
定義より、いい数列の
r-l
(=数列の要素数)は 2 の乗数になる。さらに、l, r ともに 2 の乗数の倍数になる。 -
2 の乗数の区間を考えるということで、セグメント木 が使えそう。
- ある区間を 2 の乗数の長さの区間に分割することを考えるということ。
- 大きな 2 の乗数の長さの区間から貪欲に分割していきたい。
-
セグメント木とは、ある区間の範囲について、ルートノードには区間全体を、一つ下の階層のノードには左半分と右半分を、...というように完全二分木に格納したデータ構造。
-
制約よりあり得る最大の区間
[0, 2^60)
ついて、セグメント木のようなデータ構造を考える。 -
2^60 の長さの区間から順に、入力の
[L, R)
に完全に内包されているかどうかを見ていく。内包されていれば ans スライスに追加し、はみ出た左右の部分があれば同様の処理に再帰的にかけていけばいい。- 一度の処理で二つ以上の同じ長さの区間が完全に内包されることはない。そうであるならば、一つ上の二倍のサイズの区間が完全に内包されているはずだから。
-
O(log N)
になる。完全に内包される区間がいつかは見つかりその際に再帰が止まるため、チェックする階層の数に比例する。
code
348
A - Penalty Kick
- 愚直
B - Farthest Point / 全探索
- 各頂点について、他の頂点全てとの距離(の二乗)を計算し最も遠い点を求めても、制約より
O(100 * 99)
にしかならない。変な工夫を考えずに全探索する。
code
C - Colorful Beans / Ordered Set
-
N 行の入力を処理しながら、各色のおいしさをOrdered Setに突っ込んでいき、後で各色の最も低いおいしさを取り出して、その中の最大を出力すればいけそう。
-
ただし色は最大で 10^9 種類存在し、色でループできないので工夫が必要。
- 『「各色の Ordered Set の min value」の Ordered Set』を作っておく。
- 「各色の Ordered Set」に更新があるときは、事前に
First()
を取得し『』からErace()
、更新後に再度First()
を取得し『』にInsert()
する。 - N 回のループ後に『』の Ordered Set から
Last()
を取得すれば答え。
code
D - Medicines on Grid / BFS
-
エネルギー量をキューアイテムに保持し、BFSを行う。ただし探索済みノードの記録において、よりエネルギーの多い状態でのノード再訪は試す価値があるため、bool ではなく残りエネルギー量で訪問を記録する。
-
薬は使うとなくなるが、個別の経路ごとに一度づつ使用可能なため、使っても記録からは消さない。上記の訪問済みノードの記録により、同一経路では二度同じ薬マスに来ない。
-
DFSでの探索も考えたくなるが、DFS では再帰の終了時(呼び出しもとに帰る時)に訪問済みを解除するため、よりエネルギーの少ない状態での訪問済みマスへの無駄な再訪を回避できず TLE になる。
- エネルギーを無駄にしない効率的な(最短の)移動が求められることから、BFS が適していることを感じ取りたい。
code
347
A - Divisible
- 愚直
B - Substring / 全探索
- 部分文字列の長さは最大 100。部分文字列の取り方も最大 100。全探索が 100^2 に収まるので、スマートなやり方を考えずに全探索する。
code
C - Ideal Holidays / 円環
-
1週間という周期の中で、各休日がどこに位置するかを考えたいので、各休日の日付を周期の長さ A+B で割った余り(rem)に変換する。
-
同じ位置の休日のデータが重複しても仕方ないので、rem を map に突っ込んで、map のキーからスライスに変換する。そしてソート。
-
休日の位置関係で考えると難しい。逆側の、平日について考える。平日が B 日以上連続している区間が存在すれば、条件を満たしていると問題文を言い換えることができる。
-
rems[i] - rems[i-1] - 1
で休日の間に何日平日が存在しているかが分かる。-
円環を跨ぐ
i == 0
の時は工夫が必要で、rems[i] - 1 + (weekdays - rems[len(rems)-1])
とする必要がある。
-
円環を跨ぐ
code
D - Popcount and XOR / XOR(排他的論理和)
-
XOR(排他的論理和) は、A と B のどちらかが一方のみが true なら true、それ以外は false。go の演算子は
xor := A ^ B
-
C を二進数表現にしてみる。
X ^ Y == C
となる (|C|桁の)X、Y は、(C、0)に加え、前者から任意の桁のビットをおり、後者の同じ桁のビットを立てる操作を任意の回数繰り返すことで列挙することができる。C: 7 => 111 => 111 | 000 110 | 001 101 | 010 ...
-
よって|C|桁までの X と Y の、
popcount(X)+popcount(Y)
は常にpopcpount(C)
と一致することがわかる。そして、以下の場合に条件を満たす X、Y は存在しないことがわかる。a + b < popcpount(C)
-
abs(a-b)%2 != popcpount(C)%2
-
popcpount(C)
が偶数なら、幾つビットを受け渡しても X と Y の popcount の差は偶数にしかならないため。
-
-
abs(a-b) > popcpount(C)
- 最大の差分は(C、0)の時の
popcpount(C)
であるため。
- 最大の差分は(C、0)の時の
-
上記を弾いたのち、 X、Y を(C, 0)または(0, C)で初期化し、適切な diff になるまでビットを受け渡す。
-
その後、所定の
popcount(X)(=a)
、popcount(Y)(=b)
に達するまで無害な方法でビットを足して行けばいい。
code
E - Set Add Query / 遅延評価
- 愚直にやると N 回のクエリの中で N 回ループをやらないといけないので間に合わない。後者を高速化する。
に対する更新結果はその後の更新に影響を与えないので、まとめて行うためになんらかの遅延評価を考えたい。A_i
解法 1 累積和
- 「各
の i が、いつ集合 S に追加されたか、削除されたか(A_i var idxInOut [][]int // idx => in, out, in, ...
)」を記録し、「j 回目のクエリでいくつインクリメントがおきたかの累積和」を記録すると、最後に各 に対して値を求められる。A_i - 各
idxInOut
の要素数について、奇数のもの(最後に out していないもの)には Q をアペンドすればいい。 -
idxInOut
の要素数の合計は高々 N なので、全体でO(N)
で済む。
- 各
解法 2 ポインタ
- 今までに行われたインクリメントを
var increment int
に反映していく。 - S に idx の追加があったときに、
&increment
とそれまでのインクリメントを相殺するための-*increment
を持った構造体をスライスに追加する。 - S に idx の削除があったときに、上記スライスから別のスライスにインクリメントを整理した上で構造体を移す。
- 最後に各 i に対して、いずれかのスライスから
Increment
を取り出し、値を求められる。
type Increment {Diff int, increment *int}
var increments []Increment // idx => ongoing Inc
var suspendedIncrements []Increment // idx => suspended Inc
code
346
A - Adjacent Product
- 愚直
B - Piano / 無限数列、円環
-
無限数列の条件に合う部分列を探すときは、2 周期分の数列を探索することで全ての部分列が探索できる。
- 指定の部分列の長さが一周期分を超えるときは、両側にはみ出す区間のパターンだけ考えればよく、それが上記で探索できるということ。
-
よって
部分列の長さ:W+B%12
、探索する数列の長さ:24
となり、最大 24 回の探索で答えが判定できるので、全探索する。
code
C - Σ / 等差数列の和の公式
-
As をソートし、
As[i] - As[i-1] => 1
なら間に飛ばされている整数があるので、その飛ばされている数字の合計を等差数列の和の公式で求めればいい。 -
ただし、0 から As[0]の間で飛ばされている数も見つけたいので、As に 0 をアペンドしておく。
-
K までの間に飛ばされている数字がないかどうか見たいので、As に K が含まれていると K に到達したイテレートでループを break できるので都合がいい。K が含まれていなければ K をアペンドし、飛ばされている数の合計に K を足しておく。
code
D - Gomamayo Sequence / 累積和
-
どこで周期を変えるかは非自明であるため、その探索 O(N)はやらざるを得ない。よって、効率的にコストを計算する必要がある。
-
N 文字の良い文字列とは、N 文字の
01
周期の繰り返し文字列(zeroOneSeq)と10
周期の繰り返し文字列(oneZeroSeq)を用意し、index 0 ~ i が片方のもの、index i+1 ~ N-1 がもう一方のものになっている文字列であると言い換えられる。(0 < i < N-1) -
oneZeroSeq、zeroOneSeq を作るためのコストの累積和を作成しておき、周期の境目ごとのコストを累積和から算出していけば、O(N)で最小コストが求められる。
-
oneZeroSeq => zeroOneSeq
とzeroOneSeq => oneZeroSeq
の順番があり得ること、累積和(長さ N+1)からの値の取り出し方に注意する。
-
-
類題: 334 C - Socks 2
code
E - Paint / 後ろから見る or 二分探索
- マスの最終的な色は、そのマスが属する行 or 列に対して最後にどの色で塗られたか。
解法 1 後ろから見る
- 行、列が未確定かどうかを管理しつつ、クエリを後ろから処理する。
- 行が一つ確定した場合、それ移行(=以前)のクエリでなんらかの列を確定させるとき、H-1 マスしかその色で塗れない。これを利用し、remainH, remainW を記録更新する。
- 最後に
remainH * remainW
を色 0 のカウントに足す。(何行目、何列目かという情報はどうでもいいので、グリッドを右下から塗り、最後に左上の領域が塗られずに残るというイメージを持つと分かり易い。)
解法 2 二分探索
- 各行、各列が最終的に何回目のクエリで何色で塗られたかを記録する。スライスは
{qIndex: 0, color: 0}
で初期化。- その後、
qIndex
でソート。
- その後、
- 上記スライスをループし、その行への変更より
qIndex
が大きい列の変更がいくつあるかを二分探索し、その行の変更で何マスその色で確定したかをカウントする。- 初期値の
{qIndex: 0, color: 0}
の場合スキップ。重複qIndex
は二分探索の妨げにはならないものの、塗られなかったマスを重複でカウントしてしまうことにつながってしまうため。
- 初期値の
- 最後に総マス数から上記の操作で確定したマス数を引いたものを色 0 のカウントに足す。
code
345
A - Leftrightarrow
- 愚直
code
B - Integer Division Returns
- 愚直。go の割り算(
/
演算)は切り捨て。
code
C - One Time Swap
-
スワップによって文字列が変化するのは、ある
Ss[i]
を別の文字種であるSs[j]
とスワップしたとき。 -
文字種ごとに考えたいので、とりあえず
map[char]count
のマップにする。 -
各文字種ごとに、それらの文字以外とスワップするとユニークな文字列になる。
- ループで数え上げ可能だが、ある index x, y について、
(i: x, j: y)
と(i: y, j: x)
の 2 通りについて重複加算することになってしまう。(というより本来 i < j となる組み合わせのスワップしか許容されない。)なので、最後に数え上げを 2 で割る。
- ループで数え上げ可能だが、ある index x, y について、
-
あるスワップをして、オリジナルの S と全く変わらないものができても答えに1加算するべきなので、同じ文字種が2つ以上ある場合はそうする。(サンプルケースが教えてくれている。)
sum := 0
sameChars := false
for _, count := range m {
sum += count * (len(Ss) - count)
if count >= 2 {
sameChars := true
}
}
sum = sum / 2
if sameChars {
sum++
}
code
D - Tiling / ポリオミノ、ビット全探索、順列
-
ポリオミノ系の問題は基本全探索で解く。
- 空きマスの最も左上からタイルを配置していき、グリッドからはみ出したり配置済みのタイルと被ると失敗。失敗せずにグリッドがすべて埋まれば(=空きマスが見つからない状態になれば)成功。
-
配置のパターン数 = タイルを使う順番 * 各タイルを縦横どちらで使うか = 7! * 2^7 = 645120 - 各タイルを縦横どちらで使うかはビット全探索する。
-
さらにタイルを置くたびに以下を行うため
となるが、十分現実的。O(200 * 645120) = O(129024000) - タイルのマスが使用済みではないか調べつつ、使用済みの記録をする:10^2
- グリッドをさらって最も左上の空きマスを調べる:10^2
-
NextPermutation()
で順列に対してロジックを適用するときは、オリジナルの順列への適用を事前に別で書く必要がある。
code
344
A - Spoiler
-
Ss = append(Ss[:barIdx1], ...Ss[barIdx2+1:])
で該当区間を取り除く。
code
B - Delimiter
-
for true {}
で 0 が登場するまで行を読み込んでスライスに追加。最後にスライスを反転。
code
C - A+B+C
-
Xi ごとに全探索すると、
となり間に合わない。O(Q * (N * M * L)) = O(3*10^8 * 100^3) -
問題の性質上 Xi ごとのループは必ずするので、Xi が作成可能かを高速に判定する必要がある。
-
A, B, C の組み合わせをあらかじめ全探索(
)して和をマップに記録しておけば、マップへのアクセスのみで各クエリを処理でき間に合う。O(100^3)
code
D - String Bags / DP(メモ化再帰)
-
全探索すると
となり間に合わない。O(袋の要素数^{袋の数}) = O(10^{10}) -
問題の性質上、順に各袋から要素を取る(またはとらない)、次の袋にいく...という処理はせざるを得ないと考えられるので、再帰を使いそう。
-
DP(メモ化再帰) で枝狩りができないかを考える。「ある袋まで処理し終わっている」「T があるインデックスまで完成している」という状態が同じなら、それまでの経過は関係ない。
- これを管理する状態とし、状態ごとのコストをメモ化する。
- ある状態に到達した時に、コストがメモ化されていなければさらに再帰して先に進む。
- メモ化されているコストより低いコストで到達したならメモを更新し、更に再帰して先に進む。それ以上のコストで到達したなら処理を打ち切る。
-
DP(メモ化再帰)の計算量はとりうる状態の数による。今回は以下のようになり間に合う。
O(袋の数 * len(T) * コストとして取りうる値) = O(10 * 100 * 10) = O(10000) - 数え上げのような問題と違いメモ化された値によっても再帰が進む可能性があるので、それも計算量においては状態と見なされる。
code
E - Insert or Erase / 双方向連結リスト
- ノードの順番を管理、更新する様な場合、双方向連結リスト(Doubly Linked List) を使えば以下のことが高速に行える。(
)O(1) - 連続するノードから特定のノードを消して前後を繋げる
- (
map[ノードの値]ノードのポインタ
を別で管理することで、)特定のノードの前後に要素を挟み込む
code
343
A - Wrong Answer
- 愚直。
code
B - Adjacency Matrix
- 愚直。何も出力しない場合は空行を1行のみ出力することに注意。
code
C - 343 / 整数問題(最大のいい数)
-
まず立方数のみについて考える。最大の K を考える。
(数式の変形)N = 10^{18} = (10^6)^3 より、 K = 10^6 -
よって検討すべき K は 0 ~ 10^6 であり、100 万個。立方数も同様に 100 万個。全探索できそう。
-
立方数のスライスを用意しておき、N より大きいインデックスを二分探索し、-1する。そこから回文判定のループをインデックスをデクリメントしながらする。
-
回文判定のコストは
文字数/2
で、n は最大でも 7 桁なので全探索が十分間に合う。
code
D - Diversity of Scores
- ユニークな要素の数を考えたいのでマップを上手く使えばいい。二分探索等はしないので Ordered Set は使う必要がなく、通常のマップで事足りる。
code
342
A - Yay!
- マップで文字種の出現数をカウント。
code
B - Which is ahead?
- マップに各番号(の人)の出現位置を記録。
code
C - Many Replacement / メモ化
-
文字列を更新する作業はせざるを得ないため、N(2×10^5)のループは無くせない。つまり、ある文字が最終的にどの文字になるのかを高速に判定する必要がある。
-
クエリを処理しながらある文字が最終的にどの文字になったのかをメモ化するか、あらかじめ a-z が何になるのかをメモ化しておく。
- 計算量は
O(N + 26*Q) = O(5400万) - アルファベットが 26 文字しかないことに着目する問題。
- 計算量は
-
このようなデータ遷移を木のようなデータ構造に記録し、あるデータに対応する最終的な状態を高速に取り出すのは簡単ではない。
code
D - Square Pair / 整数問題(いい数の個数)、素因数分解、平方数、合同式
-
平方数は
と表現でき、逆にこのような数は平方数である。(a^x)^2 * (b^x)^2 + ... - よって、平方数の素因数の指数は全て 2 の倍数である。
-
整数 A, B の積が平方数になるのは、素因数の指数の和が全て 2 の倍数になっている時。
-
が平方数であるとき、(a^p * b^q) * (a^r * b^s) p + q \equiv r + s \equiv 0 \mod 2 (p \mod 2) + (q \mod 2) \equiv (r \mod 2) + (s \mod 2) \equiv 0 \mod 2 - つまり指数を 2 で割った余りに変換し、全ての素因数の指数が 0,0 または 1,1 の組み合わせになっているなら、平方数になる。
- 各 Ai に対して素因数分解をし、素因数の指数を 2 で割った余りに変換し、それらを掛け合わせた値にする。こうして変化させて値が同じになった Ai 同士は、掛け合わせると平方数の条件を満たす。
- よって各 Ai を変化させ、変化後に同じ値がいくつあるかを map に格納する。そして map の key ごとに
を求めてたしあげればいい。{}_{value} C_{2} - ただし A, B いずれかまたは両方に0が含まれる場合は必ず平方数になるので、そこだけ別で考える。
- 0 を少なくとも片方で使う組合わせ:
{}_{len(As)} C_{2} - {}_{len(As)-len(map[0])} C_{2}
- 0 を少なくとも片方で使う組合わせ:
-
code
341
A - Print 341
- 愚直
code
B - Foreign Exchange
- 愚直
code
C - Takahashi Gets Lost
- グリッドサイズ 500^2、実行時間 3sec という制約から、全探索が間に合う。
code
D - Only one of two / 整数問題(K 番目のいい数)、二分探索
-
N と M の倍数を列挙すると、N*M の周期になっている。(どちらの倍数が何番目に出てくるか。)K を周期の長さで割り、余りを順に列挙する方法を考えた。しかし制約より余りの最大は(10^8)^2 なので、厳しい。
-
0~K-1
で No になり、K~INT_MAX
で Yes になるような条件があれば、二分探索が使える。-
f(x) = x以下の条件に当てはまる倍数
を実装し、f(x) >= K
という条件で二分探索すれば、目当ての値が見つけられる。
-
-
制約より、探索範囲の上限は
10^8*10^10
でいい。-
A <= B
とし、B が10^8
、K が10^10
だった場合、10^8*10^10
までの範囲に K 個以上の条件に当てはまる倍数がし存在するため。
-
code
340
A - Arithmetic Progression
- 愚直
B - Append
- 愚直
C - Divide and Divide / メモ化再帰
-
2 以上の数字について、「数字分のコストを総コストに加算し、分割する」を再帰的に繰り返すので、メモ化再帰が使える。
-
計算量はとりうる状態=メモの数になる。
-
ということを覚えておけば、再帰的に二分割を行ってできる階層は 63 以下になることがわかる。一階層ごとに最大二種類の値が生まれる(奇数を分割する場合)ので、計算量は2^{63} \approx 10^{19} 以下になり間に合う。O(126)
code
D - Super Takahashi Bros. / ダイクストラ法、優先度付きキュー(ヒープ)
-
ダイクストラ法で解く。以下基本の tips。
- グラフを作成するときは、
var graph [][][2]int // [node: [[node, weight], ...], ...]
のような型になる -
優先度付きキューの要素は、
type item {node, weight int} // weightは始点からの距離
のような型になる。 - 確定済みノード、各ノードの始点からの距離を別々のマップで管理する必要がある。
- グラフを作成するときは、
- 通常のダイクストラ法だと最短距離(時間)しか求められないが、距離(時間)を記録するときに prev node を一緒に記録しておくと、最後にそこから辿って経路も求めることができる。
code
E - Mancala 2 / 遅延セグメント木
- 箱を区間にのせる。クエリごとに箱
のボール数を 0 にし、B_i の区間にプラス 1 をしていけばいい。B_{i+1}~B_{i+ボールの数} - ボールの数が区間の長さより多い場合は更新の仕方に注意。
- 区間の和の更新は、遅延セグメント木を使えば
O(log N)
で高速に行える。区間の和の取得(ノード単体での取得も含む)もO(log N)
で行える。 - 遅延セグメント木、セグメント木の詳細は、実装やこちらの記事を参照。
code
339
A - TLD
- 愚直
code
B - Langton's Takahashi
-
ドーナツの表面の様な構造をトーラス状の曲面という。
-
愚直。
-
グリッドで上に行く場合、h-1 する!下に行く場合 h+1 する!
code
C - Perfect Bus
-
minStart := 0
で初期化しクエリを処理する。矛盾が生じたら minStart を辻褄が合う様にインクリメントする。
code
D - Synchronized Players / BFS(グリッド)
-
最短操作回数を求めるので、BFS。プレイヤー二人の位置の組み合わせより、
となる。O(60^2 * 60^2) -
試したプレイヤー二人の位置関係を記録する必要がある。メモは 60^4 と巨大なので、マップだと遅い。 4重スライスで管理する。(マップでもあらかじめサイズを最大数で初期化しておくと、ギリギリ TLE しない。)
code
338
A - Capitalized?
- 愚直
code
B - Frequency
- 愚直
code
C - Leftover Recipes / 資源配分問題
-
料理 A を最大どのくらい作れるのかをとりあえず求める。 全種類の材料の在庫/必要量の min になる。
-
このとき料理 B がどのくらい作れるのかも、全種類の材料の在庫/必要量の min になる。(O(10))
-
料理 A のを最大量~0 作る場合についてこれをやればいいので、
で解くことができる。O(10^6 * 10)
code
D - Island Tour / 円環、imos 法
-
サンプルが弱いので、適当な例を考える。
5 4 1 3 2 5 3
-
各経路は独立で考えても良いので、
(1, 3), (3, 2), (2, 5), (5, 3)
の経路の距離の和について考えればいい。 -
また、経路の始点と終点を入れ替えても距離に影響しないので、
(始点 < 終点)
となる様にソートする。 -
円環を切り開いた数直線を書く。
-
例えば
(2, 3)
の区間に関して、[2, 3) = [s, t])
の間の辺が封鎖されると距離が 4 になり、それ以外=[1, 2) = [0, s)]
または[3, 5) = [t, N)
の間の辺が封鎖されると距離が 1 になることがわかる。image
-
「ある区間内の辺が封鎖されると、ツアーの総距離にある数字が足される」と解釈できる。これは区間更新なので、imos 法で効率化可能。
-
「index i の要素は、
[島i+1, 島i+2)
の辺を封鎖したときのツアーの総距離 (最後の要素は[島N, 島1]
の辺を削除した時の~)
」という長さ N+1 の int スライスを作成することができれば、最小の要素の値が答えになる。 -
全ての要素を 0 で初期化した N+1 の長さの int スライスを作成する。経路でループし、ある区間が封鎖されるとその経路の距離が X になる(ツアーの総距離に X プラスとなる)という情報を int スライスに imos 法で反映していけば、最終的に作りたいスライスの差分配列になる。
code
337
A - Scoreboard
- 愚直
code
B - Extended ABC
-
ランレングス圧縮をし、圧縮後のスライス長が3以下か、文字種の並びが期待する並び(ex, {A, B, C}, {B, C}, {A}, etc..)のいずれかと一致しているかで判定。
-
reflect.DeepEqual()
はスライスの中身の順序も含めて判定してくれる。 -
期待する並びはベタガキで列挙したが、ビット全探索でもいける。
code
C - Lining Up 2 / Linked List、再帰
-
map[前にいる人の番号]自分の番号
を作成しておくと、先頭の人から順に再帰関数を使って辿ることができる。(map から何も見つからない=自分の後ろに誰もいない場合に終了する。) -
Linked Listに更新していき、最後にダンプしてもいい。
code
D - Cheating Gomoku Narabe / キュー、累積和
-
各行各列について、K 目が成立するか調べたい。
-
行・列の長さ K の部分区間について、高速に何回で K 目並べられるかを調べたい。
-
行、列ごとにキューを使ってセルの値を格納していき、
-
o
ならoCount++
-
x
ならq.Clear()
-
.
なら何もしない - 長さが K より多いなら
q.Pop()
して要素を減らし、o
が出てきたらoCount--
する。 - その後 K 以上なら
q.Size()-oCount
で答えの更新を試みる。
-
-
あるいは予め行、列ごとに
x, o, .
の数の累積和を作成しておき、それを元に書く長さ K の部分区間について高速に計算する手もある。。
code
336
A - Long Loong
- 愚直
code
B - ctz
- 愚直に後ろからビットポップ判定
code
C - Even Digits / 整数問題(K 番目のいい数)、N 進数 or 桁 DP(メモ化再帰) + 二分探索
5 進法
-
いい数は5つの数字を使って表現されるので、5 進法と同じ。
-
N 番目の 5 進数の数字は N を5進数に変換したもの、と思いきや N-1 を 5 進数に変換したもの。0 を1番目と数えるので。
strconv.FormatInt(int64(N), 5)
-
実際は
0~4
ではなく0,2,4,6,8
を使っているので、その対応をマップで作成しておき、5進数を変換して出力する。 -
類題: 372 B - 3^A
桁 DP(メモ化再帰)+二分探索
-
を実装して、f(x) = x以下のいい数の個数 AscIntSearch(0, INT_MAX, func(num int) {return f(num) >= K})
として二分探索すればいい。 -
上限以下の条件に合う数の個数の計算は、桁 DP(メモ化再帰) で求められる。
-
var digitDP func (pos, strict int) int // pos: 左から何桁目まで決定済みか、strict: 埋まっている桁が上限のそれと全て一致しているか
を実装すればいい。 - 一段目の関数呼び出しは
{0, 2, 4, 6, 8}
で行い、一桁目が上限のそれと一致しているときはstrict=true
-
-
桁 DP の計算量はとりうる状態と一致する。
O(pos * strict) = O(19 * 2) -
0~INT_MAX(2^63)の二分探索は最大 63 回行われるので、
O(19 * 2 *63) = O(2394)
code
D - Pyramid
-
ピラミッド型は考えづらいので、右側と左側の階段型について考える。
-
ある
が頂点だとして、左側だけを考慮した時の最大の高さは、A_i height(A_i) = min(height(A_{i-1})+1, A_i) -
このように全ての Ai に対して左側だけを考慮した高さを index 0 から出していき、右側だけを考慮した高さを index N から出していく。その後全ての頂点について
min(lHeight, rHeight)
でとりうる高さを出し、最大の高さを記録更新すればいい。
code
335
A - 202<s>3</s>
- 愚直
code
B - Tetrahedral Number
- 0~N の三重ループを回し、それぞれの和が条件に合うかを判定すればマッチする x, y, z の組み合わせを辞書順に列挙できる。
code
C - Loong Tracking
-
移動クエリごとに頭の座標が変化し、それ以外の座標が前のパーツの以前の座標にスライドする。
-
尻尾~頭の順で座標をスライスに格納し、移動クエリの際は
sl = appen(sl[1:len(sl)-1], newCoodinate)
とすれば、O(1)で座標を更新できる。
code
D - Loong and Takahashi / グリッド(応用)
-
出力するパターンを決める。サンプル 1 の渦巻き状にする。
-
スタート位置、一片の長さを渡せばグリッド内の四角の四辺を埋めてくれる関数を実装して、再帰呼び出しをすれば問題が解ける。
- 渦巻きが再帰的な構造になっていることに気づき、どんな関数を実装すれば処理ができるかを考える。
code
334
A - Christmas Present
- 愚直
code
B - Christmas Trees / 数直線
-
R, L に-A し、[R, L]の区間の
ではなくX \equiv A \mod M となる X の数を数えることにする。X \equiv 0 \mod M -
R 以下の最も R に近い
のK_r*M を求め、L-1 以下の最も L-1 に近いK_r のK_{l-1}*M を求める。k_{l-1} -
が答えとなる。R, L-1 が両方ゼロ以上の場合、R, L-1 が 0 を跨ぐ場合、R, L-1 が両方ゼロ以下の場合を考えると、全てでそうなる。K_r - K_{l-1}
code
C - Socks 2 / 組み合わせ、累積和
-
数学的な証明は難しいが、捨てられていない靴下はそのままペアにすることが最善であることが直感的に分かる。
-
片方が捨てられて余っている靴下について、どうペアを組むのが最善かを求める。余りが偶数の場合は、(0, 1), (1, 2), ...をペアにするのが最善。
-
余りが奇数の時に、どの靴下を使わないのが最善かを求める問題になる。奇数インデックスの靴下を削除し、その左右で隣り合う靴下をペアにすることになる。(偶数インデックスだと、削除した靴下を挟んでペアを作らなければいけない組みが1つできてしまい、明らかに最善ではない。)
-
靴下は、直前の靴下あるいは直後の靴下のいずれかとペアになる。index 0 始まりのペア作成と、index 1 始まりのペア作成を考え、それぞれの場合の奇妙さの累積和配列を作る。(As を二つ見て prefSum を一つ埋めるというズレがあるのにループの実装では注意。)
-
使わない靴下を挟んで、左側が前者の累積和の値を採用し、右側が後者の累積和の値を採用することになる。実装は以下の通り。
for i := 0; i<prefSumLen; i++; { oddity := prefSumZeroStart[i] + prefSumOneStart[prefSumLen-1] - prefSumOneStart[i] ans = min(ans, oddity) }
code
D - Reindeer and Sleigh / 貪欲法、累積和、二分探索
-
各クエリに対して、必要なトナカイの少ないソリから貪欲にトナカイを割り当てた方がいい。
-
各ソリに必要なトナカイの数を、昇順にソートする。累積和の配列にすると、
sort.Search(N+1, func (i int) bool { retunr prefsum[i] > X)
で二分探索すると、運べるソリの数が分かる。- 累積和の配列は、長さ N+1 であることに注意。(index 0 に 0 が入っているため。)
code
333
A - Three Threes
- 愚直
code
B - Pentagon / 図形、円環
-
各頂点のインデックスのスライスを作る。頂点 1 のインデックスを 0, 頂点 2 のインデックスを 1, ..., 頂点 5 のインデックスを 5 とする。
-
頂点 a, b の距離は、以下のように計算できる。
a, b = sortIntAsc(a, b) dist := min(b-a, 5-(b-a))
code
C - Repunit Trio / 整数問題(K 番目のいい数)、全探索(全列挙後にソート)
-
条件に合致する数(Repunit Trio)を全列挙することができる。
- Repunit は桁数毎に一種類なので、INT_MAX が 19 桁なことから 19 種類。19^3 は十分列挙可能。
-
rep(i=1~max)(j=i~max)(k=j~max)
のループで、順列を辞書順に列挙できる。
sl := make([]int, 0, pow(19, 3)) // 上限は18桁に設定。19桁だと最後のイテレートでオーバーフローでマイナスになって無限ループ // 問題の制約より、上限ギリギリの巨大なRepUnitはなくても大丈夫。 for i := 1; i <= 111111111111111111; i += pow(10, GetDigits(i)) { for j := i; j <= 111111111111111111; j += pow(10, GetDigits(j)) { for k := j; k <= 111111111111111111; k += pow(10, GetDigits(k)) { sl = append(sl, i+j+k) } } }
-
順列の辞書順が Repunit Trio の小さい順ではないことに注意。
1 + 1 + 1111 > 11 + 11 + 111 -
ソート後に、N 番目の数を出力すればいい。
-
サンプル 3 が使うマックスの Repunit の桁数を教えてくれている。制約で N が小さいことのメリットを教えてくれている。
code
D - Erase Leaves / 木、dfs(ノードカウント)、累積和
-
問題の言い換え:葉ノードが削除可能 => 始点ノードを葉にする => 始点に隣接する N 個のノードの「自身を含めた下位ノードの数」を求め、最もその数が多い隣接ノード以外について、下位ノードを全て削除すればいい。
-
dfsで自身を含む下位ノードの数を記録できる。
-
始点隣接ノードの記録をソートし累積和を作成し、
prefsum[len(prefsum)-2]
をとれば答えになる。
code
332
A - Online Shopping
- 愚直
code
B - Glass and Mug
- 愚直
code
C - T-shirts
-
現在の
RequireAnyT
、RequireLogoT
を記録、各Max
の更新を試みる。洗濯の日はRequire
をリセットする。 -
LogoT を着る日に、
RequireAnyT
及びMaxRequireAnyT
の方も更新することに注意!
code
D - Swapping Puzzle / グリッド(応用)、BFS
-
グリッドの列の入れ替え、行の入れ替えで発生する盤面のパターンは、
となる。行の順列 * 列の順列 = H! * W! -
ではない。マス目の順列 = (H*W)!
-
-
今回の場合は
パターンなので、全探索できる。5! * 5! = 120^2 -
最短手数を求める問題なのでBFS。
- visited map のキーはグリッドを文字列に変換して作る。
- キューアイテムにはグリッドそのものを持たせる。
- 行入れ替えまたは列入れ替えをする直前にコピーを作成し、そのコピーから次のキューアイテムを作る。隣接ノードをあらかじめ隣接リストに保持するのではなく、移動を行う直前に作成することを、グラフを陽にもたないという。
code
331
A - Tomorrow
- 超過した日月を%演算で丸めたら 1WA になったので、よりミスしにくい大小比較を使った。
code
B - Buy One Carton of Milk / 資源配分問題、全探索
-
制約の狭さから全列挙できそう。6, 8, 12 個入りは最大
N/6+1
,N/8+1
,N/12+1
個買える。三重ループして、6*i+8*j+12*k >= N
なら minAns の更新を試みればいい。 -
N が 6, 8, 12 のいずれか割り切れる場合は不必要に個数を 1 を足していたり、そもそも N を大幅に超える個数の組み合わせも試しているが、最小金額を求める問題なので問題ない。
code
C - Sum of Numbers Greater Than Me / 累積和
-
より大きな要素の総和を求めるということで、As をソートして累積和を取れば良さそう。A_i - ただし同じ数字が重複しているときは、
をとっても、自身と同じ数字も加算されてしまっている。prefsum_{N} - prefsum_{i+1} -
map[num]sum
を作り、累積和をイテレートするときにnum := prefsum[i]-[i-1]
として A を復元すれば、自身と同じ数を含まない累積和の値でマップの値を上書きできる。 - 最後に As でイテレートして、マップから答えを取得して出力すればいい。
code
D - Tile Pattern / 二次元累積和、包除原理
-
四角形の面積(含まれる何かの個数などでも可)を考えるときは、右下一点を指定することで
原点-その点
の四角形の面積をだせる関数を実装し、以下のような範囲を考えることで包除原理で目当ての面積が導き出せる。 (これはグリッドバージョンで、座標平面ならf(右上)
を実装する。)imgae この図を書いて思い出してもいい。
-
ans := f(C, D) - f(C, B) - f(A, D) + f(A, B)
- 引数に渡す前に A, B を 1 づつデクリメントするか、C, D を1つづインクリメントすることが、関数 f の実装を考える上で重要。
-
関数 f の実装:ある点と原点を含む四角形に、周期(とそのパーツ、その中に含まれる黒マス)がいくつ含まれるのかは、以下の図のように考えられる。詳細は実装およびコメントを参照。
imgae
-
この手の問題でも実装は綺麗にできることが多いので、こんがらがったらやり方を見直す。
code
330
A - Counting Passes
- 愚直
code
B - Minimize Abs 1
-
場合分けして考える。
-
L <= A_i <= R -
[L, R]
の範囲で、 との距離(差分の絶対値)を一番小さくできるのA_i は、X_i A_i
-
-
A_i < L <= R - ~
は、X_i L
- ~
-
L <= A_i < R - ~
は、X_i R
- ~
-
code
C - Minimize Abs 2 / 整数問題、全列挙、二分探索
-
あり得る x, y の上限が制約より導けそう。
-
D の上限を式変形すると、
。2 * 10^{12} = (\sqrt 2 * 10^6)^2 0 ~ 2*10^6
までの数の二乗は、十分全列挙できる(200 万)。 -
平方数のスライスでループする。現在のインデックス以降の平方数から「現在の平方数 + その平方数が、D を超える平方数」を二分探索する。 minAns の更新を試み、index が 1 以上ならその一つ前の平方数を使った値でも minAns の更新を試みる。
O(200万 * \log 200万)
code
D - Counting Ls
-
ある
o
のマスを固定したとき、同じ列のo
を一つ、同じ行のo
を一つ選ぶということ。あらかじめ行と列のo
の数を記録しておけば、そのような組み合わせがいくつあるかが分かる。あとはマス目でループして足し上げるだけ。- 上記の操作をイメージすると、同じ組み合わせを別のマスを起点にしたカウントで重複カウントすることはない。
-
累積和を使って解くことも可能。しかし上記のやり方の方がずっと簡単なので、立ち止まりたい。
- 自身より前/下の
o
を一つづつ取る組み合わせを考える。そのために行と列のo
の数の累積和をあらかじめ作成。 - L 字の向きが 4 種類なので、4 隅それぞれを起点にマス目のイテレートをする。
- 自身より前/下の
code
329
A - Spread
- 愚直
code
B - Next
- 愚直
code
C - Count xxx / ランレングス圧縮
-
ランレングス圧縮して、圧縮後のスライスでループ。例えば
3_a
だったら、マップに1_a
,2_a
,3_a
を記録。ループ全体で 。最後にマップの長さを数えれば答え。O(N)
code
D - Election Quick Report
- クエリが 20 万個なので、各クエリで当選者を高速に求める必要がある。マップに各候補者の各得票数を記録し、最多得票数とその者を別で記録。各クエリでマップを更新するときに、最多得票数、その者と比較すればいい。
code
328
A - Not Too Hard
- 愚直
code
B - 11/11
- 愚直
code
C - Consecutive / 累積和
-
クエリが 30 万個なので、クエリごとにランレングス圧縮(
)をしていては間に合わない。O(N) -
隣り合う数の個数の累積和を作成しておけば、区間[l, r]のそのような数の個数が高速に求められる。
code
D - Take ABC / Deque or Stack
- 文字列 S を順にDequeに突っ込んでおき、最後に入っている三文字が ABC であれば取り除けばいい。(Stackでもいい)。
code
327
A - ab
- 愚直
code
B - A^A
- 適当に試すと
16^16
が B の上限を超えるので、A の候補を 16 まで全探索すればいい。 - あるいは適当な上限 INT_MAX や B を設定し、A^A が B を超えたら break でも可。
- 繰り返し二乗法を使うと効率いい。
code
C - Number Place
- 愚直(グリッドが極小)
code
D - Good Tuple Problem / 頂点彩色問題、DFS
-
「Xs について、インデックス i とインデックス j は異なる」という情報が複数渡されて、それらが矛盾しないかどうかという様に問題を言い換えられる。これは、グラフの頂点彩色問題である。(N 色を使い、辺で直接繋がったノード同士を違う色で塗り分けられるか。)
-
Xs のインデックス番号をノードとし、違うことが確定しているインデックス同士を辺で結ぶ。そのようなグラフを隣接リストで作成する。
-
Xs を全要素-1 で初期化し、インデックス番号でループ。
Xs[i]
が-1 なら DFS を開始し、未確定のノードに色をつけるか、つけてある色が矛盾しないかをチェックする。詳細は実装参照。
code
326
A - 2UP3DOWN
- 愚直に条件分岐
code
B - 326-like Numbers
- 愚直に全探索
code
C - Peak / 累積和、二分探索
-
入力値がソートされている保証がないので、ソートすること(As)
-
ある x 座標までのプレンゼント総数の累積和を作成できることがわかる。
var psum []struct{x, count int}
-
As でループし、L を
As[i]
で固定、psum を x 座標 R 以上で psum を二分探索し、「その一つ前にある x 座標の累積和(=psum[idx].count
)」-「L より一つ前の x 座標の累積和 (=psum[i].count
)」で minAns の更新を試みる。
code
D - ABC Puzzle / 全探索、DFS
-
グリッドが最大 5*5 なので全探索できそう。
- 各行について をどのインデックスに置くかで
。それが5行なので5*4*3 = 60 。まだ効率化が必要。60^5 -
A,B,C,.,.
の順列と考えてしまうと二つのドットが区別されてしまうので、間違い。
-
- 各行について、1~5 行目はそれぞれどのインデックスに A を置くかを考えると、
通り。A, B, C それぞれについて考え、文字種ごとにインデックスが重複するパターンを一旦許容しても、5! となり間に合う。120^{3}
- 各行について をどのインデックスに置くかで
-
上記のパターンを全探索する。ループのみで書こうと思うとループのネストが N によって動的に変化してしまう。一定程度複雑な全探索は再帰(DFS)で書く。
dfs(char string, grid [][]string) bool
-
NextPermutation()
で「1~5 行目はそれぞれどのインデックスに char を置くか」を列挙し、その通りにグリッドを埋め、文字種をインクリメントして次の再帰へ。char が D ならグリッドが R,C の条件を満たすか判定して bool を返す。 -
NextPermutation()
は以下の様に書くと、オリジナルの順列への処理をループ外に別で書かなくて良くなる。
next := true
for next {
someFunc(sl)
next = NextPermutation(sl)
}
code
325
A - Takahashi san
- 愚直
code
B - World Meeting
-
mtg の時間としてあり得るのは標準時刻で 0~1 時、1~2 時、...23~24 時の 24 パターンと少ないので、全探索できる。
-
mtg の開始・終了時刻を支社の現地時間に直し、それらが両方 9~18 時におさまっている場合、社員数を参加可能人数に足す。
code
C - Sensors / Union Find、DFS or BFS
-
グリッド上で隣接するセンサー同士を一つのグループにまとめるというので、Union Findが使える。
-
Union Find の対象となるのはセンサーのマスなので、一旦それらの座標をスライスに入れる。
-
Union Find の内部配列のインデックス = センサースライスのインデックスということにし、マップ(
map[coordinate{i, j}]index
)を作成する。 -
あとは各センサーマスを始点に BFS や DFS をしていき、Union Find を更新すればいい。ただし、それ以前の BFS、DFS で自身以外がルートになっているマス目はスキップ可能。(すでに他の始点からの探索で探索済みの連結成分に入っている。)
code
D - Printing Machine / 区間問題、優先度付きキュー(ヒープ)
設計
- 数直線上に各製品の開始時間、終了時間を記録する。
- プリント可能な製品は、現在以前に開始しているもの。
- それらの どれにプリントすべきかは、最も終了時間が近い製品である。(すぐプリントできる対象から外れてしまうため。)
- 終了時間を優先度付きキューに入れて、最も喫緊の製品のそれを取り出す方法が良さそう。
- 時刻を 1 づつインクリメントしていると TLE になる && 全く製品が存在しない区間が存在しうる ので、キューが空になった後に次に見るべき製品が存在する時刻まで飛びたい。何らかの形でどの製品まで見たかを保持する必要がありそう。
実装
- 製品の開始時間と終了時間の構造体スライスを、ソートしておく。
- 大外のループの終了条件は、キューが空になりかつ全ての製品の処理が終わっていること。
- 現在時刻から開始する製品の終了時間を全てキューに入れる。どの製品の終了時間まで入れたかのインデックスを保持しておく。
- キューから期限切れの終了時間を全て取り出す。
- キューが空でないなら、喫緊の終了時間を取り出し、ans をインクリメントする。
- キューが空でないなら、現在時刻を 1 インクリメントして次のループへ。キューが空なら、次に終了時間をキューに入れる製品の開始時間まで現在時刻を飛ばして、次のループへ。
code
324
A - Same
- 愚直
code
B - 3-smooth Numbers / 整数問題、全探索、素因数分解
-
素因数分解は
かかるため、N の制約より間に合わない。O(\sqrt N) -
計算すると
、\log_2 10^{18} = 59.7 となるため、2 の乗数を 60 まで、3 の乗数を 38 まで全探索すればいい。\log_3 10^{18} = 37.7 -
オーバフローしないように、
となったときに内側の loop を break する。2^i * 3^j > N -
繰り返し二乗法は
なので、O(log_2 N) O(60*38* (\log_2 60 + \log_2 38))
code
C - Error Correction
- 文字列が等しいか、いずれかから一文字足す(一文字消す)と同じになるか、一文字のみ違うかを判定する頻出問題。ライブラリを用意する。
code
D - Square Permutation / 整数問題(いい数の個数)、平方数、組み合わせ
-
NextPemutation()
で全順列を試すと かかり間に合わない。 逆側の、あり得る平方数を試すことを考える。13! -
であるため、10^6 程度までの数が平方根としてあり得るので、平方数の列挙は間に合う。(10^6)^2 = 10^{12} (13桁) - 実際は、S を最も大きくなる様にソートした数の平方根の平方数までを列挙すればいい。
-
ある平方数が S から作成可能かを高速に判定する必要がある。各桁の数のスライスを降順(または昇順)にソートして一致すれば、作成できるということ。
- ただし今回は
010
で10
を表現することも可能なので、平方数の桁数が S の桁数に満たない場合は、同じになるように0
をアペンドする。 -
(ソートがO(10^6 * 13 * 13 \log 13) 。N は最大の桁数 13。)N * log N
- ただし今回は
- M4 Mac の CPU の処理速度はジャッジサーバーの二倍程度だということに注意。
- 制限時間 4 sec のギリギリをせめる問題は、ローカルで余裕でも注意する。 また、そういう問題はサンプルで上限付近の入力を示してくれていることも多い。
code
323
A - Weak Beats
- 愚直
code
B - Round-Robin Tournament
- グリッドで勝利数を読み込む。
{勝利数、インデックス}
という構造体のスライスを作成し、二つの値を使ってソートする。
code
C - World Tour Finals / Ordered Multi Set、貪欲法
-
各人の点数、解いていない問題の点数セットを記録しておく。各人でループし、自身を除いた点数の最多を超えるためには、解いていない問題を何問解く必要があるかを求める。(得点の高い順に貪欲に解く。)
-
各人の得点の集合、各人の解いていない問題の点数の集合について、挿入、削除、最多の取得を高速に行う必要があるので、Ordered Multi Setが適していることが分かる。
- gostl の
MultiSet
は、Erase(val)
で val と同じ値全てが消えてしまうため、独自のライブラリを使う。
code
D - Merge Slimes / 優先度付きキュー(ヒープ)
-
スライムは可能な限り同じサイズ同士で合成するのが最善。最終的に同じサイズのスライムが二個以上存在するのはあり得ないため。また、最終的に X 種類のスライムが1体ずつ存在する状態になる。
-
サイズの小さなスライムから合成していき、二倍のサイズのスライムがすでにいればその個数に加算、なければ新規に記録。これを繰り返したい。
- 小さな値から処理するということで、サイズの優先度付きキュー(ヒープ) が使える。
-
Ordered Setも思い浮かぶが、こちらは取得と削除の両方で
O(log N)
かかるので不利。 一度処理したサイズはもう処理しなくていいので。
-
実装
- サイズをヒープに追加し、サイズごとの個数をマップで管理する。
- ヒープが空になるまでサイズを取り出し、個数を 2 で割った数を二倍のサイズのマップのバリューに加算。
- 2 で割った余りが 1 ならそのサイズのスライムは最後まで残るので、
ans++
- マップにキーが存在していなかった場合のみ二倍のサイズをヒープに追加。
code
322
A - First ABC 2
- 愚直
code
B - Prefix and Suffix
- 愚直
code
C - Festival / 二分探索
- 現在の日付以降の直近の花火の日付を二分探索。
code
D - Polyomino / ポリオミノ、DFS(全探索)
-
「ポリオミノをどの順番で配置するか」x「ポリオミノを何回 90 度回転させるか」のパターンを全探索する。
O(3! * 4^3) - 複雑な全探索なので、再帰、DFS で書く。
-
各ポリオミノの座標を、0~3 回 90 度回転させたものを予め用意しておく。
var partsMap [3][4][]Coodinate // partsNo => rotateNum => cordinates sorted by most left up
- 座標は、最も左上に近い順でソートしておく。
- 座標は
[2]int
ではなくCoodinate
型にする。多重配列の可読性をマシにするため。
-
実装
- パーツの順番を
NextPermutation()
でループ、再帰関数の中で回転を列挙して再帰。 - 関数の引数に現在の最も左上の空きマスを渡す。空きマスからポリオミノを配置しようとする。
- 元々のパーツの座標は、最も左上の空きマスとのデルタを加算して使う。
- 更に再帰する直前に、最も左上の空きマスを更新する。空きマス発見後に loop break を忘れない。
- 再帰関数の戻り値は、パズルが全て解けたかどうかの bool。再帰呼び出しの際は、戻り値が true だったら true を返し、false なら別の再帰をするために次のループにイテレート。
- パーツの順番を
code
321
A - 321-like Checker
- string で読み込んで桁に分割して比較。
code
B - Cutoff
- ソートして最大と最小を記録、それ以外の合計を記録。足りない点が最小以下か、最大以上かで分岐。
code
C - 321-like Searcher / 整数問題(K 番目のいい数)、DFS(全列挙)
-
質問タブの「321-like Number は有限個であることが示せます。」に注目。
-
よく考えると、最大のいい数は
9876543210
であることが自明。いい数の総数も少なそう。何か全列挙する方法はないか? -
自身より少ない数が存在すれば、それを後ろにくっつけるということをDFSで再帰的に繰り返せば全列挙できる。
-
0 は正の整数ではないことに注意。(正負どちらでも無い。)
-
やってみると分かるが桁 DP+二分探索で解くのは相当困難。
code
D - Set Menu / 二分探索 + 累積和
-
As と Bs をソートすれば、
As[i]
に対してAs[i] + Bs[j] >= P
となる B の数を数えられる。 -
更にソート済み Bs に対して累積和を作っておけば、P を超えない組み合わせで使う B の総和が高速に求められる。
code
320
A - Leyland Number
- 愚直
code
B - Longest Palindrome / 回文
-
len(S)
文字の部分列チェック、len(S)-1
文字の部分列チェック、...とすればいい。
code
C - Slot Strategy 2 (Easy) / 全探索
-
最悪のケースは、 S1,S2,S3 の最後の一文字を使わないと揃わないケース。その場合、M-1 秒、2M-1 秒、3M-1 秒にボタンを押す必要がある。よって、0~3M-1 秒の間のいずれかの 3 点でボタンを押すパターンを全探索すればいい。
- ボタンを押すパターン:
300^3 -
i < j < k
となるように三重ループして、どのインデックスがどのリールに対応するかの 6 通りを試してもいい。(この 6 通りの検証は簡単なので、計算量には影響出ない。) - あるいは、
i, j, k
いずれも 0~3M-1 秒の範囲でイテレートし、一つでも被っていたら continue する。各インデックスはリール 1、2、3 に固定で対応させる。という方法でもいい。
- ボタンを押すパターン:
code
D - Relative Position / キュー
-
人 1 の座標から、関連する人達の座標を求める。さらに座標が判明した人達の情報から、関連する人達の座標を求める。ということを繰り返したい。キューに座標の判明している人の番号を突っ込んでいけばできそう。
-
座標の関係性を隣接リストに格納しておく。その際に、
A => B, +X, +Y
という情報があったら、逆のB => A, -X, -Y
という情報も記録する。 -
キューから座標の判明している人の番号を取り出し、隣接リストから関連する人の情報を取り出す。それらの人の座標がすでにわかっているなら continue。そうでないならその人の座標を確定し、その人の番号をキューに積む。
code
319
A - Legendary Players
- 愚直
code
B - Measure
- 愚直に各インデックスに対して 1~9 が約数かを判定する。全探索。
code
C - False Hope / ビンゴ、全探索
-
マス目が判明する順番は
通りなので全探索可能。9! = 362880 -
マス目に 1~9 の番号をつけ、番号とグリッドの座標のマップを作成する。
-
判明順を
NextPermutation()
で全探索する。判明していく座標を行スライス、列スライス、クロススライスで管理し、”がっかり”したらそれをカウントする。最後までしなかったらそれをカウントする。最後に割合から確率を出す。 -
グリッドのマス目の座標がクロスの位置にあるかどうかの判定方法は、以下の類題を参照。
code
D - Minimum Width / 二分探索(応用)、貪欲法
-
ウィンドウ幅が大きくなるほど、必要な行数が減る(単調性)。M 行に収まるようなウィンドウ幅を二分探索できる。
- min は、最も長い単語のサイズ。max は、単語のサイズの総和+
(N-1)*1
のスペース。 が二分探索の計算コスト\log (max-min)
- min は、最も長い単語のサイズ。max は、単語のサイズの総和+
-
ウィンドウ幅に対する必要行数はどのように判定できる?前から貪欲に単語サイズ+スペースを足していき、ウィンドウ幅を超えたら改行する。
O(N) -
なので現実的。O(log (10^9*N) * N) = O(47 * 2*10^5) -
AscIntSearch()
とDescIntSearch()
はどちらを使うかよく考える。(答えが見つからない場合を除き)戻り値がそのまま求める値にならないケースは、何かがおかしい。
code
318
A - Full Moon
- 愚直
code
B - Overlapping sheets / 座標平面(面積)
-
一つづつ面積を出し加算し、他との重なりを判定してその部分をどうこうする方法は難しすぎる。
-
範囲が
(0~100, 0~100)
に限定されていることから100*100
のグリッドだと考え、長方形の範囲を塗りつぶし、最後に塗りつぶしをカウントする方法でやる。
code
C - Blue Spring / 貪欲法、累積和
-
運賃 Fs をソートし後ろから D 日づつ見ていき、その和が P 円より高ければ周遊パスを貪欲にセット購入していく。ある区間の和を高速に求めたいので、累積和を作成しておく。
-
D 日未満しか残っていなくても周遊パスをセット購入した方が得な場合があるので、その条件分岐が必要なことに注意。
code
D - General Weighted Max Matching / グループ分け、DFS
-
無向辺グラフの辺の重みを記録するときは、
from => to, to => from
の両方にとりあえず必ず入れる。 -
偶数である N 個の要素を 2 個づつの区別のない N/2 グループに分割するパターン数は、N-1 の二重階乗通りである。
(N-1)!! = (N-1) * (N-3) * (N-5) * ... * 1 - 先頭の要素について、ペアリング先が残りの N-1 通り。残った N-2 個の要素についても、先頭の要素について、ペアリング先が N-3 通り。...。となるため。
- 先頭から後ろの要素をペアリング先に選ぶことで、重複数え上げ(グループの区別)を排除できている。
-
奇数である N 個の要素を 2 個づつの区別のない N/2 グループに分割するパターン数は、N の二重階乗通りである。
N!! = N * (N-2)!! -
どの要素を使わないのか * N-1個の偶数個をグループ分けする場合の数
になるため。
-
上記より
であるため全探索が可能。複雑な全探索なのでDFSで書く。O(15!!) = O(2,027,025) -
先頭から後ろの要素をペアリングさせる。使用済み要素をマップで管理し、ペアリング元、先が使用済みなら continue する。詳細は実装参照。
code
317
A - Potions
- 二分探索
code
B - MissingNo.
- ソートしてループ
code
C - Remembering the Days / DFS(グラフ)
-
今回の計算量:
O(N! * N) = O(完全グラフの全経路数 * 探索一回ごとの訪問済みノードの判定) -
今回の全経路数は
。この回数訪問済みノードの読み取り、更新を行うわけだが、マップだと処理全体が 1000ms、スライスだと 200ms だった。マップの読み取り、更新は10! = 3628800 だが、スライスと比べて処理の定数時間が 4, 5 倍程度遅い。O(1)
DFS memo
-
であり、グラフが完全グラフである場合の辺数。N(N-1)/2 = \binom{N}{2} -
「DFS の計算量は
(V: vertexes, E: edges)」と言われるが、これは始点を固定した、バックトラックなしの、DFS の計算量である。O(V + E) - バックトラックとは跡を引き返すということで、再帰呼び出しの直後に訪問済みノードを解除し、別の経路で訪問できるようにすることである。
- バックトラックなしの DFS は連結成分内の全てのノードに訪問することを目的とし、このような解除は行わない。
- バックトラックありの DFS の計算量は問題設定による。今回のような全経路を探索する場合は
となる。N!
code
D - President / ナップサック問題、DP(テーブル)
-
限られたコストで価値を最大化したり、ある価値に到達するための最小コストを求める問題を ナップサック問題といい、DP(テーブル) で解く。
-
各選挙区について、P 人鞍替えさせると(コスト)、Q 票獲得出来る(価値)。過半数票を獲得するための最小コストは?
- 負けている選挙区は、
(X-Y+1)/2
のコストで勝てる。 - 勝っている選挙区は、コストゼロでその票数を取れると考えると楽。(選挙区リストから取り除き、勝敗ラインを過半数から調整する必要がなくなる。)
- 負けている選挙区は、
-
DP テーブル
var dp [][]int
の設計- 行: 何個目の選挙区まで処理したか。大抵の DP で同様。
- 列: 各得票数。
- セル: その状況における最小コスト。
-
セルに求めたい答えと同様の値を入れる。求めたい答えの状況を列で表現する。
- 今回は最小コスト、特に過半数以上の票を獲得している状況のそれを求めたい。
- ゼロ個目の選挙区まで処理した場合、ゼロ票の場合も格納したいので、行・列の長さは 1 を足しておく。
- 各セルは初期値で埋めておく。今回は最小を求めたい(=min をとる処理があるはず)ので、十分に大きな数 INF で埋める。 (最大を求める問題なら逆。)
- INT_MAX や INT_MIN だとオーバーフローの危険がある。
-
(セルの数)O(N * (10^5/2+1))
-
テーブルを埋めるループは一つ前の行(選挙区)の全列(票数)から、次の行の遷移先(あり得る票数)の列に値を埋めていく。
- 遷移先はすでに別の遷移で埋まっている可能性があるので、そのセルの値と今埋めようとしている値の min を採用する。
- 値の入っていない(INF である)セルも処理してしまうが、min をとっている関係で上手くいく。 そこからどこへ遷移しようと、遷移先は元から入っている有効な値か、INF のままになる。
-
過半数以上取る様な遷移をしようとして、DP テーブルの範囲外アクセスになってしまう可能性がある。過半数票の列 (最後列)だけそれ以上以上の票を獲得している状態と定義しても問題の設定上問題ない。DP でよくあるテクニック。
code
315
A - tcdr
- 愚直
code
B - The Middle Day
- 目標の日数から各月の日数を順に引いていく。マイナスになったら「その月」の「終わりからマイナス分を引いた日付」が答え。
code
C - Flavors
- 異なる味同士の美味しさの和の最大は、各味の中の最大の美味しさを昇順に並べた後ろ二つの和。
- 同じ味同士の美味しさの和の最大は、各味の中の美味しさを昇順に並べた後ろ二つの和。
- 上記を求めて maxAns を更新する。
code
D - Magical Cookies / グリッド(応用)
-
行、列ごとに
map[color][]col(row)_indexes
を作成し、削除できる行、列があった場合は、インデックスをもとに逆側のマップから削除する、というやり方が思いつく。これだと各マスの h, w 座標がそれぞれ一箇所に入りそれらが最大一回ずつ削除されるので になる。しかし 400 万回以上ものマップの操作は 2 sec では TLE になるので、マップを使わないやり方を考える。O(2*2000^2) -
色の種類がアルファベットの種類 26 個しかないことに着目する。 行、列ごとの色の数を
make([]int, 0, 26)
のスライスで保持することを考える。行、列の削除できるかどうかの判定は で可能。O(26) -
行の削除の影響を列の色分布に反映する方法を考える。ある回である行が削除されたら、
i:=0~W-1
の列インデックスでループを回す。color := grid[rowIdx][i]
でその列から削除された色がわかるので、その色を列の色分布からマイナスすればいい。-
// (最初の行、列が削除できるかのチェック) * (削除された行、列に対する列、行の処理)O(26(H + W) * (H + W))
-
-
最後にマス目でループし、その行も列も削除されていないものを数えれば答え。
code
314
A - 3.14
- 愚直
code
B - Roulette
- 制約より全探索できそう。各人のベット先を Map(as Set)で保持。X にベットしていた人を、ベット種類数と一緒にスライスに突っ込んでいく。最後に種類数と人の番号でソートして、minCount を超えるまで出力すれば答え。
code
C - Rotate Colored Subsequence
- M(クエリ回数)が最大 20 万なので、スワップ操作を高速にやる方法を考える。色ごとのインデックスのスライスを作りソートする。色ごとに一旦
var toUpdate []struct{idx int, char string}
を作って、それを元に更新する。(末尾のインデックスの文字が先頭のインデックスに移ることにだけ注意。)
code
D - LOWER
-
最終的には、文字は最後の変換が大文字なら大文字、小文字なら小文字になる。ただし最後の変換の後に変更された文字は別。よって最後の変換がどちらか、それ以降に変更されたインデックスはどこかをスライスで保持する。
-
あとは文字の変更操作だけを順にやり、その後除外インデックス以外を順に大文字変換または小文字変換すればいいだけ。
-
if
ブロックとは違い、ループ内のswitch
ブロック内で break してもその switch を抜けるだけであることに注意。
code
313
A - To Be Saikyo
- 愚直。As が一人だけなら、その人は最強であることに注意。
code
B - Who is Saikyo? / DFS、有向グラフ
-
強い人から弱い人に辺が伸びる有向グラフとして表現可能。
-
あとは各人から始まる
DFS
を行い、何人の弱い人を訪問できたかをカウントすればいい。関数は node を受け取り、そこから訪問できた node 数を返す。 -
一度の DFS で同じ人に二度訪問しないために、
visited
を管理する。経路はどうでもよく連結成分を全て訪問できればいいため、呼び出しもとに帰る前に自身の訪問済みを解除するバックトラックはやらない。
code
C - Approximate Equalization 2
-
「数列の最大値と最小値の差が1以下」の場合、数列の要素は 1 種類か 2 種類しかないことになる。
sum%N == 0
ならsum/N
、そうでないならsum/N, sum/N+1
になる。(問題の言い換え) -
後者の場合、
sum/N
はN-(sum%N)
個、sum/N+1 はsum%N
個あることになる。(前者でも結局は同じ式になる。) -
As をソートして、
sum/N
の個数に達していなければ、sum/N
との diff、達していればsum/N+1
との diff をとる。- 小さい数字を小さい値に変更させる方が効率がいいことは自明。
- diff は正負どちらにでもなり得ることに注意。
- diff の正負に応じて positiveCost, negativeCost に加算し、最後にそれらが一致していることを一応アサートし、一方の値を出力すれば答え。
-
「As をソートして Deque に突っ込み最小と最大を取って平均にならすことを繰り返す」等が思いつきサンプルも通るが、やり方に正当性が無いのでこういう当てずっぽうをしない。
code
D - Odd or Even / インタラクティブ問題、合同式、XOR(排他的論理和)
-
数字の和が偶数なら 0、奇数なら 1 ということは、数字の和を mod 2 しているということになる。
-
0, 1 しか数字が存在しないので、XOR を取っていけば同じことができる。
a := 0
b := 1
// 0 + 1 ≡ 1 mod 2
ans1 := (a+b)%2 // 1
ans2 := a^b // 1
-
部分問題から考える。 N=4, K=3 の時。
- K+1 までの数字について、1 つを抜かした K 個のクエリを投げるとする。
- K 個のクエリの答えの和の mod 2 を取ることで、1~K+1 の数字の和の mod 2 が分かる。
- 上記をもとに 1~K+1 文字目の 0, 1 が判明する。(連立方程式の様に考えられる。)
- N がもっと多かったとしても同じ要領で、「確定している K-1 個の数字の番号」+「判明していない数字の番号」でクエリを投げていき、残りの番号の数字も求めていけばいい。
a b c d
1 0 0 1
-------
o o o x ≡ 1 mod 2 // ①
o o x o ≡ 0 mod 2 // ②
o x o o ≡ 0 mod 2 // ③
+ x o o o ≡ 1 mod 2 // ④
--------------------
3a + 3b + 3c + 3d ≡ 0 mod 2
a + b + c + d ≡ 0 mod 2 // ⑤
⑤に例えば④を足すと、以下が求められaの値がわかる。
a + 2b + 2c + 2d ≡ 1 mod 2
a ≡ 1 mod 2
code
312
A - Chord
- 愚直
code
B - TaK Code
- グリッドサイズが小さいので左上を固定した全探索。
O(100^2 * 9^9)
code
C - Invisible Hand / 二分探索
- 昇順ソートした売り手の価格を順に見て、価格をもとに昇順ソートの買い手の希望価格で何人買うか見つける。売り手の人数 >= 買い手の人数なら現在の価格が答え。としたくなるが、これでは以下のケースに対応できていない。
2 3
10 10
11 11 22
=> expexted: 12. 売り手:2人、買い手:1人になる。
-
単純な二分探索(
AscIntSearch()
,DescIntSearch()
)ができないかをまず考える。 -
最小の価格を求めたい。価格を増やして行った時に単調に変化するものは何かあるか?
- => 価格が上がるほど売り手の人数が増え、買い手の人数が減る。二分探索可能。
code
D - Count Bracket Sequences / DP(メモ化再帰)
-
考慮するパターンを相当減らす必要があるのでDPが濃厚。
-
”括弧列”を言い換えると「文字列内の括弧は全て閉じていなければならない」ということ。つまり、
(
が一つ出現すると後で)
をいつか必ず付けなければならない。 -
上記をもとに、「何文字目まで処理済みか」「あと何個
)
を付けなくてはならないか」という状態と、その時のパターン数を考えるメモ化再帰で解ける。 -
「あと何個
)
を付けなくてはならないか」が残りの文字数を超えてしまう場合は場合は枝刈りする。 -
必要以上に(前に十分な数の
(
が無いのに))
を付けてしまうケースもハンドリングする。
code
311
A - First ABC
- 愚直
code
B - Vacation Together / 論理積
-
予定文字列をビットに変換して論理積(両方 true の時だけ true)を取れば良さそうに見えるが、文字列が 100 桁まであり、整数が 64 ビットまでしか扱えないことから、オーバーフローする。
-
文字列は文字列スライスにして、if 文で自分で論理積を撮って更新する。
code
C - Find it! / Functional Graph、DFS(グラフ)
-
各ノードが一つだけ辺を持つ有向グラフのことを、Functional Graphという。
f(node) = next_node
の関数の様な構造をしているため。- Functional Graph は、一つの連結成分内に必ず一つの閉路を持つ。(全てのノードは必ず別のノードに行けるので、連結成分を探索すればいつか必ず同じノードを通る。)
- 一つの閉路と、そこから木が伸びたような構造をしている。
-
var graph []int // node => next_node
の構造に格納できる。
-
上記の法則を知っていれば、順番に適当なノードから探索を始め訪問したノードをスライスに格納し、同じノードを通ったら探索を終了すればいい。
- 通常のDFSでも解ける。ただしノードの数が 20 万と多いため、
でも定数倍が重いと TLE する。O(N) - 訪問ノードを順番に記録する際に、1 つのスライスを使い回す。再帰呼び出しが帰ってきた時に末尾に追加したものを削除する。 再帰呼び出しごとにスライスを複製する方法は遅すぎる。
- 文字列で訪問ノードの順番を記録する方法も考えたが、文字列結合も実はかなり遅い。 文字列は immutable なため、毎回新しいメモリを用意してコピーするため。
code
D - Grid Ice Floor / DFS(グリッド)
-
連結成分の個数を求めたいので、DFS。
-
通常すでに訪れたマスは再訪する必要はないが、滑って通過したマスは、そのマスで停止できるなら再訪の価値あり。
- よって、visited を
0, 1, 2 // NEVER, PASSED, STOPPED
で記録する。優先度の高いものの数字を大きくすると更新処理で便利。(STOPPED を PASSED で上書きしない様に注意。)
- よって、visited を
-
関数で現在の座標、どの方向の移動で訪れたのかを引数で受け取る。PASSED を記録しながら別の方向への移動を試し、別の座標に止まったら、そこが STOPPED 済みでなければ再帰呼び出し。
code
310
A - Order Something Else
- 愚直
code
B - Strictly Superior
-
まずは愚直に全探索する方法を考える。
O(商品二つの全組み合わせの比較 * 全機能の比較) = O(\binom{100}{2} * 100) -
データ列 A がデータ列 B に内包されているかどうかは、両者を map にして mapA の key が全て mapB に存在するか試せばいい。さらに mapB の方が長ければ、"完全上位互換"。
code
C - Reversible
-
map[string]struct
に、文字列と、文字列を反転させたもののうち辞書順の早い方を格納する。同一と見做されるの文字列の種類数は、map の長さ。
code
D - Peaceful Teams / グループ分け、DFS
-
n 人を丁度 k 個の区別のないグループに分ける場合の数 = スターリング数。制約より、最大の数は
S(10, 5) = 42525 -
現在の人をグループに追加するたびに、グループに NG メンバーが含まれていないかを確認する必要がある。計算量の見積りは難しいが、提出してみて時間にかなり余裕があるので良しとする。
-
グループ分けはDFSで行い、最後の人まで処理した時にグループ数が T でなければ ans に加算しない。グループ数が T に達しているときは新規グループの作成はやらない。
-
DFS で既存グループに追加する際は index でループする。 range 文を使ってループ変数
g
にアペンドするとgroupos[i]
に反映されない。-
g
はgroups[i]
と同じ既定配列を参照するが、そちらにアペンドしてもgroups[i]
の length が更新されず、そちらからは追加の要素が見えない。
-
// OK
for i := 0; i < len(groups); i++ {
groups[i] = append(groups[i], idx)
dfs(idx + 1)
groups[i] = groups[i][:len(groups[i])-1]
}
// NG
for _, g := range groups; i++ {
g = append(g, idx)
dfs(idx + 1)
g = g[:len(g)-1]
}
code
309
A - Nine
- 愚直
code
B - Rotate
- 愚直。グリッドのループの際は、イテレーターを i, j ではなく h, w でやると混乱しない。
code
C - Medicine / 二分探索
-
日にちが経つほど、毎日の薬の数は減る。単調性を満たすので日付で二分探索。
-
なので、二分探索で値を検証するたびに N 個の入力データをさらってその日付の薬の合計数を調べることが十分現実的。O(\log 10^9 * 3 * 10^5) = O(30 * 3 *10^5)
code
D - Add One Edge / BFS
-
連結成分 1 から頂点 1 と最も遠いノード、連結成分 2 から頂点 N1+N2 と最も遠いノードを選んで繋ぎ、
dist1 + dist2 + 1
をすれば答え。 -
連結成分内の各ノードの始点ノードとの(最短)距離を求めるのは、BFSで可能。
-
頂点 1 と頂点 N1+N2 から開始する BFS は、それらを最初に同時にキューに載せてしまっても構わない。互いに非連結なので、
visited
を通じて互いに影響を与えてしまうことはない。(多始点 BFS)
code
308
A - New Scheme
- 愚直
code
B - Default Price
- 愚直
code
C - Standings / 小数
-
成功率は小数。「少数は必ず整数にして扱うべき」 くらいで考えた方がいいかも。float64 で扱うと WA。
-
とA_i / (A_i + B_i) の大小を比較するために通分する。A_j / (A_j + B_j) -
ソート関数のコールバックの中で
とA_i * (A_j + B_j) の形にして比較する。A_j * (A_i + B_i)
code
D - Snuke Maze / BFS or DFS
- BFS または DFS すれば解ける。
code
307
A - Weekly Records
- 愚直
code
B - racecar
-
for i:=0; i<N; i++ { for j:=i+1; j<N; j++ }
でループして、Ss[i]+Ss[j]
とSs[j]+Ss[i]
の両方のパターンの回文判定をする。
code
C - Ideal Sheet
-
シート X の範囲を固定し、そこにどうシート A、B を重ねるかという様に考える。
-
シート A、B それぞれについて黒マス存在する範囲から
(minH, minW), (maxH, maxW)
を出し、この範囲がシート X に必ず重なっていないといけない。 -
実装 (詳細はコード参照)
- gridA, gridB の
(minH, minW)
を gridX 内のどこに置くのかでループする。 - gridX の座標を gridA、B の座標に変換するために、ずれのデルタを出す。
- デルタをもとにそれぞれの
(minH, maxW)
を grridX の座標に変換し、それが gridX の範囲外なら continue。 - その後 gridX のセルでループし、セルの値が黒なら gridA, gridB どちらかが重なっていて
#
であることを確認。.
ならどちらも重なっていないか、重なっていても.
であることを確認。
- gridA, gridB の
-
O(Aの最小範囲の左上の位置 * Bの最小範囲の左上の位置 * 答えと一致しているか確認) = O(10^2 * 10^2 * 10^2) - 実際に空のグリッドを用意して塗りつぶし、後で検証とすると効率が悪い。
code
D - Mismatched Parentheses / Ordered Set
-
一番後ろにある
"("
から、それ以降の最も近い")"
までを削除する。これを繰り返せば最終結果まで行ける。 -
"("
の座標、")"
の座標を管理し、"("
を後ろからイテレート、相方の")"
の座標を二分探索で見つけたい。 -
ただし、一度使った
")"
は使えないことから、")"
の座標の管理には二分探索(条件に当てはまる最小要素の特定のみ)と要素の消去が高速に行えるOrdered Setを使う。
code
306
A - Echo
- 愚直
B - Base 2 / 多倍長整数
-
明らかに int64 でオーバーフローするので、多倍長整数を使う。
-
最大の数は
で 63 桁。雑に計算量を見積もってこの桁の数の足し算を N-1 回するとすると、1*2^63 となり間に合う。O(63 * (63-1))
code
C - Centers
- 1~N の num の indexes のマップを作る。その後
struct {Num, MidIdx ind}
のスライスを作って MidIdx でソート、その後 A を順に出力。
code
D - Poisonous Full-Course / DP(テーブル)
- 典型的なDP(テーブル)。ある行は前の行の値からしか遷移しないタイプ。詳細は実装参照。
code
E - Best Performances / Ordered Multi Set
-
topK の要素を保持、更新し、topK の合計を更新していけば良さそう。値によるアクセス、最大値の取得が必要で、値の重複も含むのでOrdered Multi Setを使う。
-
idx 指定で値の更新が行われるので、現在の値を保持する
idxValMap
も用意する。 -
topK の要素が変更された時に、Y または残りの数の最大が topK に入る。なので rest も Ordered Multi Set で用意する。
-
prevVal が rest に含まれるなら rest から(1)、そうでないなら topK から削除。(2)(両方に存在するときは rest から削除して良い。)
- (1) Y が
topK.Worst
より大きいならtopK.Insert(Y); topK.Erace(Worst)
。そうでないならrest.Insert(Y)
- (2) Y が
rest.Best
より大きいならtopK.Insert(Y)
。そうでないならtopK.Insert(Best); rest.Erace(Best); rest.Insert(Y)
- (1) Y が
-
set の Iterator を取得した後に set の要素が削除された場合、Iterator が nil になっている場合があるので注意。
- 無効になっていない場合、
It.Prev(), It.Next()
は更新後のセットの状態を元に正常に動作する。(挿入後の場合も。)
- 無効になっていない場合、
-
gostl ベースの Go の MultiSet の実装では、Iterator を動かすと(重複を含んだ)次の値ではなく、次の種類の値に移動することに注意。
- c++の multiset の Iterator と同様の挙動を必要としない実装方針を考える。
code
305
A - Water Station
- 愚直
B - ABCDEFG
- 累積和
code
C - Snuke the Cookie Picker
- グリッドが小さいので全探索。
- 最も上、下、左、右にある
#
の座標を見つける。その範囲でループして、中に.
があればそれが答え。 - 「左上の左」「左上の上」「右下の右」「右下の下」が欠けている場合もあるので、そこも確認。
- そのマスが存在するのかの範囲外チェック(c.IsValid(H, W))も忘れない!
code
D - Sleep Log / 累積和、二分探索
-
countSleepTimeSum(time int) int
を実装してf(r) - f(l)
すればいい。 -
[]Log{起床時刻、睡眠時間の累積和}
があれば、二分探索で指定の時刻time
以上の起床時刻のLog
を見つけ、diff := 起床時刻-time; ans := 累積和-diff
してログの起床時刻が 時刻time
より超過している分の時間を累積和からマイナスすれば良さそう。- ただし、diff が
Log
以前の直近の睡眠時間以上の場合(=time
が 一つ前のLog
の起床時刻に対応する就寝時刻より前の場合)、diff ではなく直近の睡眠時間をマイナスする必要がある。よって、Log{起床時刻、睡眠時間の累積和、直近の睡眠時間}
とする。
- ただし、diff が
code
E - Art Gallery on Graph / ダイクストラ法(もどき)
-
var guarded []int
に、頂点 Idx に警備員が残り体力いくつで訪問したかを記録し、BFSしていく方法が思いつく。別の始点(別の警備員がいる頂点)からの BFS では、より大きな残り体力で到達済みのノードをスキップすればいい。- しかし BFS の計算量は
であり、上記の効率化をもってしても最悪計算量はO(N*M) になり厳しい。(体力の多い警備員から順に BFS しても TLE した。)O(K*M*N)
- しかし BFS の計算量は
-
実はダイクストラ法と同様の手順で求められる。-1 で初期化した
var fixedGuarded []int
と、{node, remainHealth}
を入れる優先度付きキュー(ヒープ) を用意し、ヒープの中にある最大体力のノードを取り出し確定、隣接ノードの{node, remainHealth}
をキューに追加すればいい。- ダイクストラが成り立つ理由と同じ。最大体力を持つノードを確定させた後に、それより大きい最大体力でそのノードに到達することが起き得るとする。その場合、確定させたノードの体力より大きい体力を持つ別のノードから到達しているはずであり、体力の大きいノードから処理するという前提と矛盾するため。
-
ダイクストラの計算量は
O((V + E)* \log V) - 各辺ごとに 1 つの頂点がヒープに追加される =>
O(E \log V) - 各頂点が 1 回以上(最大 E 回ではある)ヒープから取り出される(確定済みの場合はその後無視される) =>
O(V * \log V)
- 各辺ごとに 1 つの頂点がヒープに追加される =>
code
304
A - First Player
- minA, minAIdx を見つけて、
ans := append(As[minAIdx:N], As[0:minAIdx])
code
B - Subscribers
- 愚直。予め桁数がわかっていれば、下 N 桁の切り捨ては一旦文字に変換した上でこうできる:
str := str[:2] + "00" // 4221 => 4200
code
C - Virus
- N の小ささから、各座標間の距離を全探索可能。
- グラフを作る。距離の二乗が D の二乗以下の 2 点を隣接リストに記録していく。
- 最後に頂点 1 からのDFSで、visited(=infected)を記録していく。
code
D - A Piece of Cake / 二分探索
-
の制約から、X、Y 座標ごとの処理は間に合わない。また、最大の苺を持つ X と Y の交差するマスが最大数の苺を含んでいる保証は全くない。逆側の、苺の座標(W,H≤10^9 )から考える。N≤2×10^5 -
苺の X 座標、Y 座標から、それを超える A、B を二分探索すれば、何列目、何行目のマスかが分かる。(右側の X 座標、上側の Y 座標がマスを代表していると考える。)それを
map["A_B"]count
に記録し、最後に最も少ないカウント、大きいカウントを取ればいい。 -
ただし、
len(m)
がマス数、(A+1)*(B+1)より少ない場合苺ゼロのマスが存在するので注意。
code
E - Good Graph / Union Find
-
グラフの連結成分を管理する必要があるので、グラフをUnion Findとして格納する。
-
は連結してはならない => x と y のルートは連結してはならないと言い換えられる。x_i, y_i - これらを
ngMap[int]map[int]struct
で管理する。 - 常に若い番号の node が第一キーになる様に x と y を昇順スワップすると、メモリ効率がいい。
- これらを
-
クエリを処理するときに、(昇順スワップした)u と v のルートを求め、それが
ngMap
に存在する組み合わせかどうかで辺で連結させても良いかどうか判定する。
code
303
A - Similar String
- 愚直
B - Discord
- 全ての組み合わせのパターン数を求める。その後不仲ではないことが確定している組み合わせをマップに格納する。(マップのキーは昇順ソートした番号から生成する。)前者から後者を引いたものが答え。
code
C - Dash
- アイテムの座標をマップに格納。現在の体力を記録更新しながら移動クエリを順に処理。アイテムを使う場合はマップから削除。
code
D - Shift vs. CapsLock / DP(テーブル)
dp[i][j] // i: i"番目"の文字まで処理した. j: j=0: CapsLock OFF, j=1: CapsLock ON. val: 最短秒数.
- 以下の遷移の仕方の min を取ってテーブルを更新。
- CapsLock が反対の状態から、
- CapsLock を反転して通常入力(or シフト入力)
- シフト入力(or 通常入力)して CapsLock を反転
- CapsLock が同じ状態から、
- CapsLock を反転して通常入力(or シフト入力)、その後 CapsLock を反転
- 通常入力(or シフト入力)
- CapsLock が反対の状態から、
code
E - A Gift From the Stars / キュー
- 与えられるグラフは木であり葉が必ず存在する。適当な葉を見つける。その葉は星の葉であり、そこから遷移できるノードは必ず星の始点である。
- その星の頂点から遷移できるノードは全て星の葉である。その星の葉から遷移できるノードは全て別の星の葉である。
- 星の葉をキューに積み、星の視点を見つけ記録し、見つかった別の星の葉をキューに積む。その過程で
別の星の葉 - 今見ている星の葉
の辺をグラフから切る。- 高速に辺を切るために、グラフの隣接リストの要素は Map で用意しておく。
-
// 全ての星の葉が一度づつキューに積まれる。O(N)
code
Discussion