tookunn’s diary

主に競技プログラミング関係

AtCoder Beginner Contest 174 C - Repsept

問題

atcoder.jp

考察

7, 77, 777, ...の約数を列挙して、Kの約数を列挙して何か規則性があるのかとか探していたが
分からず。

数列をAとし、i番目の要素をA[i]とする。
Kの倍数ということは
A[i] mod K = 0ということ。

A[i + 1] = A[i] * 10 + 7なので、A[i]はmod Kをした値のまま扱えそう。

mod Kをした値だと値の種類は高々K個になる。
なので、AのK番目以降の要素は必ず既に出現した値になる。

既に出現した値以降は同じ順番で値が繰り返される。
なぜならA[i + 1] = A[i] * 10 + 7だから。

長さKの数列A(各要素にmod K適用されている)を作って
A[i] mod K = 0になるまでAをなめていく。

京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200) D - Happy Birthday! 2

問題

atcoder.jp

考察

数列Aから異なる部分数列B,Cを探してB,Cそれぞれの総和のmod200が同じものを出力する問題。

重要な点としては

  • 数列Aから見つかる部分数列は2^N-1通り
  • 部分数列の総和のmod200は200通り
  • 数列Aの長さがある長さ以上になったら、総和のmod200が被る部分数列が存在する

数列Aから見つかる部分数列は2^N-1通りあるので、単純に部分数列を全探索するのは無理そう。

部分数列は2^N-1通りあるが、その部分数列の総和のmod200は0~199の200種類のため
総和のmod200が同じものは結構ありそう。

数列AのN個の要素すべてを見なくても良さそうだが、見る必要がある要素、必要がない要素はどう判断するか。

部分数列の総和のmod200が必ず被るようになる数列を考える。

数列Aから見つかる部分数列は2^N-1通り存在し、部分数列の総和のmod200についてはそれぞれ異なる場合でも高々200通りのみ。

つまり、部分数列が201通り以上存在する場合は、部分数列の総和のmod200が被るものが必ず存在するということ。
(こういうのに鳩ノ巣原理という名前がついているらしい)

2^N-1が201通り以上になる数列には必ず総和のmod200が被る部分数列が存在するので、
数列Aの長さNが8以上の場合は必ず被る部分数列が存在する。

N >= 8の場合は数列Aの先頭から長さ8までの要素のみを見て、被る部分数列を探索する。
N < 8の場合は数列A全体の要素を見て、被る部分数列が存在するのか、存在するなら被る部分数列を探索する。

最大でも長さが8の数列の部分数列を列挙すれば良い。
8個(もしくは8個以下)の要素をそれぞれ部分数列に含める、含めないを探索していくので最大2^8-1(255)通りの部分数列を列挙して
総和のmod200を取りつつ、既に列挙した中に総和のmod200が同じものが存在していれば、該当する2つの部分数列を出力する。

AtCoder Beginner Contest 188 D - Snuke Prime

問題

atcoder.jp

考察

1 \le a_i \le b_i \le 10^9となっていて、区間として範囲が大きいので
いもす法という手法を使って、単純に各区間の増減の累積和を取ることができないことが分かる。

最初は各区間について a_i, b_iを一組としてまとめて、うまくソートなりなんなりをすれば良さそうと考えていたが
そこからまったく分からなかった。

公式解説によると
区間 a_i, b_iをまとめて考えるのではなく、 a_i, b_iを別々のものとして扱い、
いもす法の発想を少し応用した工夫をすることで解くことができる。

f:id:tookunn:20210503192521p:plain

こんな感じに区間を直線で表すと
 i日目を1からなめていったときにいずれかの区間 a_i b_iと重なるまで
払う料金は一定で、 a_i b_iに出くわしたときに料金が変動することが分かるので
いもす法っぽく a_i日目に +c_i円、 b_i + 1日目に - c_i円という料金が変動する情報を持っておけば良い。

あとは料金が変動する情報を日にちの昇順になめていって、 min(変動前の料金, C) \times 日数で料金を計算していけば良い。

ソースコード

キーでforループを回したときに順序を持たせる必要があったので、MapはHashMapではなくTreeMapにした。
よく分からないが、HashMapだとキーの一意性をハッシュで管理しているため、キーの順序は考慮されないっぽい。
atcoder.jp

ZONeエナジー プログラミングコンテスト “HELLO SPACE” C - MAD TEAM

問題

atcoder.jp

考察

基本方針は
5種類すべての能力がチーム全体として X以上にできる3人の組み合わせが存在するかを二分探索で探っていく。

3人のチーム全体の各能力は以下の通り、3人の能力の最大値となる。
 A_{max} = max(A_1, A_2, A_3)
 B_{max} = max(B_1, B_2, B_3)
 C_{max} = max(C_1, C_2, C_3)
 D_{max} = max(D_1, D_2, D_3)
 E_{max} = max(E_1, E_2, E_3)

そして、チームの総合力は以下の通り、チーム全体の各能力の最小値となる。
 min(A_{max}, B_{max}, C_{max}, D_{max}, E_{max} )

