SRM611-613 Div1E

TOEICしてきたよ なんとなくセンター試験を思い出す

・SRM611 Div1E LCMSet

数列Sから1個以上の数を選んでlcmをとったときに現れる全ての数を集めた集合をLCM(S)と書く.数列AとBが与えられるのでLCM(A)=LCM(B)かどうか判定せよ,という問題.

例えばX=[2,3,4,12]のときLCM(X)={2,3,4,6,12}だが,X=[2,3,4]としてもLCM(X)={2,3,4,6,12}となる.このように数列Xにはそれを取りのぞいてもLCM(X)が同じままであるような「不要」な数が存在する.不要な数というのは他の数のlcmで作れる数のこと(12は3と4のlcmで作れる).こうしてA,Bを「圧縮」するとLCM(A)=LCM(B)⇔A=Bであるから簡単に判定できる.

※Editorial等にないので⇒の証明を試みる.Aに含まれていてBに含まれていないような数xが存在したとする.Bに含まれる数のlcmでxが作れないならLCM(B)にxは含まれないのでLCM(A)=LCM(B)に反する.したがってBに含まれる数y_1,...y_kのlcmでxが作れることになるが,圧縮済みのAにxが含まれているからAにy_1,...y_kのうちすくなくとも1つは含まれていない.その数をxとして同じ議論を繰り返すといくらでもxが小さくできて矛盾.よってLCM(A)=LCM(B)⇒A=B

 ・SRM612 Div1E EmoticonsDiv1

はじめ1文字だけ入力されている.これに対し1文字消す,現在入力されている文字列をコピーする,コピーされている文字列をペーストする,の3つの操作が出来るとき最短何回の操作でちょうどx文字入力できるか,という問題.

(何文字入力されているか,何文字の文字列をコピーしてあるか)を頂点とするグラフをかんがえれば最短経路問題になるのでBFSなどしてやる.

・SRM613 Div1E TaroFriends

猫がx軸上に並んでいる.猫たちは合図と共にちょうどXだけ左右好きな方にうごく.このとき最も左にいる猫と最も右にいる猫の距離の最小値はいくつか,という問題.

全てのペアについて,それが端の猫になる場合があるかどうか調べて(これは上手く他の猫をこの二匹の間に収められるかで判定できる)最小値を求めるというのが想定だったっぽい.しかし僕は全探索が思いつかず"dp[i][j][k]=i番目までの猫のうち最も左にいる猫が(k=1なら右,k=0なら左に進んだ)j番目の猫であるときの端の猫同士の距離の最小値"というDPをやってゴリ押してしまった.