SCPC 준비하려고 PS에 시간을 좀 넣었다. 그래서 CTF를 제대로 못함 :( 풀이는 시간이 없으니 최대한 간략하게.

SCPC 풀이 자체는 푼 것만 최종 결과가 나오면 올릴 것 같다. 시간이 난다면 ㅋㅋㅋㅋ


BOJ 18969 Different Summands Counting

BOJ 12961 체스판 2

2020 KAIST Mock ICPC

2018 NEERC Northern Subregional

BOJ 18908 Brackets

BOJ 16833 Enlarge Circles

2019 ICPC Danang Regional


'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21

이제 개강 + SNUPC 검수 + CTF 정식입문 + 등등으로 PS 일지가 일시정지 될 것 같다.

대신 CTF write-up을 최대한 열심히 써보려고 한다. 팀에 들어갔으니 진짜 열심히 해보려고 한다 :)


BOJ 1910 Two Parties

Petrozavodsk 2018 Winter Day 8 : Saratov SU Contest

BOJ 11617 Export Estimate

BOJ 19281 Short Random Problem

BOJ 19579 물건 가져가기

BOJ 14460 Why Did the Cow Cross the Road III (Platinum)

BOJ 15756 Disruption

BOJ 17031 Moorio Kart

BOJ 18356 Movie-goer

BOJ 18358 Gluttons

BOJ 18360 Logistics

BOJ 19651 수열과 쿼리 39


'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21

BOJ 17678 합병

BOJ 18448 Best Subsequence

BOJ 8875 장난감 정리 로봇

BOJ 10846 발리의 조각상

BOJ 10848 팔렘방의 다리

BOJ 18664 Minimums on the Edges

BOJ 15986 마법 목걸이

BOJ 10717 성벽

BOJ 18196 정기 모임


'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21

USACO 문제를 집중적으로 풀었다. JOI도 약간 풀었고, 다른 문제도 조금 풀었다.

문제의 개수가 워낙 많으니까 풀이는 웬만하면 간단하게 쓰려고 한다.


BOJ 16982 Growing Vegetables is Fun 3

BOJ 16983 Coin Collecting

BOJ 18433 Collecting Stamps 3

BOJ 8222 Distance

BOJ 11961 High Card Low Card Platinum

BOJ 11991 Fenced In Platinum

BOJ 11982 Angry Cows Gold

BOJ 16760 Balance Beam

BOJ 11992 Circular Barn Platinum

BOJ 17018 Redistricting

BOJ 14522 Modern Art Platinum

BOJ 18778 Equilateral Triangles

BOJ 14164 삼각형 영역

BOJ 14448 Subsequence Reversal

BOJ 18264 Moortal Combat

BOJ 18263 Milk Visits

BOJ 15743 New Barns

BOJ 18260 Bessie's Snow Cow

BOJ 18777 Delegation Platinum

BOJ 15585 Sprinklers

BOJ 18871 Sprinklers 2 : Return of the Alfalfa


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06

7월 말 ~ 8월 초에서는 먼저 UCPC 예선, 본선이 있었다. 문제를 몇 개 안 풀어서 나중에 업솔빙을 할 생각이다.

SNUPS에서 SCPC 대비 스터디가 있어서, SCPC 예선 문제를 가능한만큼 밀었다. 본선은 추후에 진짜 대회처럼 돌아볼 생각이다.

그리고 친구들과 만나서 셋을 돌거나 개인적으로 셋을 돌고, 덤으로 그냥 지나가는 문제들을 몇 개 풀었다. 


BOJ 1624 데크소트

BOJ 19548 그건 망고가 아니라 고양이에요

Pacific Northwest Regional 2019 (Division 1)

Codeforces Educational Round 92

SCPC 1차 예선

SCPC 2차 예선


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18

NERC 2019


Yokohama 2018


NWERC 2015


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18
4월의 PS 일지 - Part 2  (2) 2020.04.09

시험 때문에 PS를 못하고 있고, 그래도 Project Euler Eulerian 랭킹은 도전하고 있다. Top 10은 충분히 가능할 듯.

6월에 글을 쓰지만 푸는 것 자체는 전부 5월에 했으므로 5월의 일지로 치려고 한다.

방학이 되면 새로 올라온 Petrozavodsk 캠프 수학 문제를 몇 개 밀고, 근본 PS도 챙기려고 한다.

다행인지 아닌지는 모르겠지만 새로 올라온 문제 중에 재미있는 수학 문제는 몇 개 없는 것 같다.


BOJ 18928 Joy With Cookies

BOJ 18929 Knights of Round Table

BOJ 17644 Magic Tree

BOJ 17005 Knight of the Tarot Cards

