Hatena::Grouptopcoder

Div2脱出のための日記 このページをアンテナに追加

2011-07-28

TopCoder SRM 513 Div2

| 20:16 | TopCoder SRM 513 Div2 - Div2脱出のための日記 を含むブックマーク はてなブックマーク - TopCoder SRM 513 Div2 - Div2脱出のための日記 TopCoder SRM 513 Div2 - Div2脱出のための日記 のブックマークコメント

結果

rating 763 → 771

points: 155.48

  • Easy 250: 22:00
  • Medium 500: Compiled
  • Hard 1000: 未open
  • : 撃墜なし/非撃墜なし

room 80: 8位

全体: 639位

久々のroom一桁順位です。自分にはスピードがないので1問では差がつきません。

問題

  • Easy 250 Training Camp

n日間の講習会の最後にテストを行う。

テスト問題はm問からなりそれぞれの問題は、講習日の内容に依存している場合がある。

生徒の出欠の記録から、生徒の正答できるはずの問題を予想せよ。

  • Medium 500 Yet Another Incredible Machine

XY座標系(-10000 <= x <= 10000)にバーを設置するためのマウントポイントが

n個(1<= n <= 50)ある。

i番目のマウントポイントにはバーiが水平に設置され長さL[i]である。

マウントポイントの座標は、(M[i], i+1)と表わせる。

バーiをマウントポイントiの一番左端にマウントすると

(M[i] - L[i], i+1)、(M[i], i+1)をバーiが占め、

一番右端にマウントすると(M[i], i+1)、(M[i] + L[i], i+1)をバーiは占める。

マウントポイントから外れない範囲でバーはx方向に1単位で任意の位置に動かすことができる。

次にボールをバーより高い位置から落下させる。m個(1<= m <= 50)のボールはそれぞれ

独立なx座標b[k]から落下するとした場合、

全てのバーがどのボールとも衝突しないように、バーを配置する組合せは何通りあるか。

解答

  • Easy 250 Training Camp
class TrainingCamp {
public:
    vector <string> determineSolvers(vector <string> attendance,
    				     vector <string> problemTopics) {
	vector<string> v = attendance;
	vector<string> u = problemTopics;
	vector<string> w;
	int days = v[0].size();
	for (int i = 0; i < v.size(); ++i) {
	    stringstream ss;
	    for (int j = 0; j < u.size(); ++j) {
		char c = 'X';
		for (int k = 0; k < days; ++k) {
		    if (u[j][k] == 'X' && v[i][k] == '-') {
			c = '-';
		    }
		}
		ss << c;
	    }
	    w.push_back(ss.str());
	}
	return w;
    }
};

  • Medium 500 Yet Another Incredible Machine

これは修正してsystem testを通したもの。

実戦では、テストケース4が通らず提出を断念。

敗因は、

    • unsigned long longを使うべき変数でintを使っていた。
    • 1000000009のmoduloをループ内の組合せ計算後、

毎回modするべきところをreturn時しかやっていなかった。

以上。他のロッジック部分は問題なかったので残念。


class YetAnotherIncredibleMachine {
public:
    int countWays(vector<int> platformMount,
		  vector<int> platformLength, vector<int> balls) {
	int const M = 1000000009;
	vector<int> X = platformMount;
	vector<int> L = platformLength;
	int const nr = X.size();
	int const b_nr = balls.size();
	unsigned long long sum = 1;
	for (int i = 0; i < nr; ++i) {
	    int c = 0;
	    for (int x = X[i] - L[i]; x <= X[i]; x++) {
		bool hit = false;
		for (int k = 0; k < b_nr; ++k) {
		    if (x <= balls[k] && balls[k] <= x + L[i]) {
			hit = true;
		    }
		}
		if (!hit) {
		    c++;
		}
	    }
	    if (c == 0) {
		return 0;
	    } else {
		sum *= c;
		sum %= M;
	    }
	}
	return sum;
    }
};

総括・反省

  • Easy 250 Training Camp

