TCO Round1B - 不定期プログラミング覚え書き

結果報告

今回はちゃんと寝ブッチしなかった！
会社の寮からテザリング参加。夕方頃お酒飲んでたけど流石に25時には酔いも冷めてた
250-500-1000回。

Level	ProblemName	Status	Point
Easy	FoxAndKgram	PassedSystemTest	209.24
Medium	FoxAndDoraemon	PassedSystemTest	372.26
Hard	FoxAndPhotography	Opened	----

Easy FoxAndKgram

問題

色々な長さの鉛筆がある．
これらの鉛筆を使って（全部使わなくても良い），K-gramという図形を作りたい．
ある自然数Kに対して，K-gramとは，

長さKの鉛筆からなる行
二つの鉛筆を長さ１だけ開けて置いた行．鉛筆二つの長さの和+1＝Kを満たす．

を満たす，K行の図形である．
鉛筆の長さを配列で受け取り，K-gramが作成可能である最大のKを返せ．
（何一つ作れない時は0を返す）

考えたこと

長さKの行を作るときに，長さlと長さK-l-1のペアがいくつ作れるか，を毎回入力配列から探すのは面倒くさい．
長さの対応だけを考えれば良いのだから，それぞれの長さの鉛筆が何個あるかをnum[l](長さlの鉛筆の個数）みたいに，最初に覚えておこう．
すると，長さKの行がいくつ出来るかは，
num[K]+min(num[1],num[K-2])+min( num[2],num[K-3] )...として表せる
但し，Kが奇数である時には，
(K-1)/2の鉛筆を二つ使って長さKの行を作る事が可能であるため，
その時だけnum[(K-1)/2]/2を追加する必要がある事に注意が必要．

コード

  int maxK(vector <int> len) {
    int result=0;
    int num[101];
    memset( num, 0 , sizeof( num ) );
    for( int i = 0 ; i < len.size(); i++ ){
      num[len[i]]++;
    }
    for( int i = 1 ; i <= 100;  i++ ){
      // check i;
      int row=num[i];
      for( int j = 1 ; j < i ; j++ ){
        if( i-1-j < j ) break;
        if( i-1-j == j ){
          row += num[j]/2;
        }
        else row += min( num[j], num[i-1-j] );
      }
      if( row >= i ) result = i;
    }
    return result;
  }

計算量の見積もりはfor分の上限をKとすると， $O(K^2)$ になるだろうか．
取り敢えず今回は100まで調べたけど，lenの要素が1-50，lenの個数が50以下という制約から，鉛筆の長さ総和が高々2500だし，50くらいまでしか答えは出ないはず．

無駄にnum[len[i ] ]++の行をnum[i ]++とかしていてバグ取りに手間取ってしまった．

Medium FoxAndDoraemon

問題

狐さんが一匹居る．宿題が沢山あって，それぞれの所要時間は入力で配列にして与えられる．
狐さんは面倒くさがり屋なので，一匹につき一つの宿題しかやりたくない．
そこで，ドラえもんにお願いし，一匹の狐を二匹にする不思議道具を出してもらった．
一匹の狐を二匹にさせるには時間がかかり（これも入力Sとして与えられる），分身中の狐は宿題をすることは出来ない．
すべての宿題を終わらせるまでに最短で何秒かかるかを示せ．

考えたこと．

一匹が二つの宿題をするケースまで考えたら脳内カオスになった．
（この場合で良い解き方ってあるんでしょうか，誰か解ったら教えてください）
途中でこの事に気づいて考えなおす．
一匹が必ず一つの問題を解くということは，最終的に狐は問題数匹いないといけないらしい．

……で？

例えば二問の問題（必要時間 $A,B$ とする）をとこうとした時は， $S+max(A,B)$ だけの時間が必要である．
三問の問題(必要時間 $A,B,C$ とする． $A\leq B\leq C$ )を解こうとした時,
最初に一問解かせる->分離->二問解かせるというケースは（とある狐が二問説いている事になるので）ありえない．
狐F1と狐F2に分離->F1に一問解かせつつF2を分離(F2とF2'になる)->二問解かせる
とするしかない．
この時，F2を分離＋二問解かせるというステップを一匹の狐の動作だと捉えると，
なんとなく，蟻本の木を切り刻んで行く問題に似てるかな，と思ってみる．
ここまで考えて書いた．サンプル通った．出した．システム通っちゃった．
正直理論的考察が適当すぎる感ある．

コード

  int minTime(vector <int> workCost, int splitCost) {
    priority_queue<int, vector<int>, greater<int> > wc;
    for( int i = 0 ; i < (int)workCost.size(); i++ ){
      wc.push( workCost[i] );
    }
    while( wc.size() >= 2 ){
      int a = wc.top();
      wc.pop();
      int b = wc.top();
      wc.pop();
      wc.push(b+splitCost);
    }
    return wc.top();
    
  }

計算量はキューの操作がworkCostのサイズをNとした時に
$O(N \log N)$ とか

再考

蟻本を改めて眺めてそこそこ納得したのでメモ．
今回の問題は，問題を狐が解く所を葉とし，各ノードにそこから先の経過時間を格納したような二分木で解釈することが出来る．
例えば二問の問題（必要時間 $A,B$ とする）をとこうとした時は，てっぺんが $S+max(A,B)$ ，左右がA,Bとなっているような二分木である．って感じ．
子供と親ノードの関係が $S+max(A,B)$ と表せる事に注意する．
この時，最適解において，もっとも簡単な宿題をする狐と二番目に簡単な問題を解く狐が一番深い所の兄弟になるだろう．
（いつも思うのだけれどこれが直感的にそんな気もしつつ数学的に綺麗に説明できない…）
よって，そのノードを $S+max(A,B)$ とひとつに纏め，これを新たな狐と見ることで，再帰的にノード数が１になるまで処理を行うことが出来る．

Hard FoxAndPhotography

問題

二列に並んだ人の写真を撮りたいと考える．
各列は同じだけの人数が並んでいて，i番目の人の身長がheightFront[i]（前の人）,heightBack[i]（後ろの人）となるように配列が入力で与えられている．
後ろの人の身長が前の人の身長よりも真に大きくなるようにしたいが，
一回の操作で，同じ列の隣同士の人をswapさせることしか出来ない．
この要件を成立させるためにもっとも少ないswap数を返せ．実現不可能な時は-1を返すようにせよ．

考えたこと

前の方の人のswapと後ろの方の人のswapが両方混じってるケースは考えなくても良いだろう．
なぜならば，全く同じ動作を後ろの人にやれば事足りるからである．

……で？
流石に後ろの列のすべてのpermutationを考える事は時間的にきびそうである．
heightFrontの要素数が16であるから，16!は10^13くらいあった．

かと言って他に良い方法は思い浮かばないんだよなあ…