Leetcode: Unique Paths

 To make some practice on DP, "Unique Paths"@Leetcode is solved.

Probably a typical one, and super easy.
https://leetcode.com/problems/unique-paths

import numpy as np

class Solution:

def uniquePaths(self, m: int, n: int) -> int:

dp = np.zeros((m,n),np.int32)

dp[0,:]=1

dp[:,0]=1

for j in range(1,m):

for i in range(1,n):

dp[j,i] = dp[j-1,i] + dp[j,i-1]

return dp[m-1][n-1]

Sudoku solver @LeetCode

 Not elegant at all, but readable sudoku solver.

https://leetcode.com/problems/sudoku-solver/

class Solution(object):

    

    def checkNew(self, i,j,k,board):

        

        for jj in range(9):

            if board[i][jj] == str(k):

                return False

        for ii in range(9):

            if board[ii][j] == str(k):

                return False

        

        iB = i//3

        jB = j//3

        b = []

        for ii in range(3):

            for jj in range(3):

                if board[3*iB+ii][3*jB+jj] == str(k):

                    return False

        

        

        return True

    

    def backtrack(self, board):

# Find a blank element. The search direction does not a matter,

# but row-oriented here.

        for i in range(9):

            for j in range(9):

                if board[i][j] == ".":

# If blank, try numbers from 1 to 9

                    for k in range(9):

                        if self.checkNew(i,j,k+1,board): # Check if k is OK            

                            board[i][j]=str(k+1)

                            if self.backtrack(board): # Try next blank until OK

                                return True

                            else:

                                board[i][j] = "." # if inconsistent, step back

                    else:

                        return False

        return True

    

    

    def solveSudoku(self, board):

        """

        :type board: List[List[str]]

        :rtype: None Do not return anything, modify board in-place instead.

        """

        self.backtrack(board)

Unique Paths III @LeetCode

Just to wake up; 

980. Unique Paths III
https://leetcode.com/problems/unique-paths-iii/

class Solution:

    

    def checkIfReachable(self,curPoint,walkable, grid):

        (i,j) = curPoint

        #print(curPoint)

        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):

            return 0

        

        if grid[i][j]==2:

            if len(walkable)==0:

                return 1

            else:

                return 0

        

        if curPoint not in walkable:

            return 0

        

        walkable.remove(curPoint)

        

        num1 = self.checkIfReachable((i+1,j  ),walkable.copy(),grid)

        num2 = self.checkIfReachable((i-1,j  ),walkable.copy(),grid)

        num3 = self.checkIfReachable((i  ,j+1),walkable.copy(),grid)

        num4 = self.checkIfReachable((i  ,j-1),walkable.copy(),grid)

        

        return num1+num2+num3+num4

    

    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        

        walkable = []

        

        for i in range(len(grid)):

            for j in range(len(grid[0])):

                if grid[i][j] == 0:

                    walkable.append((i,j))

                elif grid[i][j] == 1:

                    walkable.append((i,j))

                    start = (i,j)

        

        numPath = self.checkIfReachable(start,walkable,grid)

        return numPath

TDPC C

 というわけで、TDPC　C。

考え方は簡単で、
(1) 自分の対戦相手が今まで生き残ってくる確率
(2) 自分が勝てる確率
(3) 自分が今まで生き残って来れた確率

を掛け算して足しあわせると現在自分が勝ち上がれるかどうかの確率になる
（かどうか、いまいち直感的でないんだけど、答えはそれであってる）。

どっちかというと対戦相手を見つけてくるループが面倒で、私は予めリストアップした(groupがそれ)

https://atcoder.jp/contests/tdpc/submissions/18020128

import numpy as np

def calcProb(P,Q,R):

   RP = R[P]

   RQ = R[Q]

   prob = 1.0 / (1.0+10.0**((RQ-RP)/400.0))

   return prob

def calcConsequtiveProb(iP,iG,R,dp,iBat):

   prob = 0.0

   for i in iG:

      prob += calcProb(iP,i,R)*dp[iBat-1,i]

   return prob

N = int(input())

numPerson = 2**N

R = []

for i in range(numPerson):

   R.append(float(input()))

group = []

group.append([ [i] for i in range(numPerson)])

