Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-26

[][] TopCoder Single Round Match 513 Div.1 01:08 はてなブックマーク -  TopCoder Single Round Match 513 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:39:19.218Passed System Test121.68
5000:35:26.558Opened0.00
10000:28:17.098Opented0.00
Challenge..0.00

部屋(Room 29) 15位,全体 530位

Rating : 1513 → 1450 (-63)

 プラスマイナス1のズレ恐怖症.

続きを読む

2011-07-23

[][] Codeforces Beta Round #78 (Div. 2 Only) 17:09 はてなブックマーク -  Codeforces Beta Round #78 (Div. 2 Only) - 練習帳

概要

 問題一覧:Dashboard - Codeforces Beta Round #78 (Div. 2 Only) - Codeforces

 結果:Standings - Codeforces Beta Round #78 (Div. 2 Only) - Codeforces

結果

=.ABCDE
--0:121:101:44--
476+0/-0476/00/-20/-1--

部屋内19位(Room 23),全体469位

Rating:1478 → 1478 (unrated)

 D問題(= Div1. B問題)でミスがあったようでunratedとなりました.自分の反省点は,ケアレスミス多い事です.

続きを読む

2011-07-21

[][] Project Euler Problem 125 21:49 はてなブックマーク -  Project Euler Problem 125 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=125

要約

 正数で連続する数を各々2乗して足した形で書けて,しかもpalindromicであるもの達のうち,10**8未満のものの合計を求めよ.

方針

 i, j を動かしながら,i**2 + (i+1)**2 + ・・・+ j**2を求めて,これがpalindromicかを調べるi, jの動く範囲は10**4以下.

