PythonでJOI難易度6を埋める #15

D - 日本沈没 (Japan Sinks)

解説と同じ考え方をしたが，になった．海面を上げていくときに，それぞれの要素の両隣調べる方法が分からなかった． それぞれの高さのindexをdictに記録して，海面を上げたときの島の増減を計算する．参考にした提出．このコードの計算量はいくつ?

from sys import stdin
input = stdin.readline
from collections import defaultdict

n = int(input().strip())
a = list(map(int, input().strip().split()))

a_sorted = sorted(list(set(a)))
dic = defaultdict(list)

for i, j in enumerate(a):
    dic[j].append(i)

cnt = 0
flag = False #T→新しい陸地に入る
for i in a:
    if i > 0:
        if not flag:
            cnt += 1
            flag = True
    else:
        flag = False

if n == 1:
    if a[0] > 0:
        print(1)
    else:
        print(0)
else:
    ans = cnt
    for i in a_sorted:
        tmp = 0 #この変化での島の増減
        if i != 0:
            for j in dic[i]:
                if j == 0: #一番前のとき
                    tmp -= 1
                    if a[j + 1] > i: #±0
                        tmp += 1
                    elif a[j + 1] < i: #-1
                        tmp -= 1
                elif j == n - 1: #一番後ろのとき
                    tmp -= 1
                    if a[j - 1] > i: #±0
                        tmp += 1
                    elif a[j - 1] < i: #-1
                        tmp -= 1
                else:
                    if a[j - 1] > i:
                        tmp += 1
                    elif a[j - 1] < i:
                        tmp -= 1
                    if a[j + 1] > i:
                        tmp += 1
                    elif a[j + 1] < i:
                        tmp -= 1
        cnt += tmp // 2
        ans = max(cnt, ans)
    print(ans)

できたこと

• Aをsortして小さい順に取りだす
• 考える海面の高さは整数だけ
• 海面の高さが変化したときの島の個数の変動

学んだこと

• dictの中にlistを作れる

PythonでJOI難易度6を埋める #14

A - 長いだけのネクタイ (Just Long Neckties)

最初はDPと思っていたけど，sortして，順番に計算していけばよい．A，B のどちらも昇順でsortして前から順番に差を求めたときに"奇妙さが"が最小になる．最小値になるネクタイ以外を除いた場合は，もちろん最小値以上になるので，前に値と比較して更新していく．図を持ちいた分かりやすい解説．参考にした記事

from sys import stdin
input = stdin.readline

n = int(input().strip())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))


sort_a = []
for i in range(n + 1):
    sort_a.append([a[i], i])

a.sort()
sort_a.sort()
b.sort()
p  =[i[1] for i in sort_a] #p[i]，sortされたi番目の要素の元々のindex

ans = [-1] * (n + 1)
tmp_ans = 0
for i, j in zip(a, b):
    tmp_ans = max(i - j, tmp_ans)
ans[p[-1]] = str(tmp_ans) #joinできるようにsrtにする

for i in reversed(range(n)):
    tmp_ans = max(a[i + 1] - b[i], tmp_ans) #ネクタイをずらす
    ans[p[i]] = str(tmp_ans) #joinできるようにsrtにする

print(' '.join(ans))

できたこと

• 最小値になるのは，Aを昇順でsortしたときになること

学んだこと

• 多次元配列をinで引っぱてくるときに，その要素数と同じ数の変数で受けとれる
• indexと要素を一緒にもって考える．←けっこう使う

PythonでJOI難易度6を埋める #13

B - JJOOII 2 (JJOOII 2)

全てのJから条件を満たす文字列を作るのに，どれだけの操作が必要かを考えればよい．それぞれの文字のi番目のindexが分かっていると早く計算できる．'O'，'I'の開始位置を二分探索で求める． 参考(コピペ)した記事

from bisect import bisect_left
from sys import stdin
input = stdin.readline

n, k = map(int, input().strip().split())
s = input().strip()

index_j = [] #Jのindex
index_o = [] #Oのindex
index_i = [] #Iのindex

for i in range(n):
    if s[i] == 'J':
        index_j.append(i)
    if s[i] == 'O':
        index_o.append(i)
    if s[i] == 'I':
        index_i.append(i)

