제3회 초콜릿컵/Arena #23 문제 오류에 대한 사과문 및 출제 검수 과정 복기

안녕하세요. 제3회 초콜릿컵 주최자 bubbler입니다.

그나마 visibility가 오래 유지될 만한 곳이 BOJ 블로그라고 판단하여 여기에 올립니다.

대회 문제 중 E와 K(입력 범위만 다르고 같은 두 문제)에서 지문이 문제의 의도와 다르다는 것이 대회 종료 후에 발견되어 아레나가 unrated 처리가 된 점에 대해 송구스럽게 생각하며, 아레나에 참가해주신 모든 분들에게 깊은 사과의 말씀을 드립니다.

더 읽기댓글 쓰기

solved.ac Grand Arena Party 후기

@shiftpsh 님의 초대로 solved.ac Grand Arena Party를 방문했었습니다.

장소 올댓마인드에 도착했는데, 문이 어딨는지 몰라서 못들어갈 뻔 했습니다.

더 읽기댓글 쓰기

IOI 2016 Aliens 풀이 (BOJ 20090)

안녕하세요. 이 글에서는 IOI 2016에 출제된 Aliens 문제 풀이를 설명해보려고 합니다. 하나의 글 안에서 풀이 전체를 설명하는 것이 목표입니다.

풀이에 앞서 먼저 이 문제를 요약해보겠습니다. 왼쪽 그림과 같이 한 변의 길이가 m인 정사각형 격자가 주어지고, 그 안에 있는 n개의 점이 주어집니다. 정사각형으로 n개의 점을 모두 덮는 게 목표입니다. 이때, 정사각형은 가운데 그림에서 보는 것과 같이 왼쪽 위와 오른쪽 아래가 모두 대각선 위에 있어야 합니다. 정사각형은 서로 겹칠 수 있으며, 겹치는 영역은 한 번만 덮은 것으로 간주합니다. 같은 칸에 2개 이상의 점이 있다고 해도 한 번만 덮으면 충분합니다. 정사각형은 최대 k개만 사용할 수 있습니다. 우리는 덮은 칸의 개수를 최소화하고 그 개수를 출력해야 합니다. Aliens_SampleImage

풀이는 두 가지 부분으로 나눠서 설명하겠습니다.

  • 첫 번째 부분에서는 사용할 수 있는 정사각형의 개수 상한 k가 없을 때에 한해 문제를 해결합니다.
  • 두 번째 부분에서는 첫 번째 부분의 결과를 이용해 어떻게 k를 반영한 답을 구할 수 있는지 설명합니다.

더 읽기댓글 쓰기

[C++] tie 와 sync_with_stdio

머릿말

C++ 프로그램을 작성할 때 main 함수에 다음과 같은 문장을 쓰면 속도가 빨라진다고 알고 있는 사람이 많을 겁니다.

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    /* 실제 프로그램 */
}

하지만 왜 빨라지는지 정확하게 알고 있는 사람은 생각보다 많지 않은 것 같습니다. 이 글에서는 이 두 문장이 하는 일에 대해 알아보려고 합니다.

더 읽기댓글 쓰기

Zeta, Mobius Transform to AND, OR, GCD Convolution

Introduction

안녕하세요 jinhan814입니다. 최근 Mobius Inversion 문제를 풀다 새로운 내용을 알게 돼서 글을 써봤습니다. (원본 글, 영문)

포함-배제의 원리(Inclusion-Exclusion Principle)나 뫼비우스 반전 공식(Mobius Inverison)을 공부해 본 적이 있는 분들은 $μ(n)$의 정의와 $(-1)^{|s|}$를 곱하며 필요 없는 값들을 상쇄시키는 과정에 궁금증을 가져본 적이 있을 겁니다. 식 전개를 통해 두 공식이 성립한다는 걸 보일 수는 있지만, 이런 방식의 증명은 직관적인 명확성이 떨어집니다.

더 읽기댓글 쓰기