コード例(python
from copy import copy

N = 10 ** 8
M = 10 ** 4

def isPalindromic(n):
    digits = []

    while(n > 0):
	digits.append(n%10)
	n /= 10
    original = copy(digits)
    digits.reverse()
    return digits == original

hits = []
for i in xrange(1, M):
    psum = i * i
    for j in xrange(i+1, M):
	psum += j * j
	if psum >= N :
            break
	if isPalindromic(psum) :
            hits.append(psum)

ans = set(hits)
print sum(ans)

2011-07-20

[][] Project Euler Problem 128 07:19 はてなブックマーク -  Project Euler Problem 128 - 練習帳

問題文

 Problem 128 - Project Euler

要約

 正六角形がハニカム構造で配置され,それぞれの正六角形の中をルールに従って数字を埋めていく(ルールは問題文の図を参照してください).ある数nに対し,nと隣接する書かれているそれぞれの数字(6個ある)と差の絶対値をとり,その中にある素数の個数をPD(n)で表す.PD(n)は常に3以下である事が示せるが,PD(n)=3となるnのうち2000番目に小さい数を答えよ.

続きを読む

2011-07-18

[][] Codeforces Beta Round #77 Div2. D Volleyball 続き 20:11 はてなブックマーク -  Codeforces Beta Round #77 Div2. D Volleyball 続き - 練習帳

 前回,n=1000に対するワーシャルフロイドを行ってTLEを起こしたところまでで終わっていたのでその続きを行います.結論を先に言うと,ネックはここだけではなく,後段のコストを求めるためにダイクストラ法を行っている部分でも不適切な箇所がありました.

続きを読む

2011-07-15

TopCoder Single Round Match 512 Div.1 23:48 はてなブックマーク - TopCoder Single Round Match 512 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:26:57.423Passed System Test154.99
5000:47:49.875Opened0.00
10000:35:50.090Opented0.00
Challenge..0.00

部屋(Room 37) 8位,全体 458位

Rating : 1505 → 1513 (+8)

 下がらなかったから良し.

続きを読む

2011-07-12

[][] Codeforces Beta Round #77 Div1. B Lucky Numbers 01:06 はてなブックマーク -  Codeforces Beta Round #77 Div1. B Lucky Numbers - 練習帳

問題文

 問題文

続きを読む

2011-07-10

[][] Codeforces Beta Round 77 (Div. 2) 15:49 はてなブックマーク -  Codeforces Beta Round 77 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #77 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #77 (Div. 2 Only) - Codeforces

=.ABCDE
--0:091:400:411:23-
1032+0/-0482/0550/-10/-10/-1-

部屋内16位(Room 11),全体390位

Rating:1510 → 1478 (-32)

 C, D解けたと思ったのですが残念です.しかもBを解くのを後回しにした為に余計順位が下がってしまいました.

続きを読む

2011-07-08

[][] TopCoder 508 Div.1 250 DivideAndShift 07:02 はてなブックマーク -  TopCoder 508 Div.1 250 DivideAndShift - 練習帳

問題文

 問題文

要約

 1からNまで番号がついたスロットが横一列に並んでいる.これらに次の操作を行える.

  • Nで割り切れる素数pを適当にひとつ選び,N個のスロットp個ずつに分割する(1~N/p, N/p+1~2N/p ・・・)このうち1つを選び,N/pを新たなNとして,1からNの番号を振り直す
  • 左右どちらの方向かにスロット達を1つずつシフトする.

 左からM番目のスロットを1番目に持ってくるのに必要な最小操作回数を求めよ.

方針

 シフト=>分割と操作を行っている場合,もし,シフトによって分割のチャンクを跨ぐなら,順序を逆にして分割=>シフトとした方が最適,跨がなければこの2つの操作は書かん.従って,先に分割を繰り返してからシフトを行うと仮定してよい.

  • 分割を終了して,右シフトを繰り返して1番左まで持ってくる
  • 分割を終了して,左シフトを繰り返して1番右まで持ってくる
  • 分割を引き続き行う

のうち,最も回数の少ないものを選択する

コード例

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;

bool isprime(int n){
  if(n < 2){
    return false;
  }
  for(int i = 2;i *i <=n;i++){
    if(n%i== 0){
      return false;
    }
  }
  return true;
}

int inf = 10000000;

int calc(int n, int m){
  //  cout << n << " " << m <<endl;
  
  if(m ==1){
    return 0;
  }
  int res = inf;
  int mx  = 1;

  if(n%2 == 0){
    int nextn = n/2;
    int nextm = ((m-1)%nextn)+1;
    res = min(res, calc(nextn, nextm) + 1);
    mx = 2;
  }

  for(int i = 2;i<=n;i++){
    if(n%i == 0 && isprime(i)){
      int nextn = n/i;
      int nextm = ((m-1)%nextn)+1;
      res = min(res, calc(nextn, nextm) + 1);
      mx = i;
    }
  }

  if(mx == 1){
    return 1;
  }

  res = min(m-1, min(n-m+1, res));

  return res;
}

class DivideAndShift {
public:
  int getLeast(int N, int M) {
    return calc(N, M);
  }
};	

2011-07-07

[][] SRM 511 Div1 500 FiveHundredEleven 07:45 はてなブックマーク -  SRM 511 Div1 500 FiveHundredEleven - 練習帳

問題文

 問題文

要約

 2人がカードを用いてゲームを行う.場にカードがn枚あり,カードには0から511以下の数字が書かれている.また,2人で共通のメモリがあり,整数をひとつ記憶できる.ゲーム開始時メモリは0で初期化される.ゲーム中2人は交互にカードを1枚選んで捨て,捨てたカードとメモリのbitwise ORでメモリを更新する.メモリが511になるか,残りカードが0枚でカードが捨てられなくなったら負けとなる.先手後手のいずれが必勝かを判定せよ.カードの枚数は50枚以下.

分析

 今日も今日とてPetrさんのコードで勉強.以下のコードを参照しています

 http://www.topcoder.com/stat?c=problem_solution&rm=309046&rd=14536&pm=11484&cr=10574855(要ログイン)

 深さ優先探索で行えば良い事は何となくわかる.dfs(memory, condition)をmemory, conditionの状態から初めて,先手必勝ならば1, 後手必勝ならば2となるような関数とするならば,概形は次のようになります.メモ化のコードは省略しています.

(疑似コード)

(作成途中版,メモ化などは省略)
int n;
vector<int> card;

int dfs(int memory, (ゲームの状態を現す何かの数)){

  for each(newmemory, newcondition)
    if(dfs(newmemory, newcondition) == 2){
      return 1
    }
  }

  return 2;
}

