AtCoder Beginner Contest 174 C - Repsept
問題
考察
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
問題
考察
数列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
問題
考察
となっていて、区間として範囲が大きいので
いもす法という手法を使って、単純に各区間の増減の累積和を取ることができないことが分かる。
最初は各区間についてを一組としてまとめて、うまくソートなりなんなりをすれば良さそうと考えていたが
そこからまったく分からなかった。
公式解説によると
各区間のをまとめて考えるのではなく、を別々のものとして扱い、
いもす法の発想を少し応用した工夫をすることで解くことができる。
こんな感じに区間を直線で表すと
日目を1からなめていったときにいずれかの区間のかと重なるまで
払う料金は一定で、かに出くわしたときに料金が変動することが分かるので
いもす法っぽく日目に円、日目に円という料金が変動する情報を持っておけば良い。
あとは料金が変動する情報を日にちの昇順になめていって、で料金を計算していけば良い。
ソースコード
キーでforループを回したときに順序を持たせる必要があったので、MapはHashMapではなくTreeMapにした。
よく分からないが、HashMapだとキーの一意性をハッシュで管理しているため、キーの順序は考慮されないっぽい。
atcoder.jp
ZONeエナジー プログラミングコンテスト “HELLO SPACE” C - MAD TEAM
問題
考察
基本方針は
5種類すべての能力がチーム全体として以上にできる3人の組み合わせが存在するかを二分探索で探っていく。
3人のチーム全体の各能力は以下の通り、3人の能力の最大値となる。
そして、チームの総合力は以下の通り、チーム全体の各能力の最小値となる。
各能力において、3人の内いずれかの能力が以上であれば、チームの総合力として以上になることが確定する。
例えば、パワーの場合は
のみ以上であれば、他のはより小さいということなので、
となり、が以上の値になるということである。
あとは他の能力についても同様に言える。
これらのことからについて二分探索出来そうなことが分かる。
あとは任意の3人の組み合わせで
5つある各能力のチーム全体の値が以上にできるかを確認するのだが、
各能力について、以上にできるか出来ないかの01の状態を持つことで確認することができる。
N人の各メンバーについて、各能力について以上にできる、できないの状態を5桁のビットで持ち、できる場合は1、できない場合は0とする。
(例えば01010だと、スピードと知識については以上にすることできる)
なので3人のビット状態を合わせて11111にすることが出来れば、チームの総合力を以上にできる。
単純にN人のメンバーから3人分のビット状態を合わせて確認するとで間に合わないが、
ビットの状態数は程度しかなく、同じビット状態のメンバーを選んでも、合わせたビット状態が変化せず無駄になってしまうので
N人それぞれにビット状態を持たせるのではなく、ビット状態のみに着目して
特定のビット状態にできるメンバーがいるかどうかを情報として持つ。
(具体的にはビット状態をSetで管理するようなイメージ)
これで高々程度の計算量で3人分のビット状態を合わせて確認することができる。
そして、この3人分のビット状態から最終的に各能力を以上にできる3人の組み合わせが存在するか(11111であるか)を確認して
二分探索を行っていく。
ZONeエナジー プログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ
問題
考察
重要な点は
- 文字列反転のコストをどう工夫するか
- 連続した2文字が同じ文字の場合の削除のコストをどう工夫するか
文字列反転については
文字追加の操作を行いながら、反転しているかどうかの状態を持っておき
反転している場合は文字列の先頭に文字を追加し、反転していない場合は末尾に文字を追加することで解決できる。
例えばozRnonnoeが入力の場合、
文字列反転を工夫しないで操作を行うと
zononnoe
になる。
反転を工夫して同様の操作を行うと
eonnonoz
になる。
このzononnoeとeonnonozは反転しているだけの文字列同士であることが分かる。
削除のコストについては
文字追加操作後の文字列Sから一文字ずつ新たな文字列Tに文字を追加していく。
Sの反転状態を見て、反転している場合は末尾から、そうでない場合は先頭からTへ文字を追加する。
そのSからTへ文字を追加する際に、追加しようとしている文字と現在のTの末尾の文字が同じ場合は
文字は追加せず、Tの末尾の文字もTから削除することで、同じ文字が隣り合うことがない文字列を作成することができる。
ZONeエナジー プログラミングコンテスト “HELLO SPACE” B - 友好の印
問題
考察
コンテスト本番では上る高さを二分探索で決めて、UFOからその上った高さの位置までの直線を
一次関数y = ax + bの式に当てはめて、各iについて、x = d[i]の時にh[i]以上かどうかで探索していた。
これだと実装が複雑になるし、バグも出やすいので悪手だった。
公式解説では
H - D / (D - d[i]) * h[i]のmaxを求めていた。
発想的には一番高い遮蔽物の上部を通るような直線をタワーとUFOの間に引くと
遮蔽物とUFO間、タワーと遮蔽物間、タワーとUFO間で直線ができる。
遮蔽物とUFO間の直線を斜辺とした直角三角形
タワーとUFO間の直線を斜辺とした直角三角形が相似であることを利用する。
(D / D - d[i]) * (H - h[i])=上った高さとUFOの高さとの差 なので
UFOの高さ - (上った高さとUFOの高さとの差)で上った高さが求まる。
それを各iについて行ってmaxを取る。
追記
この考え方がわかりやすい
昨日のBに悩んでた人は、ひっくり返すと計算しやすいかも。
— chokudai(高橋 直大)🍆 (@chokudai) 2021年5月2日
7進むと5増えます。10進むといくつ増えるでしょう? pic.twitter.com/8X2wx0Aty2
反省点
タワーと一番高い遮蔽物とUFOの間に直線を引くところまでは本番でも
思いつくことができたが、そこからの数学的発想や知識を使ったところで
迷走してしまった。
AtCoder Beginner Contest 190 D - Staircase Sequences
問題
考察
まず、公差1の等差数列の総和の特性を見つけるために
公差1の等差数列の総和を求める式を考える。
総和をN、初項をA、項数をLとすると
扱いやすいように両辺に2を掛けて
となる。
この式から
は、またはで割り切れる値だということが分かる。(つまり約数である)
分かりやすくすると
という式で表すことができて、はとを約数に持ち、
またはであるということ。
ここでさえ分かればからも求めることができて良さそうなので
をまで全部試していく。
は偶数なので、とのどちらかは偶数であり、が偶数であることを
確かめていき、OKならカウントしていく。