Hatena::Grouptopcoder

prosho奮闘記 RSSフィード

2012-03-20

SRM538

05:03 | はてなブックマーク - SRM538 - prosho奮闘記

まず結果:Div2 oo- 0/0 93th. 1191→1233 念願のDiv1昇格!!

Div1昇格は嬉しい.やっとスタート地点に立つことができました.

LeftOrRight

  • 全探索が効かないことに気付けるかどうか
  • 何ケースか実験して?を全部LかRに置き換えれば良いことに気付く

LeftOrRight.cpp

EvenRoute

    本番中考えたこと..

  • dfsかな? だけど最悪計算量2^50だから無理
  • メモ化再帰, dp, dfsが頭の中をぐるぐる.なかなかうまくいかない.焦る
  • 40分後, ようやく本解に辿り着く
  • 本解

  • (0,0)からのマンハッタン距離(以下M距離)がdaの点Aとdbの点Bの間のM距離dは

    daとdbの偶奇が一致するとき偶数, 一致しないときは奇数

  • つまり任意の二点間のM距離の偶奇を考える場合, 原点からのM距離の偶奇を考えればよい
  • サンプルからソースコードにある関係を予想し, 証明できたのでsubmit.

EvenRoute.cpp

SkewedPerspective

まだてつかず

TurtleSpy

割と簡単な問題だったけど実装に手間取った.

    方針

  • なるだけbackかforwardに一直線に進んで, 180度回転(できれば)してから先ほどと逆方向(backだったならforward, forwardだったならback)に一直線に進めれば理想
  • 180度回転できなければ180度になるたけ近い可能な角度分回転
  • 180度になるたけ近い可能な角度の求め方がミソ

TurtleSpy.cpp(清書せず)

bmerryさんのデータの受け取り方が鮮やかだった.今後真似したい.

2012-03-19

SRM 537

02:34 | はてなブックマーク - SRM 537 - prosho奮闘記

まず結果:Div2. oo- 0/0 134th 1137→1191 (Div1まであと少し!)

そろそろ, 苦手意識のあるDiv2 HardとDiv1 Medに取り組んでいこう思います.

PrinceXToastbook

正答率が高かったので何か楽な解法があるのだろうと思ってましたが, 本番中には解けず.

方針

  • 各トーストの関係を有向グラフとみなす
  • 最初に食べるトースト毎に, 最終的な学習量の期待値を計算
  • 各トーストの求める期待値は, 根までの距離をdとすると, 1/(d+1)!となる(!!)
  • 根がない場合に注意

三番目のポイントはたぶん嘘.もう少し検討すべし.

PrinceXToastbook.cpp

KingXMagicSpells

  • お手上げだったのでkusanoさんの記事を読んで勉強.
  • ビット単位で考えるという発想が斬新.自力では思いつかなかった.
  • XORから連想できたか?

KingXMagicSpells.cpp

はじめのうちは自力では解けない問題が多いので, 他の人のコードを参考にぼちぼち解き進めようと思います...

2012-02-22

SRM533 Div.2とCodeforces #108 Div.2

06:13 | はてなブックマーク - SRM533 Div.2とCodeforces #108 Div.2 - prosho奮闘記

githubの使い方の練習がメインなので、コンテストの結果と感想くらいしか書きません(書けません)。

SRM533 Div.2

oo- 0/0 554.17 237th 1016→1057 パッとせず。。

  • PikachuEasy
  • 正規表現で一発だと思ったけど、C++で正規表現使った事無いので地道にコードを書く。

    'pi', 'ka', 'chu'を''にreplaceしてる人が多くchallenge祭りだったようだ。自分はchallengeできなかった。

    PikachuEasy.cpp

  • CasketOfStar
  • weightのサイズが高々10個なので全探索でも良かったが、初めに思いついたのはビットDP(というよりメモ化)。計算量はO(n・2^n)で、n=25くらいまでならビットDPが可能。

    ただdiv1はn <= 50 だったらしく違う方針のDPじゃないと解けないので注意が必要。

    CasketOfStar.cpp

  • MagicalGirl
  • 一捻り加えられたDPの良問。後で理解した。一捻りされるともう、手も足もでなくなるので完全に実力(基礎力)不足。

    coding phase中に解けた人はdiv1レベル。

Codeforces #108 Div.2

ooo-- 0/1 2560pt 218th 1586→1618 パットせず。。

A, B, Cは簡単。D, Eは難しく差がつかないラウンドだった。コンテストとしては不満。

2012-01-30

続 FHC R1 Aのバグ検証

20:43 | はてなブックマーク - 続 FHC R1 Aのバグ検証 - prosho奮闘記

追記:原因がわかったので編集しなおしました。

