JOI2015予選参加記

12:40に起床して朝食をとる。3分前にログインしてギリギリセーフ

問題1

やるだけ。

A = [int(input()) for i in range(5)]
print(min(A[0] * A[4], A[1] + max(0, A[3] * (A[4] - A[2]))))

問題2

やるだけ。

def int_d(x):
    return int(x) - 1

N, M = int(input()), int(input())
A = list(map(int_d, input().split()))
p = [0] * N

for i in range(M):
    B = list(map(int_d, input().split()))
    f = 0
    for j, b in enumerate(B):
        if A[i]== b:
            p[j] += 1
        else:
            f += 1
    p[A[i]] += f
print('\n'.join(map(str, p)))

問題3

やるだけ。

各行の末尾に空白を入れてはいけない。

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
t = [[-1 for i in range(W)] for j in range(H)]

for i in range(200):
    for y in range(H):
        for x in reversed(range(W)):
            if m[y][x] == 'c' and t[y][x] == -1:
                t[y][x] = i
            if x > 0:
                m[y][x] = m[y][x - 1]
            else:
                m[y][x] = '.'
for y in range(H):
    print(' '.join(map(str, t[y])))

問題4

メモ化やるだけ

import sys
sys.setrecursionlimit(1000000)

def dfs(n, m):
    if n == N:
        return 0
    if m == M:
        return INF
    if dp[n][m] != -1:
        return dp[n][m]
    dp[n][m] =min(dfs(n, m + 1), dfs(n + 1, m + 1) + D[n] * C[m])
    return dp[n][m]

INF = 1000000000
N, M = map(int, input().split())
D = [int(input()) for i in range(N)]
C = [int(input()) for i in range(M)]
dp = [[-1 for i in range(M)] for j in range(N)]
print(dfs(0, 0))

問題5

最初は全部調べて、以降は壊れたマスの近傍のみ調べる。

何故か思いつかなくて競技中には解けなかった。

#include<iostream>
#include<queue>
#define INF 1000000000
using namespace std;

int H, W;
int m[1000][1000];
int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
queue<int> q;


bool broken(int x, int y, int t)
{
  int n = 0;
  for(int i = 0; i < 8; i++)
    if(m[y + dy[i]][x + dx[i]] <= 0 && m[y + dy[i]][x + dx[i]] > -t)
      n++;
  return m[y][x] <= n;
}

int main()
{
  cin >> H >> W;
  for(int y = 0; y < H; y++)
  {
    for(int x = 0; x < W; x++)
    {
      char c;
      cin >> c;
      if(c == '.')
        m[y][x] = 0;
      else
        m[y][x] = c - '0';
      q.push(x);
      q.push(y);
    }
  }


  int t = 1;
  for(; !q.empty(); t++)
  {
    q.push(INF);
    q.push(INF);
    while(true)
    {
      int x = q.front(); q.pop();
      int y = q.front(); q.pop();
      if(x == INF)
        break;
      if(m[y][x] <= 0)
        continue;
      if(broken(x, y, t))
      {
        m[y][x] = -t;
        for(int i = 0; i < 8; i++)
        {
          q.push(x + dx[i]);
          q.push(y + dy[i]);
        }
      }
    }
  }
  cout << t - 2 << endl;
}

問題6

わからない。

まとめ

全体的に簡単だった(が私の成績は悪かった)。