for i in range(1,N+1):

   locGroup = []

   prevGroup = group[i-1]

   for j in range(len(prevGroup)//2):

      lg1 = prevGroup[2*j  ]

      lg2 = prevGroup[2*j+1]

      locGroup.append(lg1+lg2)

   group.append(locGroup)

dp = np.zeros((N+1,numPerson),np.float)

dp[0,:] = 1.0

for iBat in range(1,N+1):

   locGrp = group[iBat-1]

   for iGrp in range(len(locGrp)//2):

      lg1 = locGrp[iGrp*2  ]

      lg2 = locGrp[iGrp*2+1]

      for iPerson in lg1:

         prob = calcConsequtiveProb(iPerson,lg2,R,dp,iBat)

         dp[iBat,iPerson] = dp[iBat-1,iPerson]*prob

      for iPerson in lg2:

         prob = calcConsequtiveProb(iPerson,lg1,R,dp,iBat)

         dp[iBat,iPerson] = dp[iBat-1,iPerson]*prob

for i in range(numPerson):

   print(f'{dp[N,i]:.8f}')

TDPC(Typical DP Contest) A

 二次元配列にしないで解いてる人もいるみたいだけど私にはさっぱりわからないのでとりあえず二次元で。
”これまでに作成可能な点数であることが確認できれば、現在確認中のスコアを足した点数も作成可能である”ことを二次元配列で表現。

最終的には、最後の行を見れば作れる点数の個数がわかる。

https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

import numpy as np

N = int(input())

line = input().split()

p = []

p.append(0)

for i in line:

   p.append(int(i))

dp = np.zeros((len(p),sum(p)+1),np.int8)

dp[0,0]=1

for j in range(1,len(p)):

   for i in range(0,sum(p)+1):

      if dp[j-1,i]:

         dp[j,i+p[j]] = 1

         dp[j,i] = 1

#print(dp)

print(sum(dp[len(p)-1,:]))

ABC129 C

DP の勉強のために下記ブログの問題リストを解いてみている。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a

DPだとわかっているからできるけど、自分でいきなりはまだ思いつけなさそう。
https://atcoder.jp/contests/abc129/tasks/abc129_c

import sys

line = input().split()

N = int(line[0])

M = int(line[1])

dp = [0] * (N+1)

NA = [1] * (N+1)

for i in range(M):

   NA[int(input())] = 0

for i in range(N):

   if NA[i+1] == 0 and NA[i]==0:

      print(0)

      sys.exit(0)

dp[0] = 1

dp[1] = 1

for i in range(2,N+1):

   if NA[i] == 0:

      dp[i] = dp[i-1]

   elif NA[i-1] == 0:

      dp[i] = dp[i-1]

   else:

      dp[i] = dp[i-1]*NA[i-1] + dp[i-2]*NA[i-2]

print(dp[N]%1000000007)

 

Paiza Rank-S

 

In the end, I've reached Rank-S (top 2%).

Paiza Rank-A

After several attempts, I reached Rank-A in Paiza. 
Hope this helps my job hunting :)

ABC 158 C

S = input().split()
[A,B] = [int(i) for i in S]

Alow = A*100//8
Ahi  = (A+1)*100//8

Blow = B*100//10
Bhi  = (B+1)*100//10

#print(Alow,Ahi,Blow,Bhi)

Aran = [i for i in range(Alow,Ahi+1) if int(i*0.08) == A]
Bran = [i for i in range(Blow,Bhi+1) if int(i*0.10) == B]


resRan = sorted(list(set(Aran) & set(Bran)))
#print(resRan)
if len(resRan) !=0:
  print(resRan[0])
else:
  print(-1)

S = input().split()
[A,B] = [int(i) for i in S]

Alow = A*100//8
Ahi  = (A+1)*100//8

Blow = B*100//10
Bhi  = (B+1)*100//10

#print(Alow,Ahi,Blow,Bhi)

Aran = [i for i in range(Alow,Ahi+1) if int(i*0.08) == A]
Bran = [i for i in range(Blow,Bhi+1) if int(i*0.10) == B]


resRan = sorted(list(set(Aran) & set(Bran)))
#print(resRan)
if len(resRan) !=0:
  print(resRan[0])
else:
  print(-1)

うーん。焦ってるとこれぐらいのことも思いつかないもんだなぁ。

S = input().split()

[A,B] = [int(i) for i in S]

Alow = A*100//8

Ahi  = (A+1)*100//8

Blow = B*100//10

Bhi  = (B+1)*100//10

Aran = [i for i in range(Alow,Ahi+1) if int(i*0.08) == A]

Bran = [i for i in range(Blow,Bhi+1) if int(i*0.10) == B]

resRan = sorted(list(set(Aran) & set(Bran)))

if len(resRan) !=0:

  print(resRan[0])

else:

  print(-1)

Atcoder ABC157 E

下記コード、pypyだと通るけど、python3だとTLEする。

https://atcoder.jp/contests/abc157/submissions/10530007

from collections import defaultdict
import bisect
alphabet="abcdefghijklmnopqrstuvwxyz"
bS = int(input())
S= input()
nQ = int(input())
S = [i for i in S]
query = []
for i in range(nQ):
  query.append(input().split())
locs =defaultdict(list)
for i,char in enumerate(S):
    locs[char].append(i)
   
def countChars(iter,ss,ee):
  nChar = 0
  for i in alphabet:
    if len(locs[i]) == 0:
      pass
    else:
      sptr = bisect.bisect_right(locs[i],ss)
      eptr = bisect.bisect_left(locs[i],ee)
      if sptr == eptr:
        if sptr < 1 or sptr > len(locs[i]):
          continue
        else:
          if locs[i][sptr-1] == ss:
            nChar+=1
      else:
        nChar += 1
  return nChar
   
 
res = []
for iter,iQ in enumerate(query):
  if int(iQ[0]) == 2:
    res.append(str( countChars(iter,int(iQ[1])-1,int(iQ[2])) ))
  if int(iQ[0]) == 1:
    location = int(iQ[1])-1
    curChar  = S[location]
    if curChar != iQ[2]:
      locs[curChar].remove(location) #remove from old
      bisect.insort(locs[iQ[2]],location)
      S[location] = iQ[2]
     
print(" ".join(res))