Hatena::Grouptopcoder

反省会。

2012-09-07 Friday

SRM555 Division I 00:06

前回はばっちり寝てた。

ぞろ目だからやたら5が並んでたのか…今気づいた。

 Level One - CuttingBitString (255)

  • binary列を切って5ベキだけにできるなら切った個数を返す
  • とりあえず5ベキ全部出してみよう
  • 単純に探せばいいんじゃね?
  • で探すコード書くのに30分かかるという…

Level Two - XorBoard (555)

  • カードを格子状に並べる。初期状態は全部裏
  • 列全部 or 行全部ひっくり返す操作を指定回繰り返す
  • 終わった時に表が S 枚の場合の考えられる操作の組み合わせ総数を求める
    • 「2回ひっくり返した行が2つ、1回ひっくり返した行が1つ」とかは1通りと数える。結構わかりにくい
    • 「1行目2回、2行目1回、3行目2回」と「1行目2回、2行目2回、3行目1回」は同じ
  • 行・列独立で考えたい
  • 行・列それぞれひっくり返した回数の偶奇だけで最終状態は決まる
  • 指定回数に足りない分を分配して
  • それぞれの場合の数求めて
  • 行と列で掛け算して合計すればいい
  • つながったので実装
  • 意外と面倒
  • タイムアップ

Challenge

  • 撃てそうな気配なし
  • Level One は全5ベキについて1文字目から順に一致するかどうかをとにかく調べて、あとでまとめるような実装とか
  • Level Two は最後まで計算し切らないとなー

結果

  • +139.89
  • 1222 → 1235
  • 微増

http://community.topcoder.com/stat?c=coder_room_stats&rd=15177&rm=314229&cr=23072275

反省

  • これから

2012-08-17 Friday

SRM546 Division I 00:33

Level One - KleofasTail (250)

  • 偶数なら半分、奇数なら1引く」という操作で無限数列を考える
  • 初項がA~Bの場合に、Kを途中の項に含むものの数を求める
  • 何か聞いたことあるけど気のせいかも
  • とりあえずいくつか手計算
  • 二進で考えればいい
  • 末尾0ならshift、末尾1なら0にする
  • Kを通る数は、二進で上の方の桁がKに一致する
  • 下の方の桁が0, 1, 2,… で数えて合計すれば早い
  • 最初に桁が増えない奇数と、0付近は別扱い
  • 50分程度

Level Two - FavouriteDigits (500)

  • N以上で、ある2つの数字を指定個数以上含む最小の数を求める
  • 0の扱いが厄介そう
  • 下から順に書き換えてみる
  • 間に合わず

Challenge

  • 早々に撃ち落される
  • 0付近の扱いが間違ってることに気づく
  • Level Twoで打ってみるが失敗

結果

  • -25.00
  • 1506 → 1222
  • 一気にDiv2が見えてきた

http://community.topcoder.com/stat?c=coder_room_stats&rd=14738&rm=313402&cr=23072275

その後

  • Level One は「任意の数は0,1を通る」と思って間違い。
  if (K==0) return B-A+1; // 初項0は1を通らない
  • Level Two は方針そのままに書いてみるも分岐が煩雑すぎて読めなくなってきた