Easyは平易なので、問題文は雰囲気だけ見て、テストケースだけを真剣に読むという時短作戦を決行。

Example 0の説明文が全てを語ってくれていたので作戦は奏功しましたが、

生徒の出欠表と、問題と講習日の対応表からの判定手順を紙上で検討していたら、

トータルで22分ほど掛りました。

コンパイルから全テスト確認、submitが1パスで行ったのは良いのですが、

やはり、Easyは15分、200pointsくらいは欲しいところ。

  • Medium 500 Yet Another Incredible Machine

問題文がちょっとまどろっこしく読むのに時間がかかりましたが、

ロジック自体はEasy程度の平易なものでした。

moduloとかxの値域が[-10000:10000]とか、いかにもintのoverflow

匂わせるヒントがあったのですが気づかなかったのが敗因です。

メソッドのreturnがintだったので騙されました。

概算として、バー50本を20000箇所に独立に配置する場合の場合の数を考えると、

20000を表現するのに必要なbit数は2^16 = 65536から15bitsは必要ですから、

20000^50 〜 2^(15 + 50) = 2^65

2^64を越えてunsigned long longでも間に合わない値になる場合がありえるということで、

modulo取れという指定が必要とされたわけです。

"*="を繰替すような計算があれば、intで済まない可能性大。

moduloと言われたら、64bits変数でも表現できない数が出てくる。

以上が本問の教訓でした。

  • 全体

500はロジックは問題なかったので残念ですが、overflowの権化のような

問題なので教訓になりました。

当面の目標としては、2問正答してコンスタントにroom 5位以内を目指したいところです。

5位を続けていれば、ratingは1000くらいまで順調に上るはずと考えています。

今回は、vector,string,stringstreamくらいしか使わなかったですが、

STLの使い方でコンパイルでトチらなくなってきたのと

ループと条件文によるロジック構成をエディタ上で試行錯誤しなくなったのは、

良い傾向です。

しばらく、400番台のEasy,Mediamのセットを1時間で解く練習でもします。

以上。

2011-07-23

Codeforces Beta Round #78 Div. 2

| 17:51 | Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 Codeforces Beta Round #78 Div. 2 - Div2脱出のための日記 のブックマークコメント

結果

rating 1438 → 1438

points: 0

  • A: WA 00:20
  • B: WA 40分くらい
  • C: Openして、問題は理解した。
  • D: Openしたが、題意が取れず。
  • E: Openして、問題は理解した。
  • Hacks: 撃墜なし/非撃墜なし

room 17: 28位

全体: 821位

