naoya_t@hatenablog

いわゆるチラシノウラであります

yukicoder 168

twitterで見て、どんな感じなんだろうと思って覗いてみた
yukicoder contest 168 - yukicoder

参加は初めてかな

python2縛りで
4完33位

参加登録などはありません。問題が公開されたら、回答を提出すれば良いです。
誤回答によるペナルティーはありません。

A. [No.536] 人工知能 ★(84)

aiで終わる文字列ならそこをAIに変えて、そうでなければ-AIを付け足す

name=raw_input().rstrip()
if name.endswith('ai'):
  print name[:-2] + 'AI'
else:
  print name+'-AI'

B. [No.537] ユーザーID ★☆(67)

約数の数を数える問題?と思って書いたやつがWA
文字列としてconcatして同一になるものは1つとして数えないといけないのか
具体的な例が思いつかなかったけど
とりあえずconcatしてsetに放り込んで、len(set)を返してAC
// あ、例えば 99=3x33=33x3

n=int(raw_input())
s=0
a=1
xs=set()
while True:
  if n%a==0:
    if n==a*a:
       x=str(a)*2
       xs.add(x)
       break
    else:
       x1=str(a)+str(n/a)
       xs.add(x1)
       x2=str(n/a)+str(a)
       xs.add(x2)
  a+=1
  if n<a*a: break
print len(xs)

C. [No.538] N.G.S. ★★(64)

漸化式がどうとか
高校数学っぽい

b1,b2,b3=map(int,raw_input().rstrip().split(' '))
r=float(b3-b2)/float(b2-b1)
d=float(b3)-r*b2
b4=r*b3+d
print int(round(b4))

D. [No.539] インクリメント ★★☆(51)

文字列に含まれる最後の整数をインクリメントしたやつを返す
re.finditer()で探して、見つかった部分をstr(int(s)+1)して、って書いてTLE
10万桁をstr(int(s)+1)するのは重いらしい(そりゃそうだ)
繰り上がり計算するだけだし自前で実装してAC(当初よりめちゃ長くなった)

def solve(s):
  L = len(s)
  sR = s[::-1]
  b=-1
  e=-1
  for i in xrange(L):
    if sR[i] < '0' or '9' < sR[i]: continue
    b=e=i
    while e<L:
      if '0' <= sR[e] <= '9':
        e += 1
        continue
      break
    break
  if b==-1:
    return s
  else:
    b, e = L-e, L-b 
    nu = s[b:e]
    pad=0
    for i in xrange(b,e):
      if s[i]=='0': pad += 1
      else: break
    if b+pad == e:
      pad -= 1

    plus=[]
    body = s[b+pad:e]
    u=1
    for c in body[::-1]:
      cu = ord(c)+u
      if cu == 58:
        u, ch = 1, '0'
      else:
        u, ch = 0, chr(cu)
      plus.append(ch)
    if u==1:
      plus.append('1')
      if pad > 0:
        pad -= 1
    return s[:b] + ('0'*pad) + ''.join(plus[::-1]) + s[e:]

n=int(raw_input().rstrip())
for i in range(n):
  s=raw_input().rstrip()
  print solve(s)

E. [No.540] 格子点と経路 ★★★★★(7)

線分の長さではなく「個数」で、その最大値。
何回曲がるかって事か。
パターンがあるのかな。とりあえずパス

F. [No.541] 3xNグリッド上のサイクルの個数 ★★★★(9)

f:id:n4_t:20170701103158p:plain
左からDPで解けないかな、と思って
各行の3グリッド?ブロック?を上からA,B,Cと置くとして
この行で終わるサイクルが内包するブロックはA,AB,ABC,B,BC,Cの6通り(※後述)
次の行でそれに付け足す(あるいは付け足さない)としたら
AにくっつけられるのはA,AB,ABCの3通り
ABにくっつけられるのはA,AB,ABC,B,BCの5通り
ABCにくっつけられるのはA,AB,ABC,B,BC,Cの6通り
BにくっつけられるのはAB,ABC,B,BCの4通り
BCにくっつけられるのはAB,ABC,B,BC,Cの5通り
CにくっつけられるのはABC,BC,Cの3通り
空ブロックにくっつけることで手前の列で終わらせたり
この行から新たに始まるサイクルがあったり、を
DPで
って
ちょっと待て
1≦N≦10^18

ああ、行列の累乗でね
6通り+手前で終わる+新たに始まる、の8段で
8x8行列を累乗して、初期値に掛けて

答えあわないし
ってところで試合終了;;

↑↑
これだと、凹を左/右に倒したようなパターンを拾えてないんだよね
(左から続いてるサイクルで、凹を右に倒したA+C型を考慮してなかった)
右に凹なサイクルと左に凹なサイクルをくっつけちゃうと単純閉路じゃなくなっちゃうし
これどうしたらいい?
開いた凹(というか □ □)と閉じた凹を区別するだけで行ける?
とすると10x10行列?
→AC(わーい)

MOD = 1000000007

N = int(raw_input().rstrip())


def zero(R, C):
    return [[0] * C for i in range(R)]


def eye(n):
    A = zero(n, n)
    for i in range(n):
        A[i][i] = 1
    return A


I = eye(10)

A = [[1, 1, 1, 0, 0, 0,  1, 0,  0, 1],  # 0..
     [1, 1, 1, 1, 1, 0,  0, 0,  0, 1],  # 01.
     [1, 1, 1, 1, 1, 1,  0, 1,  0, 1],  # 012
     [0, 1, 1, 1, 1, 0,  0, 0,  0, 1],  # .1.
     [0, 1, 1, 1, 1, 1,  0, 0,  0, 1],  # .12
     [0, 0, 1, 0, 1, 1,  1, 0,  0, 1],  # ..2
     [0, 0, 1, 0, 0, 0,  1, 0,  0, 0],  # 0.2 <closed>
     [1, 0, 0, 0, 0, 1,  0, 1,  0, 1],  # 0.2 <open>

     [1, 1, 1, 1, 1, 1,  1, 0,  1, 0],  # stop here
     [0, 0, 0, 0, 0, 0,  0, 0,  0, 1]]  # start here


def mul(A, B):
    R, C, X = len(A), len(B[0]), len(B)
    # assert len(A[0]) == len(B)
    D = zero(R, C)
    for r in range(R):
        for c in range(C):
            k = 0
            for i in range(X):
                k += A[r][i] * B[i][c]
            D[r][c] = k % MOD
    return D


def mul1(A, b):
    Ab = mul(A, [[bi] for bi in b])
    return [r[0] for r in Ab]


def pow(A, n):
    if n == 0:
        return I
    elif n == 1:
        return A
    B = pow(mul(A, A), n/2)
    if n % 2 == 1:
        B = mul(B, A)
    return B


X = pow(A, N+1)
x = mul1(X, [0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
print x[8] % MOD