RedCapの怠惰な日々

勝手にUniversity of Aizu Online Judgeの問題をランキング付け
解かれている人数が多い順にランキングしました
Judgeできないような問題はランキングから外しときました

Organize Your Train part II
aからzまでの記号が割り振られた貨車を連結させている貨物列車に
簡単なシミュレートをして重複を取り除いた編成の組み合わせを答える問題

setとstringを使えば簡単に解ける問題
sortしてuniqueでも同様に出きると思う

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

string getInverse ( string s ) {
  reverse ( s.begin(), s.end() );
  return s;
}

int main () {
  int N;
  cin >> N;
  for ( int n = 0; n < N; ++n ) {
    string line;
    cin >> line;
    set<string> S;
    for ( int i = 1; i < line.size(); ++i ) {
      string a = line.substr(0,i);
      string b = line; b.erase(0,i);
      string ai = getInverse(a);
      string bi = getInverse(b);

      S.insert(a+b);
      S.insert(b+a);
      S.insert(ai+b);
      S.insert(b+ai);
      S.insert(bi+a);
      S.insert(a+bi);
      S.insert(ai+bi);
      S.insert(bi+ai);
    }
    cout << S.size() << endl;
  }
  return 0;
}

せっかく作ったので公開
暇な人は実行してみてね
OSはXPとVistaで動作確認済み



参考URL
http://www.deqnotes.net/acmicpc/2d_geometry/lines

Programming ChallengesのGetting Startedの問題を一通りやってみた

100 - The 3n + 1 problem
最初の問題からWA連発
見事に罠にハマってしまう
"between i and j."に注意すべし

10189 - Minesweeper
ただ実装するだけ
問題なく簡単に通った

10137 - The Trip
結構な数のWAをくらう
試行錯誤していったら通る
解法は正しいか自信が無いのでふせとく

706 - LCD Display
実装するだけ

10267 - Graphical Editor
なぜかRuntime Error
デバックしてみると無限再帰でスタックが破壊されてた(^_^;

10033 - Interpreter
こっちに色々書いた

10142 - Australian Voting
なぜか通らない
ヤケクソでSubmitしまくって今年度最多WAを達成してしまった
悔しくてリアルに泣きそうになる
翌日に書き直したら普通に通った
なぜだ？

10196 - Check The Check
実装するだけ

Programming Challenges
http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf

Interpreter
10個のレジスタと1000個のWordを使用して3桁で表される命令を実行していく
その試行で実行された命令数を出力する問題

命令8,9の間違いで2TLEと1WAを喰らう

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int P;
int Register[10];
int Words[1000];

void clear () {
  P = 0;
  for ( int i = 0; i < 10; ++i ) {
    Register[i] = 0;
  }
  for ( int i = 0; i < 1000; ++i ) {
    Words[i] = 0;
  }
}

bool compute () {
  int a1 = Words[P]/100;
  int a2 = (Words[P]%100)/10;
  int a3 = Words[P]%10;
  
  switch ( a1 ) {
    case 1:
      return false;
    case 2:
      Register[a2] = a3;
      break;
    case 3:
      Register[a2] = (Register[a2]+a3)%1000;
      break;
    case 4:
      Register[a2] = (Register[a2]*a3)%1000;
      break;
    case 5:
      Register[a2] = Register[a3];
      break;
    case 6:
      Register[a2] = (Register[a2]+Register[a3])%1000;
      break;
    case 7:
      Register[a2] = (Register[a2]*Register[a3])%1000;
      break;
    case 8:
      Register[a2] = Words[Register[a3]];
      break;
    case 9:
      Words[Register[a3]] = Register[a2];
      break;
    case 0:
      if ( Register[a3] != 0 ) {
        P = Register[a2];
        return true;
      }
      break;
  }
  ++P;
  return true;
}

int main () {
  int N;
  cin >> N;
  string line;
  getline ( cin, line );
  getline ( cin, line );
  for ( int i = 0; i < N; ++i ) {
    clear();
    int a = 0;
    while ( 1 ) {
      getline ( cin, line );
      if (line == "") break;
      sscanf ( line.c_str(), "%d", &Words[a] );
      ++a;
    }

    int step = 1;
    while ( compute() ) ++step;
    if ( i > 0 ) cout << endl;
    cout << step << endl;
  }
  return 0;
}