https://atcoder.jp/contests/abc129/tasks/abc129_d
D - Lamp
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
문제 요약
n*m에 벽이 있고 빈곳이 있는데 빈곳에 램프를 두면 상하좌우로 빛이 벽에 닿을때까지 뻗어나간다. 하나의 램프를 둬서 최대 몇개의 칸에 빛이 닿을 수 있게 할 수 있는가?
풀이 시간
6분
풀이
각 위치에서 상하좌우로 최대로 몇만큼 뻗을 수 있는지를 O(1)에 알 수 있으면 O(NM)에 된다.
U[i][j] := (i,j)에서 최대한 위로 뻗을 때 칸 수
D[i][j] := (i,j)에서 최대한 아래로 뻗을 떄 칸 수
L[i][j] := (i,j)에서 최대한 왼쪽으로 뻗을 때 칸 수
R[i][j] := (i,j)에서 최대한 오른쪽으로 뻗을 떄 칸 수
각각 O(NM)에 채워줄 수 있고, 답은 max(U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, m;
ll u[2020][2020], d[2020][2020], l[2020][2020], r[2020][2020];
string arr[2020];
int main(){
fast;
cin>>n>>m;
for(int i = 0 ; i < n ; i++)cin>>arr[i];
//set UP
for(int j = 0 ; j < m ; j++){
ll cnt = 0;
for(int i = n-1 ; i >= 0 ; i--){
if(arr[i][j]=='#')cnt=0;
else u[i][j] = ++cnt;
}
}
//set DOWN
for(int j = 0 ; j < m ; j++){
ll cnt = 0;
for(int i = 0 ; i < n ; i++){
if(arr[i][j]=='#')cnt=0;
else d[i][j] = ++cnt;
}
}
//set RIGHT
for(int i = 0 ; i < n ; i++){
ll cnt = 0;
for(int j = m-1 ; j >= 0 ; j--){
if(arr[i][j]=='#')cnt=0;
else r[i][j] = ++cnt;
}
}
//set LEFT
for(int i = 0 ; i < n ; i++){
ll cnt = 0;
for(int j = 0 ; j < m ; j++){
if(arr[i][j]=='#')cnt=0;
else l[i][j] = ++cnt;
}
}
ll ans = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(arr[i][j]=='.')ans = max(ans, u[i][j]+d[i][j]+l[i][j]+r[i][j]-3);
}
}
cout<<ans;
}
https://atcoder.jp/contests/arc149/tasks/arc149_c
C - Avoid Prime Sum
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
문제 요약
N*N 행렬을 1~N^2까지의 수를 한번만 사용해서 채우는데, 상하좌우로 인접한 원소끼리 더했을 때 소수가 나오지 않게 채우시오.
풀이 시간
61분(25분 + 36분)
풀이
홀수는 홀수끼리 최대한 인접한게 좋고, 짝수는 짝수끼리 최대한 인접한게 좋다. 왜냐하면 둘이 더하면 짝수라서 소수가 나올 일이 없기 때문이다. (2는 소수지만 1~N^2을 한번씩 사용하므로 2가 나올 일이 없다)
N이 짝수이면 사용해야 하는 홀수의 개수와 짝수의 개수가 같으므로, N*N을 반으로 쪼개서 다음과 같이 배치할 수 있다.
그러면 홀수와 짝수가 인접한 부분이 딱 N군데 생기는데, 얘는 다음과 같이 처리한다.
(1)2*N+1 이상의 가장 작은 소수가 아닌 홀수를 찾는다. 얘를 x라 하자.
(2)인접한 모든 곳을 합이 x가 되게 채운다.
(3)나머지는 사용하지 않은 짝수, 홀수로 채운다.
예를 들어 N=4를 보자. 2*4+1(=9) 이상의 가장 작은 소수가 아닌 홀수는 9이다.
그러면 인접한 곳들을 합이 9가 되게 채운다. 그 중 하나는 다음과 같다.
| 2 | 7 |
| 4 | 5 |
| 6 | 3 |
| 8 | 1 |
이렇게 채우면 된다. (2+7 = 4+5 = 6+3 = 8+1 = 9)
따라서 맨 위를 (2, x-2)로 채우고 그 아래는 짝수는 2씩 증가, 홀수는 2씩 감소하게 쭉 채워주면 된다.
짝수는 끝. (남은 부분들은 아무 짝수, 아무 홀수나 채워주면 된다)
N이 홀수일 때를 보자. 다음과 같이 채워야 한다.
여기서 분기점을 보자.
이런식으로 개수가 바뀌는 분기점만 빼고 보면, 나머지 N-1개의 인접한 곳은 짝수에서 채웠던것처럼 채워줄 수 있다.
그럼 저 초록색 부분이 문젠데, 저기는 매우 간단하다. 먼저 홀수(연한 초록색)에, 안썼던 것중에 위랑 합해서 소수가 되지 않는 수를 아무거나 넣어준다.
그러면 남은 진한 초록색은 연한 초록색이랑 합해서 소수가 되지 않는 짝수를 아무거나 넣으면 된다.
이제 남은 부분은 짝수일때랑 마찬가지로 채워주면 된다.
단 이 풀이로는 N=3을 찾지 못하므로 N=3은 손으로 구해주면 된다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
ll ans[1010][1010];
bool prime[2020202]={1,1};
int main(){
for(ll i = 2 ; i <= 2000000 ; i++){
if(!prime[i]){
for(ll j = i*i ; j <= 2000000 ; j+=i)prime[j]=1;
}
}
fast;
cin>>n;
if(n==3){
cout<<"3 1 5\n"<<"7 8 4\n"<<"9 6 2";
return 0;
}
if(n%2==0){
ll a = 2*n+1;
while(!prime[a])a+=2;
set<ll> used;
ll cur_even = 2, cur_odd = a-2;
for(int i = 0 ; i < n ; i++){
ans[i][n/2-1] = cur_even;
ans[i][n/2] = cur_odd;
used.insert(cur_even); used.insert(cur_odd);
cur_even += 2, cur_odd -= 2;
}
cur_even = 2, cur_odd = 1;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(ans[i][j])continue;
if(j<n/2){
while(used.find(cur_even) != used.end())cur_even += 2;
ans[i][j] = cur_even;
cur_even += 2;
}
else{
while(used.find(cur_odd) != used.end())cur_odd += 2;
ans[i][j] = cur_odd;
cur_odd += 2;
}
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)cout<<ans[i][j]<<" \n"[j==n-1];
}
}
else{
ll a = 2*n+1;
while(!prime[a])a+=2;
set<ll> used;
ll cur_even = 2, cur_odd = a-2;
for(int i = 0 ; i < n ; i++){
if(i==n/2+1)continue;
if(i<n/2+1){
ans[i][n/2-1] = cur_even;
ans[i][n/2] = cur_odd;
used.insert(cur_even); used.insert(cur_odd);
cur_even += 2, cur_odd -= 2;
}
else{
ans[i][n/2] = cur_even;
ans[i][n/2+1] = cur_odd;
used.insert(cur_even); used.insert(cur_odd);
cur_even += 2, cur_odd -= 2;
}
}
for(int i = 1 ; i <= n*n ; i+=2){
if(used.find(i) != used.end())continue;
if(!prime[i+ans[n/2+2][n/2+1]] or !prime[i+ans[n/2][n/2+1]])continue;
used.insert(i);
ans[n/2+1][n/2+1] = i;
break;
}
for(int i = 2 ; i <= n*n ; i+=2){
if(used.find(i) != used.end())continue;
if(!prime[i+ans[n/2+2][n/2]] or !prime[i+ans[n/2][n/2]])continue;
if(!prime[i+ans[n/2+1][n/2+1]])continue;
used.insert(i);
ans[n/2+1][n/2] = i;
break;
}
cur_even = 2, cur_odd = 1;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(ans[i][j])continue;
if((i<=n/2 and j<n/2) or (i>n/2 and j<=n/2)){
while(used.find(cur_even) != used.end())cur_even += 2;
ans[i][j] = cur_even;
cur_even += 2;
}
else{
while(used.find(cur_odd) != used.end())cur_odd += 2;
ans[i][j] = cur_odd;
cur_odd += 2;
}
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)cout<<ans[i][j]<<" \n"[j==n-1];
}
}
}똑같은 코드가 2번 있어서 좀 길다. 또 사용한 수를 set으로 관리했는데, 1~1000^2까지라서 배열로 관리해도 된다.
그리고 이거 민트퍼포 문제던데 ARC라 그런지 좀 어려웠다.