public class FavouriteDigits {
 public long findNext(long N, int digit1, int count1, int digit2, int count2) {
  long n=N;
  long[] tp = new long[17];
  tp[0] = 1L;
  for (int tpI=1; tpI<tp.length; tpI++) tp[tpI]=tp[tpI-1]*10;
  
  int d1,c1,d2,c2;
  if (digit1 == 0 || (digit1 > digit2 && digit2 != 0)) {
   d1=digit1; c1=count1;
   d2=digit2; c2=count2;
  } else {
   d1=digit2; c1=count2;
   d2=digit1; c2=count1;
  }
  
  int tpI=0;
  while (count(n, d1) < c1) {
   int x = (int)((n % tp[tpI+1]) / tp[tpI]);
   n += (d1-x) * tp[tpI];
   if (n<N) {
    n += tp[tpI+1] - (d1*tp[tpI]);
    continue;
   }
   tpI++;
  }
  int mk = tpI;
  
  while (count(n, d2) < c2) {
   int x = (int)((n % tp[tpI+1]) / tp[tpI]);
   boolean next=true;
   if (x != d1) {
    n += (d2-x) * tp[tpI];
    if (n<N) {
     n += tp[tpI+1] - (d2*tp[tpI]);
     next = false;
    }
    if (count(n, d1) < c1) {
     n -= tp[tpI+1] - (d2*tp[tpI]);
     tpI = mk;
     while (count(n, d1) < c1) {
      int y = (int)((n % tp[tpI+1]) / tp[tpI]);
      n += (d1-y) * tp[tpI];
      if (n<N) {
       n += tp[tpI+1] - (d1*tp[tpI]);
       continue;
      }
      tpI++;
     }
     mk = tpI;
     next = true;
    }
   }
   if (next)tpI++;
  }
  
  return n;
 }
 
 private int count(long n, int digit) {
  int c=0;
  long l=n;
  while (l>0) {
   if (l%10==digit) c++;
   l=l/10;
  }
  return c;
 }
}
  • 戦略が間違ってるのでまた考える

反省

  • 次は頑張ると思ってたらPCご臨終
  • 1ヶ月足掻いたがだめだったので新PC購入
  • 環境も整ったので次は頑張る

2012-06-11 Monday

SRM545 Division I 00:13

Level One - StrIIRec (275)

  • 転倒数の最小値と与えられた置換(一部)以降で辞書順最小のものを求める
  • とりあえず置換を埋める
  • 転倒数OKならそれ返す
  • あとは転倒数増やす方針にした
  • 後ろから適当に入れ替える…だめ。辞書順最小になってない
  • 入れ替えるところが見つかったら戻る…これもだめ
  • 入れ替えたら一旦辞書順に並び替えないとだめなのか?
  • 方針がまずい気がする
  • 残り10分。ちょっと間に合わないか…
  • Challenge用のケース作る
  • 明らかに通ってないものの提出

Challenge

  • 自分と似たようなことをやってるコードを見つける
  • 後ろから順番に並び替えるだけだとだめなんだよな…自分含め。
  • 成功。+50
  • もう1つ似たようなの発見
  • こっちは通って失敗-25。入れ替えが地味に違うな…

結果

http://community.topcoder.com/stat?c=coder_room_stats&rd=14737&rm=313279&cr=23072275

その後

  • 一応解いた
  • 転倒数しか見てないからダメなのであって、辞書順に次のを求めるようにする
  • c[i-1]<c[i] となる最大のiを求める
  • 辞書順で次 → c[i-1]<c[j](j>=i)となる最大のj*1を持ってきて入れ替えてi以降をソート*2
  • まともにやると全然間に合わない
  • c[i-1]<c[j](j>=i) となる最大のjを持ってきて入れ替えた時点で、転倒数は+1。辞書的に次から入れ替え直後までのものはすべて転倒数がこれより小さい*3ので、調べる必要なし。ソート外す。
import java.util.ArrayList;

public class StrIIRec {

  public String recovstr(int n, int minInv, String minStr) {
    ArrayList<Character> l = new ArrayList<Character>();
    for(int i=0; i<n; i++) {
      l.add((char)('a'+i));
    }
    for(int i=0; i<minStr.length(); i++) {
      l.remove(Character.valueOf(minStr.charAt(i)));
    }
    String str = minStr;
    for(Character d:l) {
      str += d.toString();
    }
    char[] c=str.toCharArray();
    while(true) {
      if (count(c) >= minInv) {
        break;
      }
      if (!nl(c)) break;
    }
    
    return new String(c);
  }
  
  private int count(char[] c) {
    int cnt = 0;
    for(int i=0; i<c.length; i++) {
      for (int j=i+1; j<c.length; j++) {
        if (c[i] > c[j]) cnt++;
      }
    }
    return cnt;
  }
  private boolean nl(char[] c) {
    for (int i=c.length-1; i>0; i--) {
      if (c[i-1] < c[i]) {
        for (int j=c.length-1; j>=i; j--) {
          if (c[i-1] < c[j]) {
            char tmp = c[j];
            c[j] = c[i-1];
            c[i-1] = tmp;
            return true;
          }
        }
      }
    }
    return false;
  }
}

