Hatena::Grouptopcoder

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

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>