Codeforces Round #790 (Div. 4) A~E

A. Lucky?

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    const t = input().split('').map(Number);
    if(t[0]+t[1]+t[2] === t[3]+t[4]+t[5]) console.log("YES");
    else console.log("NO");
  }
}

6자리 숫자에서 반을 나누어 각각 더한 합이 같으면 YES, 틀리면 NO 출력하면 된다.

B. Equal Candies

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    let n = parseInt(input());
    const a = input().split(' ').map(Number);
    let min_a = 1e7;
    for(let i of a) min_a = Math.min(min_a, i);
    let ans = 0;
    for(let i of a) if(i > min_a) ans += i-min_a;
    console.log(ans);
  }
}

1. 최소 개수의 사탕 수를 구한다.
2. 나머지 사탕들의 개수를 최소 개수가 되도록 먹어치운다.

C. Most Similar Words

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    const [n, m] = input().split(' ').map(Number);
    const s = [];
    for(let i = 0; i < n; i++){
      s.push(input());
    }
    let ans = Number.POSITIVE_INFINITY;
    for(let i = 0; i < n; i++){
      for(let j = i+1; j < n; j++){
        ans = Math.min(ans, solve(s[i], s[j], m));
      }
    }
    console.log(ans);
  }
}

const solve = (s1, s2, m) => {
  let ret = 0;
  for(let i = 0; i < m; i++){
    let tmp = Number.POSITIVE_INFINITY;
    const [c1, c2] = [s1[i], s2[i]];
    tmp = Math.min(tmp, Math.abs(c1.charCodeAt(0)-c2.charCodeAt(0)), Math.abs(c2.charCodeAt(0)-c1.charCodeAt(0)));
    ret += tmp;
  }
  return ret;
}

주어진 n 개의 길이가 m 인 문자열들 중 두개를 골라 서로가 같게끔 만들 때 드는 moves 중 최소값을 구하는 문제.

문자열 a, b 가 있을 때 문자열의 각 원소를 a 에서 b, b 에서 a 로 바꾸는 것 중 더 적은 moves 를 선택하여 누적해주면 된다.

D. X-Sum

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const dy = [-1, 1, -1, 1];
const dx = [-1, 1, 1, -1];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    const [n, m] = input().split(' ').map(Number);
    const a = Array.from(Array(n), () => Array(m));
    for(let i = 0; i < n; i++){
      const tmp = input().split(' ').map(Number);
      for(let j = 0; j < m; j++){
        a[i][j] = tmp[j];
      }
    }
    let ans = 0;
    for(let y = 0; y < n; y++){
      for(let x = 0; x < m; x++){
        ans = Math.max(ans, solve(n, m, a, y, x));
      }
    }
    console.log(ans);
  }
}

const solve = (n, m, a, sy, sx) => {
  let ret = a[sy][sx];
  for(let i = 0; i < 4; i++){
    let y = sy;
    let x = sx;
    while(true){
      y += dy[i];
      x += dx[i];
      if(y < 0 || y >= n || x < 0 || x >= m) break;
      ret += a[y][x];
    }
  }
  return ret;
}

체스 보드의 모든 위치에서 비숍을 이동시켜보고 최대값을 갱신하면 되는 완전탐색 문제.

E. Eating Queries

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    const [n, q] = input().split(' ').map(Number);
    const a = input().split(' ').map(Number);
    a.sort((a, b) => {
      if(a > b) return -1;
      else return 1;
    });
    for(let i = 1; i < n; i++){
      a[i] += a[i-1];
    }
    for(let i = 0; i < q; i++){
      let x = parseInt(input());
      let j = lower_bound(a, x);
      if(j === n) console.log(-1);
      else console.log(j+1);
    }
  }
}

const lower_bound = (a, key) => {
  let m = 0;
  let l = 0;
  let r = a.length-1;
  while(l <= r){
    m = Math.floor((l+r)/2);
    if(key <= a[m]) r = m-1;
    else l = m+1;
  }
  if(key > a[m]) return m+1;
  else return m;
}

1. 정렬
2. 누적합
3. 이진탐색

O(NlogN) 로 통과할 수 있다.

---

F. Longest Strike (Upsolving)

JavaScript

'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let [inputString, currentLine] = ['', 0];
process.stdin.on('data', inputStdin => inputString += inputStdin);
process.stdin.on('end', _ => {
  inputString = inputString.trim().split('\n').map(string => string.trim());
  main();
});
const input = () => inputString[currentLine++];

const main = () => {
  let tc = parseInt(input());
  while(tc--){
    const [n, k] = input().split(' ').map(Number);
    const a = input().split(' ').map(Number);
    // 1
    a.sort((a, b) => {
      if(a < b) return -1;
      else return 1;
    });
    // 2
    let last = a[0];
    let cnt = 1;
    const aa = [];
    for(let i = 1; i < n; i++){
      if(last !== a[i]){
        if(cnt >= k) aa.push(last);
        cnt = 1;
        last = a[i];
      }
      else{
        cnt++;
      }
    }
    if(cnt >= k) aa.push(last);
    if(!aa.length){
      console.log(-1);
      continue;
    }
    // 3
    const aaa = [];
    last = aa[0];
    let tmp = [aa[0]];
    for(let i = 1; i < aa.length; i++){
      if(aa[i]-1 === last){
        tmp.push(aa[i]);
      }
      else{
        aaa.push(JSON.parse(JSON.stringify(tmp)));
        tmp = [aa[i]];
      }
      last = aa[i];
    }
    if(tmp.length) aaa.push(tmp);
    // 4
    const aaaa = [];
    for(let i = 0; i < aaa.length; i++){
      let s = aaa[i].length;
      let l = aaa[i][0];
      let r = aaa[i][s-1];
      aaaa.push([r-l, l, r]);
    }
    aaaa.sort((a, b) => {
      if(a[0] > b[0]) return -1;
      else return 1;
    });
    console.log(aaaa[0][1], aaaa[0][2]);
  }
}

l <= x <= r 에서 x 가 a 배열 안에 존재하는 원소인 줄 알았는데 단지 l 과 r 사이의 모든 정수 값이었고, x 가 a 에 존재하며 k 번 이상 등장해야 한다는 뜻이였다.

문제 이해를 잘못 해서 시간안에 풀지 못한 문제.

1. 배열 a 정렬
2. k 이상 존재하는 원소들만 새로운 배열 aa 에 추가
3. 공차가 1인 등차수열들을 찾아내 배열 aaa 에 저장
4. 배열 aaa 의 각 원소들의 맨 앞 l 과 맨 뒤 r 값을 찾아 r-l 값과 함께 배열 aaaa 에 저장하고, 내림차순 정렬하여 맨 앞의 값을 답으로 출력한다.

array 의 sort 메소드를 비교함수 없이 사용하면 기본적으로 오름차순 정렬이 되는 줄 알았는데, 전혀 정렬이 되지 않아서 wrong answer 를 받았었다.

후기

Div.4 라 문제가 쉬워 빠르게 풀어나갈 때 마치 알고리즘 고수가 된 기분이었다.

대회가 있는 걸 잊고 25분 늦게 들어왔는데 시작 시간을 맞춰 풀었으면 F 번까지 풀 수 있었을 것 같다