SRM691Div2反省

反省や解法のメモを書いていきます．


300:

0~9の数字の書いてあるカードと+の書いてあるカードがそれぞれ何枚かと1個のカウンターがある．ある順番でこのカードを取っていき，以下の操作を行う．

    

  • 数字のカードなら，その数字とカウンターの数字の差の絶対値の分だけペナルティを加算する
    • 

  • +のカードなら，カウンターの数字を1進める
    • 

カードの構成が与えられたときペナルティを最小にするための順番を返せ．

直感的に解ける問題でした．他の人のコードをちらっと見た限りでも，みんなだいたい同じ解き方で，

数字のカードを小さい順に並べ，+の数を増やしながら，+が足りなくなるまでペナルティが0になるように数字を配置していく

という感じのものでした．僕の解法も同じでしたが，charとintの変換に苦労するなど初心者感満載な時間のかけ方をしてしまいました……

500:

0~n-1のn個の頂点とi,a[i]間の辺をもつグラフが与えられる．新たに頂点nを追加し，頂点の部分集合Mに対して，Mに属するすべての頂点iについて，辺i,a[i]を削除して，辺i,nを追加する．この操作のあと，すべての頂点が繋がっているような部分集合Mの数を返せ．

僕は解法が思いつかず．Div1だと「0から1のパスが存在するようにする」問題だったようですが，Div2では「すべての頂点が繋がっている」ようにする問題でした．Div1のほうが簡単にみえる……僕に理解できた解答は，ループから一つ頂点を選んでも連結のままだが，ループ以外から頂点を選ぶとその頂点が切断されるということに着眼して，

    

  1. 各ループから少なくとも一つずつ頂点を選ぶ
    2. 

  2. ループに含まれない頂点は選んでも選ばなくても良い 
    3. 

という条件を満たすような選び方の総数を求める

というものでした．いやぁ難しい．精進します．

900:

整数 nを割り切らない正の整数のうち二番目に小さいものを S(n)とおくとき， \sum_{i=1}^{n}S(i)を返せ．

いたってシンプルな見た目の問題で，解を出すだけならどちゃくそ簡単ですが，nが1,000,000,000まで大きくとれるので，時間を短くする工夫が必要でした．他の人のコードを見ると，どうやら「n=1,000,000 * iの答えを配列でとっておき，n=1,000,000 * i + rのときはrの分だけ計算する」ことで計算量をO(r)くらいに減らした解答が多かったです．なるほどローカルなら時間制限なしで走らせられるのでそういう解き方もできるんですね．勉強になります．真似しようとは思いませんが．うまいと思ったのは，それぞれのnに対してS(n)を計算するのではなく，逆に

 S(n)に対してS(n)=kとなるようなnの個数N(k)を求め，k \cdot N(k)の総和を求める

というものでした．いわゆる逆転の発想，大事ですね．

結局まともに解けたのは1問だけでしたが，Div1に配属されました．かなり厳しいと自覚はありますが頑張ろうと思います．