ans = float('inf')
for start_j in range(len(index_j) - k + 1):
    cnt = index_j[start_j + k - 1] - index_j[start_j] - (k - 1) #start_jからK個のkの間の個数

    start_o = bisect_left(index_o, index_j[start_j + k - 1]) #start_jからK個めのJの位置で二分探索
    if start_o + k > len(index_o): #start_oから後ろにK個の'O'がない
        continue

    cnt += index_o[start_o] - index_j[start_j + k - 1] - 1 #間の文字を数えるので -1
    cnt += index_o[start_o + k - 1] - index_o[start_o] - (k - 1) #start_oからK個のOの間の個数

    start_i = bisect_left(index_i, index_o[start_o + k - 1]) #start_oからK個目のOの位置で二分探索
    if start_i + k > len(index_i): #start_iから後ろにK個の'I'がない
        continue

    cnt += index_i[start_i] - index_o[start_o + k - 1] - 1
    cnt += index_i[start_i + k - 1] - index_i[start_i] - (k - 1)

    ans = min(cnt, ans)

if ans == float('inf'): #条件を満たす文字列が作れない
    print(-1)
else:
    print(ans)

できたこと

• なし

• 各文字のindexを前処理で計算しておく

学んだこと

• 文字列の順番が決まっているときは二分探索で範囲を絞れる
• 個数をindexの差から求める

PythonでJOI難易度6を埋める #12

C - 夜店 (Night Market)

問題からDP感がでてる．時刻からまでのDP1，時刻からまでのDP1で解く．
DP1[ i ][ j ] := お店 i まで調べて，時刻jまでに実現できる最大の楽しさの和．
DP2は1と考えかたが逆で，
DP2[ i ][ j ] := 時刻 j からお店 i ~ N を訪ずれたときの最大の楽しさの和．

どちらのDPをお店に入るか，入らないかの2択のうち大きい方で更新していきます． 参考にした記事にも書いてあるように，Pythonだと間に合わないので C++ をコピペしました，許して

//#define _GLIBCXX_DEBUG

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define uint unsigned int
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1000000000;

int main() {
    IOS;
    int N,T,S;
    cin >> N >> T >> S;
    vector<int>A(N);
    vector<int>B(N);

    for (int i=0; i<N; i++){
        cin >> A[i] >> B[i];
    }

    vector<vector<int>>dp(N+1, vector<int>(T+1));
    // dp[a][b] := 店aまで見て時刻bまでに実現できる最大の楽しさ

    for (int i=0; i<N; i++){
        for (int j=0; j<=S; j++){
            chmax(dp[i+1][j], dp[i][j]);
            if (j-B[i] >= 0)chmax(dp[i+1][j], dp[i][j-B[i]] + A[i]);
        }
    }
  vector<vector<int>>dp2 (N+1, vector<int>(T+1));
  for (int i=N; i>=1;i--){
    for (int j=T; j>=S; j--){
      chmax(dp2[i-1][j], dp2[i][j]);
      if (j+B[i-1]<=T) chmax(dp2[i-1][j], dp2[i][j+B[i-1]]+A[i-1]);
    }

  }
    int ans = -INF;
    for (int i=0; i<N; i++) chmax(ans, dp[i][S]+dp2[i+1][S]);
    cout << ans << endl;
}

できたこと

• 二つのDPに分けて考える

学んだこと

• C++ での，逆順でのfor文
• 2つのDPを用いたときの，繋げ方

PythonでJOI難易度6を埋める #11

ひさしぶりの写経しました．

E - イルミネーション (Illumination)

建物の中にあるイルミネーションしないマスをどうやって数えるかが分からなかった．

写した記事

from sys import stdin
input = stdin.readline

w, h = map(int, input().strip().split())
g = [list(map(int, input().strip().split())) for _ in range(h)]

for i in range(h):
    g[i] = ['x'] + g[i] + ['x']
g.insert(0, ['x'] * (w + 2))
g.append(['x'] * (w + 2))
w, h = len(g[0]), len(g)

directs = [[(0, 1), (0, -1), (-1, 0), (1, 0), (1, -1), (-1, -1)], [(0, 1), (0, -1), (-1, 1), (1, 1), (1, 0), (-1, 0)]]

visited = [[0] * w for _ in range(h)]
stack = [(0, 0), (1, 0)]

while stack:
    i, j = stack.pop()
    visited[i][j] = 1
    direct = directs[i % 2]

    for dh, dw in direct:
        fh, fw = i + dh, j + dw
        if not ((0 <= fh < h) and (0 <= fw < w)):
            continue
        if visited[fh][fw]:
            continue
        if g[fh][fw] == 1:
            continue

        g[fh][fw] = 'x'
        stack.append((fh, fw))

