2020年 6月 14日 / 15日
まえがき
はじめてのCodeforces
健康管理
何した
具体的に
今日解いた問題
ABC170 E- Smart Infants
multisetから、ある値xを一個だけ消したい時は,s.erase(s.find(x)) 配列の要素の先頭の値は(配列の名前をsとすると）
*(s.begin())
末尾の要素は
*(s.rbegin())
で取得出来る。
Codeforces Round #599(Div.2) A.Maximum Square
- [全探索]
辺の長さ1 ~ 1000が作れるか全部見てあげても間に合う。全体の計算量はO(KN2) <= 107かな 各辺の長さLについて、N枚の板がL以上かを見る。その枚数がL以上なら辺Lは作れる。
Codeforces Round #599 (Div. 2) B2. Character Swap(Hard Versiion
- [操作、整列]
操作が2n回まで出来るってことは、ある文字を希望通りの位置に持ってくることは出来る。
s == t に出来る条件は、各文字'a' ~ 'z' について、其の文字が偶数回ずつ使われていること。 後はsとtの1文字目から順にs[i]に合わせるって感じで構成していけば行けるっぽい。
例えばs[i] == 'a'だったら、 t[i] も'a'にしたい。
で、s[i]より後ろを見て、'a'を見つける。なかったらt[i]より後ろを見て'a'を見つける。
s[k]に'a'があったら、t[i]とs[k]をswap
t[k] に'a'があったら、s[i+1]とt[k]をswap。
後、s[k]とt[i]をswapすることで構成していく。
Codeforces Round #599 (Div. 2) C. Tile Painting
- [割った余り？,実験,最大化]
なんか、手元で実験してたら、N=6の時1、8の時2,10のとき1,35のとき1ってなった。
で、よく分からないけどN素数ならNが答え
Nが素因数一種類で構成されているならその素因数が答え。(N = 39なら3が答え)
Nが2種類以上の素数で構成されているなら答えは1
これでAC出来ました。 で、以下は落書きです。
とりあえず、Nが素数の時は、Nの除数で1を超えるものはNしかないのですが、N枚の板について、板間の距離がNである2枚というのは当然存在しません。（最大距離はN-1)。
よって、Nが素数であるときはN色で塗り分けることが出来る。（計算量は素数判定にかかるコストなのでO(√N)
以下はNが素数じゃないときについて考えよう。
まず、Nが一種類の素因数だけで構成されているとき(N = pk)(pは素数、kは整数)
このとき、Nの除数（約数？）はp1,p2,...,pkです。
まず、1マス目を色1で塗って、距離pのところも1で塗ります。
次に、1マス目から距離p2も色1で塗ることをかんがえます。すると、実は距離がp2の板というのは、距離pの板を色１にした段階で勝手に1で塗られています。
同様に、p3,...,pkについても距離pの板を1で塗った操作により適切な色に塗り分けられています。
同じ手順を2マス目の板(今度は色2で塗る)、3マス目の板,...,p枚目の板(1枚目の板から距離がpの板はp+1枚目の板です)についてやることで、N枚の板をP色で塗り分けることが出来ます。
次に、Nが二種類以上の素因数で構成されている場合をかんがえます。(例N=6, N = 10, N =35 など)
素因数に2が入っている場合からまず見ていきます。
N = 2 * 7 ( = 14) とします。
まず、1枚目を色1で塗り、距離2のところを全部色1にします。
次に、1枚目の板から距離が7のところを塗ります(マス8)。これは,2と7が互いに素なので（かは知らないけど)必ず同じマスになりません。
ってことは、マス8から距離2のところを見ると、マス6も色1で濡れます。
ってことは今度はマス4,2, 10 , 12 ... も色１で濡れるって感じで、結局一種類の色でしか濡れないな〜ってなる。
証明はわからないけど、
2や7に対応するのをa,bとして
ax+by = 1 となるようなx,yの組が存在するから。って感じでやるのかな？(拡張ユーグリッドとかっていうんだっけ？）
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