各能力において、3人の内いずれかの能力が X以上であれば、チームの総合力として X以上になることが確定する。
例えば、パワーの場合は
 A_2のみ X以上であれば、他の A_1,A_3 Xより小さいということなので、
 A_{max} = A_2となり、 A_{max} X以上の値になるということである。
あとは他の能力についても同様に言える。

これらのことから Xについて二分探索出来そうなことが分かる。

あとは任意の3人の組み合わせで
5つある各能力のチーム全体の値が X以上にできるかを確認するのだが、
各能力について、 X以上にできるか出来ないかの01の状態を持つことで確認することができる。

N人の各メンバーについて、各能力について X以上にできる、できないの状態を5桁のビットで持ち、できる場合は1、できない場合は0とする。
(例えば01010だと、スピードと知識については X以上にすることできる)
なので3人のビット状態を合わせて11111にすることが出来れば、チームの総合力を X以上にできる。

単純にN人のメンバーから3人分のビット状態を合わせて確認すると O(N^3)で間に合わないが、
ビットの状態数は 2^5程度しかなく、同じビット状態のメンバーを選んでも、合わせたビット状態が変化せず無駄になってしまうので
N人それぞれにビット状態を持たせるのではなく、ビット状態のみに着目して
特定のビット状態にできるメンバーがいるかどうかを情報として持つ。
(具体的にはビット状態をSetで管理するようなイメージ)
これで高々 O((2^5)^3)程度の計算量で3人分のビット状態を合わせて確認することができる。

そして、この3人分のビット状態から最終的に各能力を X以上にできる3人の組み合わせが存在するか(11111であるか)を確認して
二分探索を行っていく。

ZONeエナジー プログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ

問題

atcoder.jp

考察

重要な点は

  • 文字列反転のコストをどう工夫するか
  • 連続した2文字が同じ文字の場合の削除のコストをどう工夫するか

文字列反転については
文字追加の操作を行いながら、反転しているかどうかの状態を持っておき
反転している場合は文字列の先頭に文字を追加し、反転していない場合は末尾に文字を追加することで解決できる。

例えばozRnonnoeが入力の場合、
文字列反転を工夫しないで操作を行うと
zononnoe
になる。
反転を工夫して同様の操作を行うと
eonnonoz
になる。

このzononnoeeonnonozは反転しているだけの文字列同士であることが分かる。

削除のコストについては
文字追加操作後の文字列Sから一文字ずつ新たな文字列Tに文字を追加していく。

Sの反転状態を見て、反転している場合は末尾から、そうでない場合は先頭からTへ文字を追加する。
そのSからTへ文字を追加する際に、追加しようとしている文字と現在のTの末尾の文字が同じ場合は
文字は追加せず、Tの末尾の文字もTから削除することで、同じ文字が隣り合うことがない文字列を作成することができる。

ZONeエナジー プログラミングコンテスト “HELLO SPACE” B - 友好の印

問題

atcoder.jp

考察

コンテスト本番では上る高さを二分探索で決めて、UFOからその上った高さの位置までの直線を
一次関数y = ax + bの式に当てはめて、各iについて、x = d[i]の時にh[i]以上かどうかで探索していた。
これだと実装が複雑になるし、バグも出やすいので悪手だった。

公式解説では
H - D / (D - d[i]) * h[i]のmaxを求めていた。

www.youtube.com


発想的には一番高い遮蔽物の上部を通るような直線をタワーとUFOの間に引くと
遮蔽物とUFO間、タワーと遮蔽物間、タワーとUFO間で直線ができる。

遮蔽物とUFO間の直線を斜辺とした直角三角形
タワーとUFO間の直線を斜辺とした直角三角形が相似であることを利用する。

(D / D - d[i]) * (H - h[i])=上った高さとUFOの高さとの差 なので
UFOの高さ - (上った高さとUFOの高さとの差)で上った高さが求まる。
それを各iについて行ってmaxを取る。

f:id:tookunn:20210502131658p:plain

追記

この考え方がわかりやすい



反省点

タワーと一番高い遮蔽物とUFOの間に直線を引くところまでは本番でも
思いつくことができたが、そこからの数学的発想や知識を使ったところで
迷走してしまった。

ソースコード

二分探索

atcoder.jp

想定解法

atcoder.jp

AtCoder Beginner Contest 190 D - Staircase Sequences

問題

atcoder.jp

考察

まず、公差1の等差数列の総和の特性を見つけるために
公差1の等差数列の総和を求める式を考える。

総和をN、初項をA、項数をLとすると
 N = \frac{1}2 \times L \times (A + A + L - 1)
 N = \frac{1}2 L (2A + L - 1)
扱いやすいように両辺に2を掛けて
 2N = L (2A + L - 1)となる。

この式から
2Nは、Lまたは(2A + L - 1)で割り切れる値だということが分かる。(つまり約数である)

分かりやすくすると
 2N = X \times Yという式で表すことができて、 2NXYを約数に持ち、
 X = L, Y = (2A + L - 1)または X = (2A + L - 1), Y = Lであるということ。

ここで Lさえ分かれば 2Nから (2A + L - 1)も求めることができて良さそうなので
 L \sqrt{2N}まで全部試していく。
 2Nは偶数なので、X Yのどちらかは偶数であり、 2Aが偶数であることを
確かめていき、OKならカウントしていく。