Hatena::Grouptopcoder

prosho奮闘記 RSSフィード

2011-12-10

pythonのitertools

00:56 | はてなブックマーク - pythonのitertools - prosho奮闘記

昨日コドフォに参戦しました。結果はさておき、その際気付いた俺用メモを書いときます。

・二次元のベクトルを扱うなら複素平面で考えても面白い。

昨日のコドフォDiv2. Dは

if((a+bi)*i == (c+di) || (a+bi) == (c+di)*i){

....

}

みたいな感じで正方形判定しました。(超大雑把な説明なのでこれでわかったら凄いかもw)

実際は長方形判定を利用したほうが圧倒的に可読性が高いのでそちらをオススメします。


pythonのcombinations()

pythonのitertoolsにpermutations, combinationsというメソッドが用意されています。

使い方は、

>> from itertools import *
>> # 第一引数はiterable
>> for p in permutations(range(5)):
>>     print p
>> ......
>> for c in combinations(range(5), 2): # 5C2
>>     print c
>> ......

という感じ。

今まで、permutationsはC++のalgorithmのnext_permutation()しか使わなかった(知らなかった)のでpythonに用意されていると知って驚き。

さらにcombinations()は感動しました。自分で実装するのはなかなか大変。

まれに、組み合わせ生成できたら楽だなーと思うような問題があります。

combinationを生成するのは難しいので、組み合わせを生成する必要がない解き方がメインで実際一番効率的なアルゴリズムの場合であることが普通ですが、そういう本解が思いつかなかった時に、combinations()が役立つかもしれません。

腕に自信のある人はpermutations()やcombinations()を実装してみてはどうでしょうか。

2011-10-31

twitter

12:51 | はてなブックマーク - twitter - prosho奮闘記

@_prosho_で最近始めました。よろしくお願いします~。

今はマラソンに参戦中です。

2011-10-09

GCJJ 2011 決勝

10:12 | はてなブックマーク - GCJJ 2011 決勝 - prosho奮闘記

Aのsmallとlargeしか解けず, しかも250位付近でTシャツもらえないショボイ結果 orz

次回は (もしあれば, ) 必ずとりたい.

被害者多数のBと心中しました.

C-smallは全探索でいいのかー.

2011-09-24

Codeforces #88

06:31 | はてなブックマーク - Codeforces #88 - prosho奮闘記

結果:oxxxx 1453->1559

Aは416pt. BはSystem TestでTLE. CはPretestでTLE.

Bを見なおして着実に取ってれば上位20%にいれたかと思うと悔しい。

一発で正解が書けるかどうかが実力なんですけどね。。。

それにしても上位十傑は本当にどういう頭の回転をしてるんだw

今回、今の自分のしょぼさの原因はアルゴリズム云々よりも、

単純に実装力の無さだとわかって一歩前進した。

まずは着実に思ったことを実装できる基礎力を身につけよう。

欲張らずに、解ける問題を着実に解くのが肝要ですね。

追記:

やっぱり、Pythonは計算時間的に不利っぽいです。

117BをPythonで書いてTLEしなかった方は是非とも教えていただきたいです。

Pythonは数値計算がC系に比べて遅いのだろうか?

C++で書いて通るコードを参考に、同じ物をPythonで書いたら(↓のコード)通りませんでした。

なので、数値計算が多く計算時間が怪しい問題は、C++でこれから書くようにしないと・・・orz

文字列処理の問題とかはPythonをお勧めしますが。

これからPythonで参加しようとしている方はご注意を。

import sys

def solve():
    a, b, mod = map(int, sys.stdin.readline().split())
    for i in xrange(1, mod):
        if i > a: break
        if (mod-(i*10**9)%mod) % mod > b:
            return "1 %09d" % i
    return "2"
    
print solve()

追記の追記:上記の問題点を解決してそうな、Cythonなる言語があるそうです。これが使用可になる日はくるのか...?(いや、来ないなw)

2011-09-18

Codechef 不正解晒し

04:11 | はてなブックマーク - Codechef 不正解晒し - prosho奮闘記

ダメなところに気付いたら教えて下されば嬉しいです。。

またPythonコードのhack的なこともあれば気が向いたら教えて下さい。

あと、CodeChefって他人のコードを覗けるのでしょうか?