追記の追記:Sigmarさんのご指摘で真の原因が判明しました。前の記事のコメントを参照してください。

前の記事の通り、R1は落ちてしまいました。今回はAのバグを探りたいと思います。

まず、正解者のコードを実行して得た結果answer.outと、自分がsubmitしたファイルA.outのdiffをとります。

$ > diff A.out answer.out
1c1
< Case #1: 567503
---
> Case #1: 4256235

となります。

Case1のS = 8512466のときだけ値が合わないようです。

そこで、前の記事にあるコードの最後の出力部分を少し書き換えてみます。

while(test++ < r){
		cin >> S;
		int res = INF;
		int resi, resj;
		for(int i = 1;i*i <= S; i++){
			if(S % i == 0){
				int j = S / i;
				if(res >= memo[i] + memo[j]){
					res =min(res,  memo[i] + memo[j]);
					resi = i; resj = j;
				}
			}
		}
		printf("Case #%d: %d (resi = %d, resj = %d) (memo[resi] = %d, memo[resj] = %d), answer = %d\n", test, res, resi, resj, memo[resi], memo[resj],memo[resi] + memo[resj]);
}

これで実行した結果、

Case #1: 567503 (resi = 1, resj = 8512466) (memo[resi] = 1, memo[resj] = 567502), answer = 567503

となります。memo[8512466] = 567502という計算が間違っています!

たぶん、二項計算の途中でオーバーフローがおきてるのでしょうか??

まだよくわかってませんが、nCrでn=23, 4前後まで計算してストップしたほうが、今回のようなややこしいバグを含まなくて良かったかもしれません。

Facebook Hacer Cup 2011 R1

11:57 | はてなブックマーク - Facebook Hacer Cup 2011 R1 - prosho奮闘記

Qual はo-oで通過。Bはちょっと考えて大変そうだったので早めに諦めました。

今日の3:00にR1が終了したので、軽く振り返ってみようと思います。

コードや考え方が間違ってる可能性もあるのでご注意を。

(なお、問題説明は省略します。これ読んでる人の多くはR1に参加してると思うので)

最後に、誰か、はてなの日記でコードを綺麗にハイライトしてくれる方法をご存知でしたら、是非教えてください~(追記:←解決しました)

追記:結果は残念ながらxooでした。。Aのどこが悪かったんだろう・・・、challenge phase対策の格好の勉強材料になりそうですw

未だにバグがわからないので、気付いたら教えてくださると嬉しいです。

Checkpoint

ポイントは組み合わせ nCr を計算して、nCrに対する最小のnを記憶しておくこと。nCrの計算にパスカルの三角形を利用しました。

// include部分は省略
typedef long long ll;

int memo[10000002];

// pascal's triangle
void prepare(){
	queue <int> as;
	as.push(1);
	memset(memo, -1, sizeof(memo));
	for(int turn = 1; turn < 10000001; turn++){
		ll sz = as.size();
		ll pre = 1;
		while(sz--){
			int a = as.front(); as.pop();
			if(a > 10000000) continue;
			if(memo[a] == -1) memo[a] = turn;
			if(a + pre <= 10000000) as.push(a + pre);
			pre = a;
		}
		if(turn % 2 == 1 && pre != 1 && 2 * pre <= 10000000) as.push(pre * 2);
	}
}

int main(){
	prepare();
	int r, S, test = 0;
	cin >> r;
	while(test++ < r){
		cin >> S;
		int res = INF;
		for(int i = 1;i*i <= S; i++){
			if(S % i == 0){
				int j = S / i;
				res = min(res, memo[i] + memo[j]);
			}
		}
		printf("Case #%d: %d\n", test, res);
	}
	return 0;
}

Recover the Sequence

1,2,...,Nを求める答えとしてマージソートして逆変換する方針で解きました。リストの使い方が楽なのでpythonで書きました。

import sys

done = 0
S = ""

def solve(lst):
    n = len(lst)
    if n <= 1:
        return lst
    mid = n / 2
    first_half = solve(lst[0:mid])
    second_half = solve(lst[mid:])
    return merge(first_half, second_half)

def merge(lst1, lst2):
    global S, done
    result = []
    while len(lst1) and len(lst2):
        if S[done] == '1':
            result.append(lst1[0])
            lst1.pop(0)
        else:
            result.append(lst2[0])
            lst2.pop(0)
        done += 1
    result += lst1 + lst2
    return result

def checksum(lst):
    res = 1
    for i in lst:
        res = (31 * res + i)
        res %= 1000003
    return res

def main():
    T = int(sys.stdin.readline())
    test = 0
    while(test < T):
        test += 1
        N = int(sys.stdin.readline())
        global S, done
        S = sys.stdin.readline().strip()
        done = 0
        lst = [i for i in xrange(1, N + 1)]
        ret = solve(lst)
        memo = {}
        for i in xrange(len(ret)):
            memo[ret[i]] = i
        ret = [memo[i] + 1 for i in memo]