월간 향유회 2023. 5. 풀이

https://www.acmicpc.net/category/detail/3593

== 미리보기 스포일러 방지 ==

== 미리보기 스포일러 방지 ==

더 읽기댓글 쓰기

10169번 풀이

2014년 고2 때 KOI에 나갔던 적이 있습니다. 아마 본선까지는 갔었나 그렇습니다.

그런 사정으로 10169번을 풀었는데, 제 풀이랑 똑같은 풀이를 못 찾아서 공유합니다.


더 읽기댓글 쓰기

코드를 빠르게 짜는 방법에 관한 고찰 (+ 구데기컵 카페 후기)

코드를 빠르게 짜기 위해서는 어떻게 해야 할까요. 정말 많은 PS러들이 하고 있는 고민일 것이라고 생각합니다. 마침 구데기컵 카페에서 시프트님보다 브론즈5 빠르게 풀기 대결이 있었고, 제가 승리 (!!) 했기에, 이렇게 카페 후기를 빌미로 글을 써보려 합니다.

코드를 빠르게 짜는 것은, 물론, PS에서는 꽤나 보조적인 고민이 될 것입니다. 그러나, 결국 언젠가는 코드를 빠르게 짜는 것이 큰 도움이 됩니다. 예를 들어, 저는 ABC 기준으로 A~D번 기준으로 코드를 짜는 시간보다 생각을 하는 시간이 더 많이 걸린 적이 많지 않습니다. 이러한 경우에는, 코드를 빠르게 짜는 것도 매우 중요합니다. 등수의 기준에 점수뿐만이 아니라 페널티도 있기 때문입니다. Codeforces는 심지어 문제를 푸는데 시간이 더 걸릴수록 점수가 감점되는 시스템이다 보니 이러한 중요성이 더 부각된다고 생각합니다. 때때로 Speedforces라는 이야기도 돌고 있고요.

이러한 상황에서 우리는 어떻게 코드를 짜야, 코드를 "빠르게" 짤 수 있을까요? 이에 저는 여러 가지 가설들을 세우고 그 가설들이 실제로 코드를 짜는 속도에 얼마나 기여하는지 생각해 보는 방식으로 이야기를 하려 합니다.

더 읽기댓글 쓰기

AtCoder Educational DP T. Permutation 풀이 피드백

카카오 데이터 센터 화재로 티스토리 블로그가 접속이 안돼 백준 블로그를 이용합니다.

앳코더에서는 PS에서 자주 등장하는 동적 계획법 유형들을 26가지로 정리한 Educational DP Contest를 제공하고 있습니다.

이 블로그에서는 T번 문제인 Permutation의 풀이를 더 쉽게 이해할 수 있는 피드백을 제공합니다.

더 읽기댓글 쓰기

Online FFT의 $\mathcal{O}(n \sqrt {n})$ 구현

수열 $\{a_n\}$, $\{b_n\}$의 컨볼루션 $c_n = \sum_{i=0}^{n} a_i b_{n-i}$를 구하는 것은 FFT를 이용하여 $\mathcal{O}(n \log {n})$에 계산할 수 있습니다.

그런데 $\{a_n\}$, $\{b_n\}$의 각 원소가 online으로 주어진다면, 즉 예를 들어 $c_{n-1}$의 값을 알아야만 $a_n$$b_n$을 알 수 있다면 FFT를 이용하는 방법을 그대로 사용할 수 없습니다. 이러한 경우 $\{c_n\}$을 계산하는 문제를 Online FFT라고 부릅니다. Online FFT를 사용할 수 있는 대표적인 사례로 어떤 함수 $f$가 존재해 $a_n = f \left (n, \sum_{i=0}^{n-1} a_i b_{n-1-i} \right )$ 꼴의 점화식을 가지는 수열을 계산할 수 있습니다.

EDIT (2022-10-15): Online FFT의 정식 명칭은 relaxed multiplication인 것 같습니다.

더 읽기댓글 쓰기