反省

  • 時間がかかりすぎたのは問題
  • Challenge用にケース用意しておいたのは○
  • もう年か…

*1:c[i-1]に一番近いc[j]

*2:逆順に並んでるのでreverseで良い

*3:逆順に並んでるものが最大だから

2012-05-30 Wednesday

SRM544 Division I 22:59

少しくらい練習しときゃよかったと思いつつ。

Level One - ElectionFraudDiv1(275)

  • roundした投票率から最小の有権者数を求める
  • 最少人数を求めてちょっとずつ増やして
  • ループが全然終わってない…直す
  • ループ抜ける判定条件がおかしい…直す
  • 45分経過。テスト未だ通らず
  • 状況確認。Level Two出してる人多いな

Level Two - FlipGame(500)

  • 長方形に並んだタイルのうち、最短境界線引いて左下を全部裏返す
  • 与えられた状態から全部裏にするのにかかる最小手順を求める
  • 右上にある表を境界にすればいい
  • 1列の裏返し関数作って
  • n列に拡張して
  • 出した。17分

Level One

  • 早々に諦める条件追加したらテスト通った。
  • かなり怪しいけど出した。残り10分

Level Three - SplittingFoxes(900)

  • 進む、右向く、左向くとやっていって座標の合計値を求める
  • まともにやったら絶対終わらんな…

Challenge

  • Level Twoは間違うポイントなさげ
  • Level Oneは何か出来るかもしれないけど、自分がわかってない
  • 人のコードを読むばかり
  • 早々にLevel Oneは撃墜
  • 何で撃ち落とされたんだろう…よく分からない

その後

  • Chatroom見てるとどうもLevelTwo簡単すぎと。
  • LevelOneは全有権者数さえわかれば良くて、わざわざ各候補者の得票数まで求めなくて良い。
  • LevelThreeは4*4行列に値放り込んで計算してる。まとめて計算できるんか…何でかわかんないけど。
  • Challengeの結果とか詳しく分かるのね

反省

  • Simple is the best
  • 練習しといた方がいい気がする。ていうかしたい。
  • LevelThreeどうなってんだろう

結果

  • 1309 → 1521
  • 黄色くなった

http://community.topcoder.com/stat?c=coder_room_stats&rd=14736&rm=313096&cr=23072275

2012-05-20 Sunday

SRM543 Division II 23:38

初参戦。反省は必要だと思う。

当日の状況 23:38

Level One - EllysTSP (250)

  • "C":Cityと"V":Villegeを交互に訪れる場合の最大数を求める
  • とりあえずCとVを数えて少ない方×2
  • 余りの分を間違えないように
  • 出した。15分くらい

Level Two - EllysXors (500)

  • LからRまでの合計。ただしXOR
  • 単純に計算したらどう考えても時間足りないよな…
  • ちょっと計算
  • 2^nから2^(n+1)-1までは0になるのでここだけ省略
  • あんまり省略できてないなあ…
  • この辺でCPU使用率100%に
  • 再起動して提出。残り15分

Level Three - EllysThreeRivers (1000)

  • 川3本を渡るときの最小時間
  • 3点動かすのめんどくさいなあ…と思ってたら時間切れ

Challenge

  • 2問目は単純計算にぶつけてみたけど間に合わず
  • 1問目の余り間違い2つみつけて+100
  • 自分の2問目はやっぱりだめ
  • 6つくらいチャレンジかけてる人も

反省 23:38

Level Two

  • XORが自分自身を逆元とする加群なんだから1~Rから1~L-1を引く=XORする、とすればよかった
  • 1~Rなら周期4で即求まるらしい

Level Three

  • なんか書くべき…
  • 屈折率とか

結果 23:38

  • Level One:235.93
  • Score:335.93
  • Rank:216
  • Rating:1309

詳しく

http://community.topcoder.com/stat?c=coder_room_stats&rd=14735&rm=313067&cr=23072275