#        print ret
        print "Case #%d: %d" % (test, checksum(ret))
main()

Squished Status

まず、MODが4207849484とデカイのと、compressed sequence中の0の扱いに注意する必要があります。

以上に注意すれば、比較的に簡単な問題かと思いました。

自分はメモ化再帰で解きました。


static const double EPS = 1e-5;
typedef long long ll;
const ll MOD = 4207849484;
string S, M;
int keta_max, M_int;


int myatoi(string n){
	int res = 0;
	rep(i, n.size()){
		res *= 10;
		res += n[i] - '0';
	}
	return res;
}

ll memo[1001];

ll rec(int index){
	if(memo[index] != -1) return memo[index];
	ll res = 0;
	if(index == S.size()){
		res = 1;
	}
	else{
		FOR(i, 1, min(keta_max + 1, (int)(S.size()-index) + 1)){
			string tmp = S.substr(index, i);
			if(tmp[0] == '0' || myatoi(tmp) > M_int) continue;
			if(index + i <= S.size()){
				res += rec(index + i);
				res %= MOD;
			}
		}
	}
	return memo[index] = res;
}

int main(){
	int n, test = 0;
	cin >> n;
	while(test++ < n){
		cin >> M >> S;
		keta_max = M.size();
		if(S.size() > 1000){printf("Case #%d: %lld\n", test, 0); continue;}
		M_int = myatoi(M);
		ll res = 0;
		memset(memo, -1, sizeof(memo));
		res = rec(0);
		res %= MOD;
		printf("Case #%d: %lld\n", test, res);
	}
	return 0;
}

追記:A落ちてます・・・。二項計算の所が怪しいのかな・・・

Mi_SawaMi_Sawa2012/01/30 16:44>|cpp|
そーすこーど
||<
ですかね.
http://hatenadiary.g.hatena.ne.jp/keyword/ソースコードを色付けして記述する(シンタックス・ハイライト)
に書いてあります.

prosho007prosho0072012/01/30 17:54Mi_Sawaさん

情報ありがとうございます!お陰様でハイライトできました。
Mi_Sawaさんは無事にR1通過したようですね。R2も是非頑張ってください!

SigmarSigmar2012/01/31 01:21Aのパスカルの三角形の計算ですが、恐らくprepare全体の中で一度でも要素が10000000を超えた場合(a+pre>10000000もしくは2*pre>10000000となった場合)、その後2*preをasに一切追加しないようにする必要があるのではないかと思います。

prosho007prosho0072012/01/31 16:17Sigmarさん
ご指摘ありがとうございます!ああ、なるほど!!
確かに2*preの追加に注意すべきでした。パスカルの三角形じゃなくなりますね!
自力では全く気付きませんでしたたが、お陰様で目の前の霧が晴れました!!本当にありがとうございます!!!

RajuRaju2012/11/16 15:51Normally I'm against killing but this arctile slaughtered my ignorance.

pylrlrcweqpylrlrcweq2012/11/16 22:17ndjBap <a href="http://gssmxjyfajrd.com/">gssmxjyfajrd</a>

2011-12-20

SRM 527 Div2

11:58 | はてなブックマーク - SRM 527 Div2 - prosho奮闘記

結果は 224.28+0+0+(50-25)=249.28で144位。877→968(+91)。

Easyで慎重になりすぎたのとMediumでメモ化再帰の実装を時間に追われてミスったのが反省点。

P8XGraphBuilder (Medium解き直し)

class P8XGraphBuilder {
public:
vector <int> SCORES;
int memo[52][52][110];

int rec(int d, int num, int rest){ 
  
  if(memo[d][num][rest] != -1) return memo[d][num][rest];
  int res;
  if(rest == 0 && num == 0){ 
      res = 0;  
  } 
  else if(rest <= 0 || num <= 0 || d <= 0) res = -INF; 

  else{ 
     res = max(rec(d-1, num, rest), rec(d, num-1, rest-d) + SCORES[d-1]); 
  } 
  return memo[d][num][rest] = res;
} 

int solve(vector <int> scores) { 
  int n = scores.size()+1; 
  memset(memo, -1, sizeof(memo)); 
  SCORES = scores; 
  int res = rec(n-1, n, 2*(n-1)); 
  return res;
}
};


プロコンを始めて四ヶ月、ようやくメモ化再帰とDPが実装できるようになって来ました。

基本は、

全探索のコードを考える→(TLEの可能性)→メモ化→(スタックオーバーフローの可能性)→DP

の順番で考えること。

最初の「全探索のコードを考える」のが一番重要で難しい。