PS87 AtCoder ABC 253 풀이 https://atcoder.jp/contests/abc253/tasks Tasks - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A. 항상 a> b >> c; if (a > c) swap(a, c); if (a w; vectorv; for (int i = 0; i > s; if (s == 'o') { v.pu.. 2022. 9. 12. AtCoder Educational DP Contest F~J https://atcoder.jp/contests/dp/tasks Tasks - Educational DP Contest AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp F. LCS를 복원하는 문제입니다. dp로 복원해봅시다. go(i, j)를 S를 i번을 볼 것이고, T를 j번을 볼 것일 때 지금까지 최대로 겹치는 길이로 정의합니다. 우선 안겹치는 경우 다음 전이는 go(i+1, j) 또는 go(i, j+1)입니다. 겹치는 경우 다음 전이는 1+go(i+1, j+1)이 됩니다. 이렇게 go(0,0)을 호출해서 모든 dp.. 2022. 9. 9. AtCoder Educational DP Contest A~E https://atcoder.jp/contests/dp/tasks Tasks - Educational DP Contest AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A. i에서 i+1 or i+2로 전이할 수 있습니다. 즉 i는 i-1과 i-2에서 옵니다. dp[i]=max(dp[i-1]+C1 , dp[i-2]+C2) 임을 쉽게 알 수 있습니다. 시간복잡도는 O(N)입니다. #include using namespace std; int n, h[100005], dp[100005]; int main() { ios::sy.. 2022. 9. 9. AtCoder ABC 257 D, E D. https://atcoder.jp/contests/abc257/tasks/abc257_d D - Jumping Takahashi 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 시작점을 잘 정해서 조건을 만족하도록 전부 순회할 수 있는지 그 때 최소의 S를 찾는 문제입니다. 시작점을 고정하고, S도 고정시킨 후 각 점에서 다른 모든 점으로 조건을 만족한다면 그래프 위에서 선분으로 연결해줍니다. 이 때, dfs를 쭉 해주고 나면 모든 점을 방문했는지 여부를 O(N)에 알 수 있습니다. 이제 시작점을 선택하는 경우 .. 2022. 9. 8. 이전 1 2 3 4 5 6 7 8 ··· 22 다음