BOJ 16892 레몬 주스 게임

BOJ 14704 타일 뒤집기 (Hard)

BOJ 18617 From Modular to Rational

BOJ 18763 Knowledge Oriented Problem (Ruby I)


'PS > Problem Solving' 카테고리의 다른 글

7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18
4월의 PS 일지 - Part 2  (2) 2020.04.09
4월의 PS 일지 - Part 1  (0) 2020.04.06
  1. 시래기국 2020.08.05 00:51

    18763번에 도전해보고 있는데 패스 그래프와 주어진 그래프의 특성 다항식의 Resultant를 구하는 과정에서 K가 너무 커서 유클리디안도 유한 시간내에 못구할것 같아서 패스 그래프 계수의 일반항이 컴비네이션인것을 이용해 규칙을 찾아보려 했는데 제 눈엔 보이지 않아서 이 과정에서 크게 막혀서 제가 아직 관찰하지 못한 규칙이 있나 싶어서 참고하신 논문같은게 있으신지 만약 없으시다면 방향에 대한 힌트좀 부탁드립니다

    • rkm0959 2020.08.05 00:57 신고

      path 그래프의 laplacian matrix의 특성 다항식을 구하는 문제가 되는데요, 이는 행렬의 특수한 형태를 이용하면 점화식을 얻을 수 있습니다. 즉, f_n(x)를 크기 n의 path 그래프라고 하면 f_n(x)를 f_{n-1}, f_{n-2} 등으로 표현할 수 있습니다. 이제 행렬 연산으로 효율적 계산이 가능합니다.

    • 시래기국 2020.08.05 01:05

      답변 감사합니다
      추가로, 말씀하신것처럼 구현한다면 주어지는 그래프 특성다항식에 O(N^3)가 소요되니까 패스 그래프의 연산은 O(N log N)꼴로 구현해야 하는건가요?

    • rkm0959 2020.08.05 01:07 신고

      resultant의 특성상 f_n을 mod(주어지는 그래프 특성다항식)에 대해서만 구해도 충분하고, 행렬곱을 활용하면 다항식 곱셈/나머지 연산은 로그번 계산됩니다. 그러니 여기서 곱셈/나머지 연산은 naive하게 해도 됩니다.

    • 시래기국 2020.08.05 01:09

      친절한 답변 감사드립니다

  2. 시래기국 2020.08.25 23:29

    계속된 질문 죄송합니다. 위에서 답변해주신것처럼 Path graph laplacian matrix의 특성다항식을 점화식을 이용해 matrix exponentiation으로 구하는 솔루션을 이해하고 실제로 구현해보았으나 Pn의 항의 숫자와 계수가 너무 커져서 matrix multiple마다 행렬 원소에 담기는 다항식을 Q로 모듈러하면서 계수도 마찬가지로 10^9+7로 모듈러 해주니 예제 2번까지는 잘 구해집니다. 그러나 K가 10^18로 주어지는 예제 3번은 자꾸 잘못된 값을 계산하고 Q를 500차 특성다항식으로 두니 연산시간이 너무 길어져서 잘못된 방법을 사용한 것 같아 자료를 찾아보니 Pn mod Q를 O(log n|Q|^2)에 구할 수 있다고 하는데 이처럼 로그 시간에 Pn mod Q를 구하는 방법이 무엇인지 궁금합니다.

    계산에 사용된 점화식은 Pn = (x-2)Pn-1 - Pn-2입니다.

    • rkm0959 2020.08.26 01:04 신고

      주어진 점화식을 행렬처럼 다루면 됩니다.

    • 시래기국 2020.08.26 14:36

      혹시 테스트 케이스 하나 답 맞는지만 봐주실 수 있나요?
      5 10 10000000000000000
      1 2
      1 3
      1 4
      1 5
      2 3
      2 4
      2 5
      3 4
      3 5
      4 5

      -------

      453755612

    • rkm0959 2020.08.26 14:38 신고

      맞습니다

BOJ 18542 Permutant

BOJ 8483 Earthquake

BOJ 17318 Highway Cycling

BOJ 12928 트리와 경로의 길이

BOJ 15879 Edge Coloring

BOJ 13203 읽어내기

BOJ 16250 Cactusophobia

BOJ 17105 골드바흐 트리플

BOJ 10638 Point Distance

BOJ 13428 배열의 합

BOJ 17642 Dynamic Diameter


'PS > Problem Solving' 카테고리의 다른 글

7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18
4월의 PS 일지 - Part 2  (2) 2020.04.09
4월의 PS 일지 - Part 1  (0) 2020.04.06
3월의 PS 일지 - Part 7  (0) 2020.03.26