ans = 0
for i in range(h):
    for j in range(w):
        if g[i][j] == 'x':
            continue
        direct = directs[i % 2]
        if g[i][j] == 1:
            cnt = 0
            for dh, dw in direct:
                fh, fw = i + dh, j + dw
                if not ((0 <= fh < h) and (0 <= fw < w)):
                    continue

                if g[fh][fw] == 1:
                    cnt += 1
            ans += 6 - cnt

        if g[i][j] == 0:
            cnt = 0
            for dh, dw in direct:
                fh, fw = i + dh, j + dw
                if not ((0 <= fh < h) and (0 <= fw < w)):
                    continue

                if g[fh][fw] == 1:
                    cnt += 1

            ans -= cnt

print(ans)

PythonでJOI難易度6を埋める #10

ioi - 国際情報オリンピック (IOI)

沼った．途中のACはちゃんと解いてないやつ．

• score = 与えられる各選手の得点
• final_score = 自分以外の選手が残りの問題を完答したときの得点() を昇順でsort
• sort_score = 与えられる得点を昇順でsort
• limit_num = 金メダルがもらえる人数
• index_final = final_scoreに二分探索(right)でscore[i]を挿入したときのindex
• index_sort = sort_scoreに二分探索(right)でscore[i]を挿入したときのindex

のときは，final_score = sort_scoreになることに注意
基本的な指針は，

• 自分以外の選手が残りの問題を完答しても(final_score)，自分の最初の点数がlimit_num以内 → 確定で貰える
• 自分だけが残りの問題を完答すれば，limit_num以内 → 可能性がある

．

score[i]がfinal_scoreに追加されるとき，されるので，の場合以外はscore[i]よりも大きい値が追加されることになる．なので，index_finalは自分が残りの問題を完答したときの得点も追加されてある状態でのindexなので，は，index_final - 1が順位となる．

これをすべての得点で行なえばよい．

from math import ceil
from bisect import bisect_right

k, n, m = map(int, input().split())
score = [int(input()) for _ in range(k)]

limit_num = ceil(k / 12)

sort_score = sorted(score)
now_rate = []
final_socre = []

for i in range(k):
    rate = bisect_right(sort_score, score[i])
    now_rate.append([i, k - rate])
    final_socre.append(score[i] + 100 * (n - m))

now_rate.sort()
final_socre.sort()

check = set([])
for i in range(k):
    if n == m:
        if k - bisect_right(final_socre, score[i]) < limit_num:
            print(i + 1)
    if n != m:
        if k - bisect_right(final_socre, score[i]) <= limit_num:
            print(i + 1)

print('--------')

for i in range(k):
    if bisect_right(sort_score, score[i] + 100 * (n - m)) > k - limit_num:
        print(i + 1)

PythonでJOI難易度6を埋める #9

banner - 横断幕 (Banner)

愚直に計算すると組み合わせ数が爆発して死．
そこで，4個の頂点のなかで，1個の頂点の色は自由に選べることに注目する．長方形から1つの頂点を取り除いた形で，他の3個の頂点の色が全て異なるような図形を考える．その図形はのこりの1頂点に，どの色を当てはめても条件を満たす組合せとなるので，そのような図形の数を数える．事前にそれぞれの行，列で色の個数を数えておく．点が黒色だとすると，求めたい図形の個数は，同じ行の白の個数 同じ列の灰の個数 + 同じ行の灰の個数 同じ列の白の個数となる．これをそれぞれの全ての頂点で行ない，その合計をとる．今数えた図形から，まったく同じ2個の長方形ができるので，合計を2で割ったものが答え．図を用いた分かりやすい解説

from sys import stdin
input = stdin.readline

h, w = map(int, input().strip().split())
maps = [list(map(int, input().strip().split())) for _ in range(h)]

count_maps_h = [[0, 0, 0] for _ in range(h)] #黒，灰，白
count_maps_w = [[0, 0, 0] for _ in range(w)] #黒，灰，白

for i in range(h):
    for j in range(w):
        if maps[i][j] == 0:
            count_maps_h[i][0] += 1
            count_maps_w[j][0] += 1
        if maps[i][j] == 1:
            count_maps_h[i][1] += 1
            count_maps_w[j][1] += 1
        if maps[i][j] == 2:
            count_maps_h[i][2] += 1
            count_maps_w[j][2] += 1

ans = 0

for i in range(h):
    for j in range(w):
        if maps[i][j] == 0:
            ans += count_maps_h[i][1] * count_maps_w[j][2] + count_maps_h[i][2] * count_maps_w[j][1]
        if maps[i][j] == 1:
            ans += count_maps_h[i][0] * count_maps_w[j][2] + count_maps_h[i][2] * count_maps_w[j][0]
        if maps[i][j] == 2:
            ans += count_maps_h[i][0] * count_maps_w[j][1] + count_maps_h[i][1] * count_maps_w[j][0]

print(ans // 2)