Computer_Study

https://atcoder.jp/contests/typical90/tasks/typical90_aj 036 - Max Manhattan Distance（★5）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 x,y로 점의 좌표가 주어지고 Q개의 쿼리가 주어진다. 쿼리에 해당하는 좌표와 가장 맨해튼거리가 먼 점의 거리를 구하라. 문제를 읽고 몇 분동안 생각해보다가 내가 아는 알고리즘에서는 풀 수 있는 방법이 없는것 같아 해설을 봤는데, 해설코드로도 이해가 안되서 gpt와 함께 분석까지 했다. 우선 내가 접근한 방식은 ..

https://atcoder.jp/contests/typical90/tasks/typical90_ah 034 - There are few types of elements（★4）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 원소가 주어질때 포함된 요소가 K개 이하인 연속된 부분수열의 길이를 구하라.7 21 1 2 2 3 3 4 로 주어지면 2개이하인 연속된 부분수열로 1,1,2,2 / 2,2,3,3 으로 최대길이는 4다. N의 최대가 10만개이므로 모든 경우의수를 계산하는 N^2의 방법으로는 불가능하다. 이를 O(N..

https://atcoder.jp/contests/typical90/tasks/typical90_ag H, W가 주어졌을 때, LED 켜진 개수를 최대화 하는 문제이다. 조건으로는 2*2 구간에 켜져있는 LED가 1개만 있게 키는것이다. 조금 생각해봤을 때, 그리디한 접근으로 2*2에 불이 켜져있게 하려면 왼쪽 위부터 차근차근 불을 키면된다. 수식으로 정리하면 (H+1)/2 * (W+1)/2 이다.  이렇게 제출하니 틀렸다고 나오자 corner케이스가 있나 하고 검토를 해봤지만 찾을 수 없어서 몇개의 테캐나 통과를 못했는지 보러갔는데, corner1~10.txt 정도의 케이스를 통과를 못했다. 그래서, 설마 1칸짜리면 LED가 빼곡히 들어가도 되나? 싶었다. 조건이 2*2구간 안에 켜져야 하기 때문에 1..

https://atcoder.jp/contests/typical90/tasks/typical90_ad 030 - K Factors（★5）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 2이상의 N이하의 정수 중에서 소인수가 K개이상인 정수의 개수를 구하라. 난이도가 왜 별 5개 짜리문제인지는 모르겠다. 난이도만 보고 수학적인 뭔가를 써야 되나 싶었다. 우선 각 N마다 소인수분해를 해서 저장하는 방식이 문제의 의도는 아닐것이다. 예전에 이런 비슷한 문제를 백준에서 본적이 있어서 쉽게 접근할 수 있었던 것 같다. 에라토스테네스..

https://atcoder.jp/contests/typical90/tasks/typical90_ab 028 - Cluttered Paper（★4）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 색종이가 주어진다. 색종이의 왼쪽 위 그리고 오른쪽 아래의 좌표가 a, b, c, d로 주어진다. 색종이를 N개 두었을 때, k=1~N까지 종이가 정확히 k 겹쳐진 부분의 면적을 출력하라. 문제를 보면 2차원 누적합 관련 문제임을 유추할 수 있다. https://www.acmicpc.net/problem/11660비슷한 문제..

https://atcoder.jp/contests/typical90/tasks/typical90_aa 027 - Sign Up Requests （★2）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp Lowcoder라는 사이트를 다카하시군이 만들었다. N개의 문자열이 주어질때, i일에 문자열 S의 입력이 등록된다. 이미 등록됐을 경우에는 무시하고 새로 등록할시 등록한 날짜를 출력한다. set자료구조를 이용하면 쉽게풀린다. #define _CRT_SECURE_NO_WARNINGS#include #include #include ..

https://atcoder.jp/contests/typical90/tasks/typical90_z 026 - Independent Set on a Tree（★4）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 7레벨은 이제 건너뛰도록 하자 하나의 트리 그래프가 주어질때 인접하지 않은 정점의 집합을 N/2개 출력하시오.예제이다. 정점 하나를 잡고 시작해서 깊이를 기준으로 깊이가 짝수일때만 vector에 넣어서 정렬 후 출력했더니 테스트케이스 일부가 틀렸었다. 다시 생각해보니 내가 시작 정점을 1로 한거였는데 1이 끝이 아니..

https://atcoder.jp/contests/typical90/tasks/typical90_x 024 - Select +／- One（★2）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 길이가 N인 두개의 배열 A, B가 있다. 배열 A에서 특정 index의 원소를 선택하여 +1, 또는 -1 하여 배열 B를 K번 이내에 만들 수 있는가?를 판별하는 문제이다. +1 또는 -1 한다는 것은 어떻게든 값을 만들 수 있는 것이고 K번 이내에 가능한지 만 판별하면 되는 것이다. 0번째 원소가 3, 5라고 할때 3을 5로 만들기..

https://atcoder.jp/contests/typical90/tasks/typical90_v 022 - Cubic Cake（★2）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp A* B* C 크기의 빵이있다. 이를 최소한으로 잘라서 모두 같은 크기로 만들어라. 자른 횟수를 구하라.많이 볼법한 문제이다. A, B, C의 공통된 크기로 만들려면 gcd를 이용한다. 그리고 나눈횟수를 단순히 세주면 된다. #define _CRT_SECURE_NO_WARNINGS#include #include #include #include..

https://atcoder.jp/contests/typical90/tasks/typical90_u 021 - Come Back in One Piece（★5）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 정점과 M개의 간선을 가진 유향그래프가 있을 때 간선 i는 정점 Ai에서 정점 Bi로 향한다. 다음 조건을 만족하는 2개의 정점 (x,y)의 쌍 이 몇개 인지 구하라- 정점 x에서 정점 y로 가는 경로와 정점 y에서 정점 x로 가는 경로가 모두 존재한다. 문제를 읽어 보고 나서 아이디어가 바로 떠올랐다. 정점 a에..