log 2021-09-07
sport
cf 1567 복습
C
https://codeforces.com/contest/1567/problem/C
hint
생각보다 풀이/해답 코드 구현 모두 엄청 간단한 문제였다. 단순한 발상 두 개만 떠올리면 되는 것이었다.
- 어떤 양수 n을 만드는 음이 아닌 정수 쌍의 개수는?
- 해당 문제에서 덧셈이 정상적으로 적용되는 부분은?
rust solution
- 어떤 양수 n을 만드는 음이 아닌 정수 쌍의 개수는?
- n+1가지이다: (0,n), (1,n-1), …, (n-1,1), (n,0)
- 해당 문제에서 덧셈이 정상적으로 적용되는 부분은?
- 해당 문제에서, 짝수/홀수 컬럼끼리는 덧셈이 정상적으로 적용된다
위 두 가지 사실로부터, 짝수/홀수 컬럼이 나타내는 수를 계산해서, 각각 그 수를 a,b라 하면, (a+1)(b+1)-2 가 답이 된다. (앞/뒤 수가 0인 경우 제외)
fn solve<R: io::BufRead, W: io::Write>(scan: &mut UnsafeScanner<R>, out: &mut W) {
let cases = ri32(scan);
for case in 0..cases {
let mut n = ri32(scan);
// make array of digits
let strn = n.to_string();
// digits 0, 2, 4, ...th
let mut digits1 = vec![];
// digits 1, 3, 5, ...th
let mut digits2 = vec![];
// enumerate digits
for (i, c) in strn.chars().enumerate() {
if i % 2 == 0 {
digits1.push(c);
} else {
digits2.push(c);
}
}
// dbg!(&digits1);
// dbg!(&digits2);
// digits1 -> number
let a = digits1.iter().fold(0, |acc, c| acc * 10 + c.to_digit(10).unwrap() as i32);
let b= digits2.iter().fold(0, |acc, c| acc * 10 + c.to_digit(10).unwrap() as i32);
// dbg!(&a);
writeln!(out, "{}", (a+1)*(b+1) - 2 ).ok();
}
}
kakao 2020 다시풀기
기둥과 보 설치
구조물이 겹치지 않게 나온대서 그냥 맵에 저장했는데, 생각해보니 기둥과 보는 그림에서 겹치지 않아도 맵에서 겹칠 수 있다. 그 부분을 고려하지 않아서 실패한 듯하다.
py fail solution
# 검사
def validate(r,c,a,maps):
valid = False
if a == 0:
# 1. 바닥 위
if r == 0:
valid = True
pass
else:
# 2. 보의 한쪽 끝 위
if c-1>=0 and maps[r][c-1] == 1:
valid = True
pass
elif maps[r][c] == 1:
valid = True
pass
# 3. 다른 기둥 위
if r-1 >= 0 and maps[r-1][c] == 0:
valid = True
pass
pass
pass
# 보 설치 시도
elif a == 1:
# 1. 한쪽 끝이 기둥 위
if r-1>=0 and maps[r-1][c] == 0:
valid = True
pass
if r-1>=0 and maps[r-1][c+1] == 0:
valid = True
pass
# 2. 양쪽 끝이 보
if c-1>=0 and maps[r][c-1] == 1 and maps[r][c+1] == 1:
valid = True
pass
pass
return valid
def solve(n, build_frame):
# pillar 기둥: 0
# bridge 보: 1
maps = create2DArray(150,150,-1)
nodes = []
for i,build in enumerate(build_frame):
x,y,a,b = build
r,c=y,x
valid = True
maps_before = maps.copy()
# 설치 모드
if b == 1:
nodes.append((r,c,a))
maps[r][c] = a
# check valid for all nodes
for rr,cc,aa in nodes:
valid = validate(rr,cc,aa,maps)
if not valid:
break
pass
if not valid:
maps = maps_before
nodes.remove((r,c,a))
pass
else:
# 삭제 모드
# remove (r,c,a) from nodes
if (r,c,a) in nodes:
nodes.remove((r,c,a))
maps[r][c] = -1
pass
else:
continue
# check valid for all nodes
for rr,cc,aa in nodes:
valid = validate(rr,cc,aa,maps)
if not valid:
break
pass
if not valid:
maps = maps_before
nodes.append((r,c,a))
pass
pass
# make list of structures from nodes
structures = []
for r,c,a in nodes:
structures.append([c,r,a])
pass
print(structures)
return sorted(structures)
가사 검색 다시풀기
또 헷갈려서 틀림
py solution
헷갈린 부분
- 트라이에 길이 정보 배열 추가, 관리 방법
- prefix 트라이는 쿼리 자체도 거꾸로 해야함.
def solve(words, queries):
from collections import defaultdict
trie = {}
rtrie = {} # postfix trie
all = defaultdict(int)
# words: ['frodo', 'front', 'frost', 'frozen', 'frame', 'kakao'] etc...
# queries: ['fro??', '????o', 'fr???', 'fro???', '????o', 'front', 'fro??', '????o'] etc...
# 1. build trie from words (with length information)
for word in words:
all[len(word)] += 1
cur = trie
for c in word:
if(c not in cur):
cur[c] = {}
cur = cur[c]
cur['!'] = [len(word)]
else:
cur = cur[c]
cur['!'].append(len(word))
cur['#'] = len(word)
for word in words:
cur = rtrie
for c in word[::-1]:
if(c not in cur):
cur[c] = {}
cur = cur[c]
cur['!'] = [len(word)]
else:
cur = cur[c]
cur['!'].append(len(word))
cur['#'] = len(word)
# print(trie)
# print(rtrie)
ans = []
# 2. lookup queries forward
for query in queries:
target_len = len(query)
is_prefix = query[0] == '?'
is_postfix = query[-1] == '?'
q = query.replace('?', '')
if(is_prefix and is_postfix):
# print('ALL')
ans.append(all[target_len])
elif(is_prefix):
# print('PRE')
cur = rtrie
# 2-1. find matching node from trie using prefix or postfix
for c in q[::-1]:
if(c not in cur):
ans.append(0)
break
cur = cur[c]
else:
# 2-2. get number of queries that length match
ans.append(cur['!'].count(target_len))
else:
# print('POST')
cur = trie
# 2-1. find matching node from trie using prefix or postfix
for c in q:
if(c not in cur):
ans.append(0)
break
cur = cur[c]
else:
ans.append(cur['!'].count(target_len))
# print('ans', ans)
return ans
Comments