ABがWrong Answerで、CDEは手が出せず。全滅でありました。 :-(

どうも他の方の日記によるとD問題が意味不明過ぎて、

unrated回になったということのようで、うまいこと救われた形になりました。

問題

  • A. Help Far Away Kingdom

標準入力で与えられる実数の整数部の一の位が'9'の場合は、"GOTO Vasilisa."を標準出力に表示し、

それ以外の場合は小数部分が'0.5'以上であれば切り上げた整数を'0.5'より小さければ切り捨てた整数を

標準出力に表示しなさい。

  • B. Help Chef Gerasim

n個のコップに注がれた液体を全てのコップで等しい量になるよう1度だけ注ぎ直す。

標準入力の1行目はカップの数n、2行目以降の行がコップに注がれた液体の量。

入力が以下の場合、

3

270

250

230

"20 ml. from cup #4 to cup #1." と表示する。

既に全てのコップの液体の量が等しく、調整の必要がない場合、"Exemplary pages." と表示する。

調整しても全てのコップの量を揃えられない場合、"Unrecoverable configuration." と表示する。

  • C. Help Victoria the Wise

サイコロの各面を標準入力で指定された文字列の1文字づつを使って塗り分け、その塗り分けの種類数を標準出力に出力せよ。

入力が"BOOOOB"の場合、"2"を表示。

"YYYYYY"の場合、"1"。

"ROYGBV"の場合、"30"。

  • D. Help King

王女の婿候補n人をコインを投げた裏表で選別して婿を決定する。婿が決まるまでに必要なコインの投擲回数を表示せよ。

n=2なら1/1

n=3なら8/3

  • E. Help Greg the Dwarf

長さ'l'幅'w'の棺桶を屈折した通路を通せるように作りたい。

通路は直角に屈折した部分があり、折れ曲った一方の通路の幅は'a'で、もう一方の幅は'b'。

棺桶の長さ'l'は身長から決まっているので、通路を抜けられる幅'w'の最大値を求めよ。


DIV1との関連

今回のDIV2の問題のうち、DIV1の問題でもあるものは、

DIV2DIV1
C A
D B
E C

みごとにスライドして使われています。

DIV2でCDEを正答できないとDIV1に上っても定着できないということですね。

解答

解答は全てpythonです。

  • A. Help Far Away Kingdom

以下は提出したものではなく、後でsystem testを通したもの。

x, f = raw_input().split('.')
n = int(x)

if x[-1] == '9':
    print "GOTO Vasilisa."
else:
    if f[0] >= '5':
        print n + 1
    else:
        print n

入力は常に小数点付きの実数ということなので、入力を整数部と小数部に分けた文字列として解析している。

提出した解答では、小数部の文字列を/= 10などと割っていって、'0.5'以上になるか判定していたのが、NGだった模様。

  • B. Help Chef Gerasim

BもAと同じく、後でsystem testを通したもの。

n = int(raw_input())
li = [(int(raw_input()), i + 1) for i in xrange(n)]
li.sort()
mx = li[-1]
mn = li[0]

if mx[0] == mn[0]:
    print "Exemplary pages."
    exit(0)

if (mx[0] - mn[0]) % 2 == 1:
    print "Unrecoverable configuration."
    exit(0)

val = (mx[0] - mn[0])/2
vv = mn[0] + val
li.pop(0)
li.pop()

if len(li) != len([x for x in li if vv == x[0]]):
    print "Unrecoverable configuration."
    exit(0)

print "{0} ml. from cup #{1} to cup #{2}.".format(val, mn[1], mx[1])

実戦の解答では、

2

1

0

というケースで0.5mlづつには分割できないということで、

"Unrecoverable configuration."とするべきところが処理できず、

WAとなっていた。

問題に明記されているのだが、液体の量がIntegerで表現されるところが微妙な引っ掛け。

豆の数とかキャンディーの数とか加算名詞であれば対応できたと思うのだが。

総括・反省

  • A.

float変数は極力使うな。なるべく文字列かIntegerとして扱え。

という格言(今作った)通りの問題。

今回は文字列だけで間に合う問題なので、格言に従っておけば何の問題もなかったはず。

  • B.

問題に登場する人・物は理解を助けるイメージに過ぎないので、

一旦、問題を記号と数学的性質に抽象化し、そのレベルで考慮すべき条件に抜けがないか確認せよ。

これも格言(?)通りでした。液体なのにIntegerという具体例に微妙な点があるなら、

騙されないように整数として抽象化しておくべきでした。そうすれば、最大と最小の差が2で割れない時の扱いは、

"Unrecoverable configuration."にするくらいしか無さそうという予想がついたはず。

  • C.

codeforcesで付いたtagによると"brute force"なので、

総当たりで解けるらしいですが、同じ模様の違う並びを同じかどうか判定するという部分をどうするか想像付かない。

  • D.

これは英語ゲーっぽい。候補一人一人の前でコインをトスして表が出れば合格ってことなのか?

丁半博打のように候補に裏表を賭けさせてから、おもむろに王様がコイントスするのか?

色々なふるい分け方法がありそうなんだけど選別方法は問題文には含まれてないような。

方式も含めてトスが最小になるようにしろというのが題意なのか?

Petrさんも解けてないぞ。

  • E.

大学1年生の時なら解けてそうな問題。三角関数の公式とか忘れました。

学生時代なら、計算機なしで微分して極大極小を計算して後は値の代入のみというところまで

持っていくことはよくやったな。1時間で出来るかというと怪しいけど。

実は解析なしで、幾何だけで解けちゃったりするのかもしれまんが。

以上。

tatuyan_edsontatuyan_edson2011/07/23 20:41はじめまして。
Cは全部数え上げるという手もありますよ。
Dですが、そもそも題意が取れません。おっしゃるとおり、選別方法が書いておらず、意味がわからないからunratedと、Editrialに書いてありました。後日再アップするみたいなので、その時に意味がわかるかも知れません。

hide5stmhide5stm2011/07/23 22:14http://codeforces.com/blog/entry/2323
ありがとうございます。ホントですね。
総評みたいのが出てるのですね。

GabrielGabriel2012/07/09 23:11Whoa, things just got a whole lot eaiesr.

nqephnzmlsgnqephnzmlsg2012/07/10 15:44H7ATQc <a href="http://dsbenakwexdo.com/">dsbenakwexdo</a>

2011-07-09

Codeforces Beta Round #77 Div2

| 17:22 | Codeforces Beta Round #77 Div2 - Div2脱出のための日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #77 Div2 - Div2脱出のための日記 Codeforces Beta Round #77 Div2 - Div2脱出のための日記 のブックマークコメント

今回は金曜日の24:00から2時間という都合が良い時間だったため参戦。

結果

rating 1407 → 1438

points: 1164

  • A: 452 00:24
  • B: 712 01:12
  • C: Openのみ
  • D: Openのみ
  • E: 未Open

room 13: 11位

全体: 338位

でありました。

概要

  • A. Football

与えられた0と1からなる数列中に0か1が連続7個以上出現したら"YES",それ以外は"NO"

  • B. Lucky Numbers (easy)

ある10進数の数値の各桁が4と7のみからなり、さらに4と7の出現数が同じである場合、その数値をsuper lukey numberと呼ぶ。

数値nが与えられた時、その数値より大きいsuper lukey numberのうち最小のものを返せ。

  • C. Hockey

Openのみ。

文字列中を検索して、指定文字列が出現したら置き換える問題らしいが、

さらに細かい変換ルールがあるようで、例2がどうしてその変換になるか理由が解らず断念。

自分にとっては英語ゲー?のような形。

  • D. Volleyball

Openのみ。

交差点ごとにタクシーが停まっていて、それを乗り継いで最小コストで目的地に行きたい

という問題らしいが、最短経路問題はあまり経験がないので断念。

  • E. Horse Races

未Open。題名さえ見てなかった。

  • Hacks

BはTLEがあり得るので、その辺りでHackしようと考え、Bをlockしたものの

Hackの方法が分からず撃墜は断念。

総括

Aはいつものことながら引っ掛けのないやるだけ問題。

いかに早く理解して、タイプ数の少ない方式を考えるかが勝負。

今回の文字列中の連続の判定は、今後も良く使いそうなので、定番の判定方法を見つけて引き出しにしまっておかなくては。

Div1に定着するためには15分以内に解くのが目標と言えそう。

B以降の問題は解き方によっては、TLE(Time Limits Exceed)にかかります。

今回のBのような数値の問題は、数値のまま解くか文字列にして解くかがTLEの別れ道だったりします。

    • 条件を満す数値(今回はsuper lukey number)の判定方法
    • 条件を満す数値の検索方式
    • 条件を満す数値の作成方法

を数値・文字列のどちらでやるのがアルゴリズム的に速くて簡単かを考えています。

今回のsuper lukey numberでは、

    • [1, 10^9]の範囲でのsuper lukey numberの出現頻度はかなり低い。

2桁のものは2/89、3桁のものは0、4桁では6/9899...

    • super lukey numberの判定は簡単
    • 数値n以上をインクリメントして1つづつ判定していくのは、10^9近辺で行うとTLE可能性が大
    • 数値n以上のsuper lukey numberを2分探索など効率的に探すアイデアはなし
    • super lukey numberの文字列による作成は可能

ということで、与えられた数値nの桁数を求めて、桁数が同等以上のsuper lukey numberを

生成し、nと比較して最小のsuper lukey numberを求める作戦を取りました。

super lukey numberの生成は、4と7の出現回数が同じ文字列の全組合せを作るだけです。

今回は、再帰関数を使ったのですがもっとお手軽な方法があるような気がするので見つけなくては。

Div1定着には30分以内で解かないといけないでしょう。

とりあえず、Div2でA,Bの2問は確保できる自信は付いてきました。

A,Bを毎回確実に取れれば、rating 1500に定着できそうな気がします。

Div1に上がるためには、あともう1問取れるかが鍵と思われます。

今後の対策

あとA,Bは自信が持ててきたので、Cを取る練習、そして今回のようにCが自分にとって

英語ゲーとなった場合のD対策が課題になります。

なのでとりあえずC,D過去問の練習。C,Dの問題の傾向が掴めたら

(たぶん図形、グラフ系問題が多い?)その分野の練習。

他にA,Bで撃墜(Hack)できるようにHackの仕方を調べよう。

ちなみにcodeforcesでは、撃墜されても再提出が可能らしいので、システムテストで堕ちるより、

撃墜された方がなんぼかマシです。もしかすると早めに撃墜すると感謝されちゃうかもしれません。

ここがSRMとは大分違うのでチャンスがあればバンバン撃墜しちゃいましょうw

解答詳細

A. Football

与えられた0と1からなる数列中に0か1が連続7個以上出現したら"YES",それ以外は"NO"

judge()で数列を1文字づつ0か1か判定していますが、ちょっと間抜け。

文字列"0000000","1111111"の探索をするように書いた方がコーディングが速く終りそう。

それをやるには、文字列内の探索系の勉強不足なのでそれも練習しよう。

def judge(line):
    zero = 0
    one = 0
    old = -1
    for i in line:
        if not (i == '1' or i == '0'):
            continue
        if old == 1 and i == '1':
            one += 1
            if one >= 7:
                return True
        elif old == 0 and i == '0':
            zero += 1
            if zero >= 7:
                return True
        else:
            old = int(i)
            if i == '1':
                one = 1
                zero = 0
            else:
                zero = 1
                one = 0
    return False

import sys

for line in sys.stdin:
    if judge(line):
        print "YES"
    else:
        print "NO"
B. Lucky Numbers (easy)

ある10進数の数値の各桁が4と7のみからなり、さらに4と7の出現数が同じである場合、その数値をsuper lukey numberと呼ぶ。

数値nが与えられた時、その数値より大きいsuper lukey numberのうち最小のものを返せ。

super lukey numberは、小さい順に47,74,4477,4747,4774,7447,7474,7744,...



def rec(l, m4, m7, li):
    if m4 == 0 and m7 == 0:
        li.append(int(''.join(l)))
    if m4 > 0:
        l4 = l[:]
        l4.append('4')
        rec(l4, m4-1, m7, li)
    if m7 > 0:
        l7 = l[:]
        l7.append('7')
        rec(l7, m4, m7-1, li)

def super_lucky(m):
    li = []
    rec([], m/2, m/2, li)
    li.sort()
    return li

def search(n):
    m = len(str(n))
    if m % 2 == 1:
        m += 1
    li = super_lucky(m)
    for i in li:
        if n <= i:
            return i
    li = super_lucky(m+2)
    for i in li:
        if n <= i:
            return i

import sys

for line in sys.stdin:
    print search(int(line))

TiianTiian2012/07/10 05:17A rolling stone is worth two in the bush, thkans to this article.

xrnmxwpxrnmxwp2012/07/10 16:21KNwiWr <a href="http://dllzltakzyht.com/">dllzltakzyht</a>

vwxgywosvwxgywos2012/07/11 20:49N1J4wW , [url=http://ckrvvuzxsvjg.com/]ckrvvuzxsvjg[/url], [link=http://zopolcvfqxgj.com/]zopolcvfqxgj[/link], http://mpsrwqltoohp.com/

pefvcczjpefvcczj2012/07/12 12:34JlgsLb <a href="http://rkbmhvjucnwc.com/">rkbmhvjucnwc</a>