AtCoder ABC107参戦記

今回はC問題まで解けましたが、700点のD問題には手も出ませんでした。しかし他の人も解けていなかったこともあって、3完でパフォーマンスが1200ちょっとでて、無事緑コーダーになりました。この記事ではB, C問題のコードと考え方を書きます。D問題は実装出来たらそのうち書くかもしれません。

B問題 (Grid Compression)

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
delJ = []
for j in range(W):
    judge = True
    for i in range(H):
        if A[i][j] == "#":
            judge = False
            break
    if judge:
        delJ.append(j)
 
output = []
for i in range(H):
    if "#" in A[i]:
        B = ""
        for j in range(W):
            if j not in delJ:
                B += str(A[i][j])
        output.append(B)
 
for i in output:
    print(i)

消去する列を探索したのちに、行ごとに出力形式を整える処理を行っています。j列に一つも"#"がなかった場合、delJにjが記録されます。すべての列を判定後、今度はi列を見ます。もしA[i]がすべて"."なら出力しません。一つでも"#"がある場合、delJに記録されている列を消去した文字列をoutputに記録します。

C問題 (Candles)

import numpy as np
N, K =map(int, input().split())
X = [int(_) for _ in input().split()]
X2 = np.zeros((N,))
X2 += X
minus = X2[X2 < 0] * (-1)
minus.sort()
plus = X2[X2 >= 0]
lenM, lenP = len(minus), len(plus)
 
def length(i, j):
    if i == 0:
        return plus[j-1]
    if j == 0:
        return  minus[i-1]
    else:
        LtoR = min(minus[i-1], plus[j-1])
        return plus[j-1] + minus[i-1] + LtoR
 
minLength = 1000000000
for i in range(0, K+1):
    a, b = i, K-i
    if lenM >= a and lenP >= b :
        minLength = min(minLength, length(a, b))
 
print(int(minLength))

非常にnumpyモジュールの配列操作が便利だなと感じた問題でした。まずはどうやって移動時間を求めるかですが、移動速度が1なので、最短経路を求める問題になります。最短経路ですが、何回も正の座標と負の座標を行き来するのではなく、正、負それぞれ行けるところまでいった後に、反対方向に進むのが最適です。ですので、正負それぞれ何本のろうそくをめぐるか、そしてどちらを先にめぐるれば最短でK本のろうそくを訪問できるかという問題になります。