class FiveHundredEleven {
public:
  string theWinner(vector <int> cards) {
    n = cards.size();
    c = cards;
    memset(memo, 0, sizeof(memo));
    if(dfs(0, 0) == 1){
      return "Fox Ciel";
    }else{
      return "Toastman";
    }    
  }

問題は状態として何を持つかとその更新方法です.カードの数が50枚なので,それぞれのカードを使ったかどうかをみると2**50通りとなり計算量が間に合わないません,結論としては捨てたカードの枚数だけを状態として持てば十分なのですが,なぜそれで良いのかきちんと説明できないです.

(作成途中版,メモ化などは省略)
int dfs(int memory, int cardsPlayed){

    //カード切った事で値が更新される場合
  for(int i = 0;i < n;i++){
    if((c[i] & memory) != c[i]){ 
      int nextmemory = c[i] | memory;
      if(nextmemory != 511 && dfs(nextmemory, cardsPlayed+1) == 2){
	return 1;
      }
    }
  }

  (カードを切った事で値が更新されない場合のコードを後で考える)

  return 2;
}

最後に値が更新されない場合を考えます.例えば残りカードが

●●●●○○×××
●:すでに切ったカード
○:まだ切ってなく,切るとメモリの値を更新されるカード
×:まだ切ってなく,切ってもメモリの値を更新できないカード

となっていたとします.このとき,n=9, cardsPlayed=4です.ここから×の数3を取り出すのが目標です.今回の問題では,メモリは逐次bitwise ORを取っていくので,

    if((c[i] & memory) != c[i])

では,●と×を区別する事が出来ません,そこでこの条件を適用する前に,予め●を除いておきます.すなわち,

    int cardsRemaining = n - cardsPlayed

    if((c[i] & memory) != c[i]){
      cardsRemaining--;
      ・・・
    }

です.結局最終的なコードは次のようになります.

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cstring>

using namespace std;

int n;
int memo[512][51];
vector<int> c;

int dfs(int memory, int cardsPlayed){
  if (memo[memory][cardsPlayed]!= 0){
    return memo[memory][cardsPlayed];
  }
  
  int cardsRemaining = n - cardsPlayed;

  for(int i = 0;i < n;i++){
    if((c[i] & memory) != c[i]){
      cardsRemaining--;
      int nextmemory = c[i] | memory;
      if(nextmemory != 511 && dfs(nextmemory, cardsPlayed+1) == 2){
	memo[memory][cardsPlayed] = 1;
	return 1;
      }
    }
  }

  if(cardsRemaining > 0){
    if(dfs(memory, cardsPlayed+1) == 2){
      memo[memory][cardsPlayed] = 1;
      return 1;
    }
  }

  memo[memory][cardsPlayed] = 2;
  return 2;
}

2011-07-04

[][] SRM 511 Div1 250 Zoo 00:37 はてなブックマーク -  SRM 511 Div1 250 Zoo - 練習帳

 SRMがある事に気づきませんでした,もったいない.

問題文

 問題文


方針

 答えが0とならない条件は,「i」と答えた動物の数がi番目に来るように数字を並べたものが正規表現で2*1*0*と現されるとき.2がp個,1がq個のとき,求める場合の数は

(2**p)*2 (qが0でない時)
(2**p) (qが0の時)

コード例

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

class Zoo {
public:
  long long theCount(vector <int> answers) {
    int n = answers.size();
    vector<int> stat(41);
    for(int i = 0;i < n;i++){
      stat[answers[i]]++;
    }

    for(int i = 0;i < 40;i++){
      if(stat[i] < stat[i+1]){
	return 0;
      }
    }
    if(stat[0] > 2){
      return 0;
    }
    long long ans = 1;

    int i = 0;
    for(i = 0;i < 41;i++){
      if(stat[i] == 0){
	break;
      }
      ans *= stat[i];
    }

    if(stat[i-1] == 1){
      ans *= 2;
    }

    return ans;

  }
}

2011-07-03

Codeforces Beta Round #76 (Div. 2 Only) 09:00 はてなブックマーク - Codeforces Beta Round #76 (Div. 2 Only) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #76 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #76 (Div. 2 Only) - Codeforces

 時間的に参加できるかと思いましたが,間に合いませんでした.

続きを読む