Codeforces Beta Round #26 (Codeforces format) - 君はまるで砂漠に咲く、一輪の花。

A. Almost Prime

number theory

ざっくりと大意

・約数に素数が厳密に2つ含まれている数をカウントする？
・例えば6なら2,3が、18も同様に2,3。4は2だけ、9は3だけ。

方針のようなもの

・全部さがす。

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
n=int(raw_input())
prime=[]
ans=0
#nまでの素数リストを用意
for i in range(2,n+1):
    if all(i%p!=0 for p in prime):
        prime+=[i]
#1は省略で2からnまで探す
for j in range(2,n+1):
#探索対象が新しくなるたびに素数カウンターを初期化。
    chk=0
#現在の探索してる数が約数に素数が2つであるものかチェックする。
#例えばjが6ならば2,3がchkにカウントされる。
    for k in range(2,j):
        if j%k==0 and (k in prime):
            chk+=1
    if chk==2:
        ans+=1
print ans

えーと、、なんかもっと楽な探し方があったようです。今回も2539385のdaidailanlanさんを参照。

#!/usr/bin/python
n=input()
c=[0]*(n+1)
for i in range(2,n):
    if not c[i]:
        for j in range(i,n+1,i):
            c[j]+=1
print c.count(2)
#print c すると
#[0, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2]

何か数学で法則とかなんだろうか？これで確かに6,10に該当するであろう箇所が2になっている。

B. Regular Bracket Sequence

greedy

ざっくりと大意

・なんか()がきちんと閉じられた長さを数える？

方針のようなもの

・(が1つ以上あるときに)出現で閉じ成立らしいのでソレをカウント。

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
l,ans=0,0
for i in raw_input():
    if i=='(': l+=1
    elif l: l-=1; ans+=1
print ans*2

ansは回答時に*2でも+=2でも影響はない様子。勝手に連続して成立と思い込んでいたが例えばTest7で ()()(()(((　()()が連続したあとで(()となっているが続けて加算される。
自分でも何を言ってるのか状態ですが。。。