Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2011-09-14

Single Round Match 518 00:26 Single Round Match 518 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 518 - nodchipのTopCoder日記 Single Round Match 518 - nodchipのTopCoder日記 のブックマークコメント

出先からの参戦でノートPCを持って行かなかったため、Linux+Eclipse+Javaでやってみました。

Easy 250 LargestSubsequence

  • なるべくASCIIコードの大きな文字を先頭に置きたい
  • ということは一文字目は文字列の中で最も大きい文字
  • 複数ある場合は一番初めに来るもののはず
  • では2文字目以降はどうだろう
  • 1文字目以降の中で最も大きい文字っぽい
  • 3文字名工も同様
  • 少し形を変えてスタックの先頭に大きな文字を入れていく感じで書いてみる
  • Passed System Test
public class LargestSubsequence {
  public String getLargest(String s) {
    List<Character> stk = new ArrayList<Character>();
    for (int i = 0; i < s.length(); ++i) {
      char ch = s.charAt(i);
 
      while (!stk.isEmpty() && stk.get(stk.size() - 1) < ch) {
        stk.remove(stk.size() - 1);
      }
 
      stk.add(ch);
    }
 
    String result = "";
    for (char ch : stk) {
      result += ch;
    }
    return result;
  }
}

Middle 500 ConvexSequence

  • きっとDP
  • ・・・
  • 本当にDP・・・?
  • 直感的にはa\[i\]=min(a\[i\],\lfloor a\[i-1\]+a\[i+1\] \rfloor)を繰り返せば収束する気がする
  • 本当かなぁ・・・
  • まず上記の更新式によって、更新直後は更新した値が条件をみたすのはわかる
  • また更新後の値は正解の値より大きいことは自明
  • ・・・
  • 十数行だしサンプル通るかくらい確かめてみよう
  • ・・・
  • 通った
  • 念のためランダムテストケースを突っ込んでTLEしないかどうか確かめてみる
  • ・・・大丈夫そう
  • 出しちゃえ
  • Passed System Test
public class ConvexSequence {
  public long getMinimum(int[] aa) {
    long[] a = new long[aa.length];
    for (int i = 0; i < aa.length; ++i) {
      a[i] = aa[i];
    }
 
    long result = 0;
    boolean updated = true;
    while (updated) {
      updated = false;
      for (int i = 1; i < a.length - 1; ++i) {
        if (a[i - 1] + a[i + 1] >= 2 * a[i]) {
          continue;
        }
 
        updated = true;
        long next = (a[i - 1] + a[i + 1]) / 2;
        result += a[i] - next;
        a[i] = next;
      }
    }
 
    return result;
  }
}

Hard 1000 Nim

  • 真面目に考えていません

Challenge Phase

  • とりあえず順番に読んでみる
  • ・・・
  • 怪しいコード発見
  • 書き写してみる
  • ・・・
  • 時間かかりすぎて終了orz

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
LargestSubsequencegetLargestLevel One0:05:27.736Passed System Test241.19
ConvexSequencegetMinimumLevel Two0:16:43.505Passed System Test383.75
NimcountLevel Three0:51:18.694Opened0.00

1798->1875 500の大波乱に便乗してレーティングが上がりました。1900を回復したいところです。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20110914
 |