Digit Rotation

Wrong Answerが返ってくるんですが、反例がわからない。。


import sys

def eraseZero(string):
    memo = -1
    for i in xrange(len(string)):
        if string[i] == '0':
            memo = i
        else:
            break
    return string[memo+1:]

def bigger(b, s):
    if len(b) > len(s):
        return True
    if len(b) < len(s):
        return False
    for i in xrange(len(b)):
        if b[i] > s[i]:
            return True
        if b[i] < s[i]:
            return False
    return False

def solve():
    T = int(sys.stdin.readline())
    for case in xrange(T):
        n = sys.stdin.readline().strip()
        n = eraseZero(n)
        leng = len(n)
        maxi = "0"
        if leng >= 2:
            now = n
            for i in xrange(leng):
                if len(now) >= 2:
                    now = eraseZero(now[1:]+now[0])
                else:
                    break
                if bigger(now, maxi):
                    maxi = now
            now = n
            for i in xrange(leng):
                if len(now) >= 2:
                    now = eraseZero(now[-1]+now[0:len(now)-1])
                else:
                    break
                if bigger(now, maxi):
                    maxi = now
            if n[1] != '0' and bigger(n, maxi):
                maxi = n
            if n[1] == '0' and n[-1] != '0' and bigger(n, maxi):
                maxi = n
            print maxi
        else:
            print n

solve()


Hotel

これもWAになる理由がわからない。。

import sys

def solve():
    T = int(sys.stdin.readline())
    for case in xrange(T):
        N = int(sys.stdin.readline())
        arr = map(int, sys.stdin.readline().split())
        leav = map(int, sys.stdin.readline().split())
        res = 0
        inn = 0
        now = (arr+leav)
        now.sort()
        now = list(set(now))
        
        for t in now:
            for i in xrange(N):
                if arr[i] == t:
                    inn += 1
                if leav[i] == t:
                    inn -= 1
            res = max(res, inn)
            
        print res

solve()

Digit SumもTLEでしたがこれは原因がわかりました。

SRM Div2 &Codeforces & CodeChef 報告

03:57 | はてなブックマーク - SRM Div2 &Codeforces & CodeChef 報告 - prosho奮闘記

まず、Div1復帰をかけたSRMDiv2

結果:1100(?忘れた)->1087(?忘れた)

下がりました。。Easyに時間がかりすぎ&Medium開いてから間違いに気付きresubmitで100/250 score, Mediumも遅く310/500 scoreくらい。Challenge Phaseで+2/-2で+50score。Hardも言われてみたらすごく簡単な問題だった。。

まさかの大混戦の回でしたね。。

Codeforces Div2にPythonで初参戦もA,Bしかできず、1500->1453..Div1にいくにはせめてあと二問解けなきゃいけないのか。。

CodeChefもPythonで初参戦。

問題は凄くとっつきやすく、実装も楽そうなのだが、WATLEが帰ってきて結局正解0問。

すごく面白かったけど、殆どの人がC/C++/Javaを使っていたから不安になった。

Pythonは一応light-weightedな言語だから、実行時間的なことはまぁ大丈夫だと思っていたが今は疑問符がつく。。

あああ、どれもパッとせず悔しい。

一皮むけるために復習せねば!

明日のSRMは場所的に参戦できるか不明。。

DoraDora2012/11/15 11:03Always a good job right here. Keep rolling on trhuogh.

stxczctstxczct2012/11/16 06:11F6T9Tt <a href="http://mhbhrlebrmkp.com/">mhbhrlebrmkp</a>

bynwaabynwaa2012/11/17 05:359Gzuqb , [url=http://jabeljwazqbi.com/]jabeljwazqbi[/url], [link=http://cqtitcfhhwfk.com/]cqtitcfhhwfk[/link], http://ppsthbsojxyf.com/

oqotyshjcmgoqotyshjcmg2012/11/17 12:34hXdd70 <a href="http://dioglpeablzw.com/">dioglpeablzw</a>

gvslhzbimkgvslhzbimk2012/11/17 21:54KxEwzM , [url=http://emmkzblgoprt.com/]emmkzblgoprt[/url], [link=http://vhcnywpooyda.com/]vhcnywpooyda[/link], http://wlufhrgjelvg.com/