Codeforces Round #837

Dashboard - Codeforces Round #837 (Div. 2) - Codeforces

A - Hossam and Combinatorics

ans = minv == maxv ? N * (N - 1) : (2 * cnt(minv) * cnt(maxv));

00:04 AC

 

B - Hossam and Friends

문제 이해를 잘못하였다.

00:08 WA

 

다음과 같은 배열 A를 정의한 후 two pointer로 관리하면 된다.

A[i] = max(i번 사람이 모르는 사람의 번호)

multiset으로 풀이할 수도 있다.

00:16 AC

 

C - Hossam and Trainees

소인수분해

00:22 AC

 

E - Hossam and a Letter

누적 합 + two pointer

01:30 AC

 

D - Hossam and (sub-)palindromic tree

문자열에서의 maximal sub-palindrome은 dp로 구할 수 있다.

이를 트리에서 구하기 위해서는 약간의 전처리가 필요하다.

 

다음과 같은 배열을 정의하자.

dist[i][j] = i번 정점과 j번 정점 사이의 거리

go[i][j] = i번 정점에서 j번 정점으로 가는 단순 경로에서 i번 정점의 다음 정점 번호

이는 N번의 dfs로 구할 수 있다.

 

이제 기존 문제와 동일하게 dp로 풀이할 수 있다.

업데이트는 거리순으로 처리해주면 된다.

01:52 AC

 

F - Hossam and Range Minimum Query (not solved)

Pass

 

끝

끝