163AC - ABC054C: One-stroke Path

競プロ DFS
ABC54-C (300 points)
問題

与えられた N 頂点 M 辺の単純無向グラフについて, 頂点 1 を始点として全ての頂点を 1 度だけ訪れるパスを数え上げる.

  • 2 \leq N \leq 8
  • 0 \leq M \leq N(N - 1)/2
  • 1 \leq a_i < b_i \leq N
方針
  • DFSで列挙. 
# input
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [set() for _ in range(N)]

for a, b in G:
    edges[a - 1].add(b - 1)
    edges[b - 1].add(a - 1)

def dfs(start, edges, path):
    path.append(start)
    if len(path) == N:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, edges, path)
    path.pop()
    return ans    

print(dfs(0, edges, []))

162AC - ABC053C: X: Yet Another Die Game

競プロ
ABC053-C (300 points)
問題

サイコロの好きな面が上になるように置き, 以下の操作を必要な回数行うとき, x 点以上得るために必要な最小の操作回数を求める.

  • 操作：サイコロを手前、奥、左、右のどれかの方向に90°だけ回転させる。その後、上を向いている面に書かれた数を y として y 点得る.
  • 1 \leq x \leq 10^{15}
  • 入力は全て整数.
方針

明らかに 6 → 5 → 6 → 5 → \cdots とするのがベスト. 

# input
x = int(input())

q, r = divmod(x, 11)

if r > 6:
    ans = 2 * q + 2
elif r > 0:
    ans = 2 * q + 1
else:
    ans = 2 * q

print(ans)

161AC - ABC103C: Modulo Summation

競プロ
ABC103-C (300 points)
問題

N 個の正整数 a_1, a_2, \ldots, a_N が与えられるとき, 非負整数 m に対して f(m) を以下のように定義する.
f(m) = \sum_{i = 1}^N (m \ mod \ a_i)
このとき, f の最大値を求める.

  • 2 \leq N \leq 3000
  • 2 \leq a_i \leq 10^5
  • 入力は全て整数.
方針
  • f の第 i 項について考えると m \ mod \ a_i の最大値は a_i - 1.
  • m = a_1 \times a_2 \times \cdots \times a_N - 1 とすると, 各項が最大値を取るので, このとき f も最大値. 
# input
N = int(input())
A = list(map(int, input().split()))
 
ans = sum(A) - N
 
print(ans)

156AC - ABC054B: Template Matching

numpy 競プロ
ABC054-B (200 points)
問題

N \times N の行列 A と M \times M の行列 B が与えられたとき ( M \leq N), B が A に含まれるかどうかを判定する.

  • 1 \leq M \leq N \leq 50
方針
  • 総当たり. 
import numpy as np

# input
N, M = map(int, input().split())
A = [list(input()) for _ in range(N)]
B = [list(input()) for _ in range(M)]

A_arr = np.array(A)
B_arr = np.array(B)

for i in range(N - M + 1):
    for j in range(N - M + 1):
        if np.array_equal(A_arr[i:i + M, j:j + M], B_arr):
            print('Yes')
            exit()

print('No')

154AC - ABC055C: Scc Puzzle

競プロ
ABC055-C (300 points)
問題

N 個の 's' と M 個の 'c' を組み合わせて 'scc' という文字列をいくつ作れるか求める. ただし 'c' を 2 個組み合わせて 1 個の 's' を作れるものとする.

  • 1 \leq N, M \leq 10^{12}
  • 入力は全て整数
方針
  • 2 * N <= M：'s' は全て使用可能 + 残った 'c' で 'scc' を作る.
  • 2 * N > M ：使用できない 's' があるので, 'c' を全てそのまま使う. 
import math

# input
N, M = map(int, input().split())

if 2 * N <= M:
    ans = N + math.floor((M - 2 * N) / 4)
else:
    ans = math.floor(M / 2)

print(ans)

153AC - ABC056C: Go Home

競プロ
ABC056-C (300 points)
問題

時刻 0 に座標 0 からスタートして, 時刻 i に \{+i, 0, -i \} 動くことができるとき, 座標 X に到達できる最短時刻を求める.

  • 1 \leq X \leq 10^{9}
  • 入力は全て整数
方針
  • X = 10 ぐらいまで実験してみる.
  • t までに到達できる座標は \sum_{i = 0}^{t} i まで.
  • \sum_{i = 0}^{t} i までの座標であれば時刻 t までに到達可能.
  • よって \sum_{i = 0}^{t - 1} i < X \leq \sum_{i = 0}^{t} i となる tを求めればよい.
# input
X = int(input())

i = 1
while 2 * X > i * (i + 1):
    i += 1

print(i)

147AC - ABC058C: Digits in Multiplication

競プロ
ABC057-C (300 points)
問題

2 つの整数 A, B に対して, F(A, B) を「 10 進表記における, A の桁数と B の桁数のうち大きい方」と定義する.
このとき, 整数 N に対して, 2 つの正の整数 A, B が N = A \times B を満たすように動くとき, F(A, B) の最小値を求める.

  • 1 \leq N \leq 10^{10}
  • 入力は全て整数
方針
  • N = A^2 となるとき（ N が平方数）がベスト, N = 1 \times N となるとき（ N が素数）が最悪.
  • i = \lfloor \sqrt{N} \rfloor から始めて, 約数が見つかるまで i を 1 ずつ減らしていく. 
import math

# input
N = int(input())

i = int(math.sqrt(N))

while i:
    if N % i == 0:
        print(len(str(N // i)))
        break
    else:
        i -= 1