ABC018を解いてみた
A問題
aより大きいbが存在すれば、aの順位は一つ落ちることになります。a, b, cの大小関係を調べこの条件にのっとって順位を表す変数の変更しました。
a = int(input())
b = int(input())
c = int(input())
ranka = 1
rankb = 1
rankc = 1
if(a > b):
rankb += 1
else:
ranka += 1
if(a > c):
rankc += 1
else:
ranka += 1
if(b > c):
rankc += 1
else:
rankb += 1
print(ranka)
print(rankb)
print(rankc)
B問題
最初はstr[i]として文字列を1文字ずつ取り出し処理しようとしたのですが、Pythonではこの表現に対応していませんでした。そこでスライスという機能を用いて文字列の処理を行いました。s[l:r]で文字列sのl番目からr-1番目までを取り出すことができ、s[::-1]とすることでsを逆順に並べ替えることができます。これを用いて条件にそって処理を行っていきました。
qiita.com
s = list(input())
n = int(input())
for i in range(n):
l, r = map(int, input().split())
s[l-1:r] = s[l-1:r][::-1]
print("".join(s))
C問題
全探索しか思い浮かばなかったので解説を読んで満点解法のアルゴリズムを実装しました。…のですがそれでもTLEで不正解になってしまいました。枝刈りをしようと考えて、縦、横の半分が K より小さい場合にひし形を書けることはありえないため0を出力してプログラムを終了、および端kマスがひし形のの中心になることはないため探索範囲から抜くとしました。…ですが、それでもTLEで実行時間は2秒を完全にオーバーしていました。計算量は O(RCK)≒O(1.2×10^8) 程度でギリギリなんとかなるかなと思ったのですが間に合わなかったようです。結果を見たところPython3でACを出しているかたがいらしゃったのでコードを読んで理解したいと思います。その方でも1.998秒で超ギリギリだったのでPythonにはかなり厳しい制約なんですかね…？
import sys, time
# 入力
r, c, k = map(int, input().split())
s = [[i for i in input()] for j in range(r)]
board = [[0 for i in range(c)] for j in range(r)]
# ひし形をかけることはありえないため終了
if( r/2 < k or c/2 < k):
print(0)
sys.exit()
up = 0
down = 0
for i in range(r):
for j in range(c):
#(i, j)マス目が中心のとき
#下に探索
for l in range(k+1):
#端までいっていればループ終了
if(i + l >= r): break
if(s[i+l][j] == "o"):
up += 1
# x にたどり着いたらループ終了
else:
break
#上に探索
for l in range(k+1):
if(i - l < 0): break
if(s[i-l][j] == "o"):
down += 1
else:
break
#上下の探索で少ない方を記録
board[i][j] += min(up, down)
up = 0
down = 0
#print(board)
flag = 1
ret = 0
# 端kマスがひし形の中心になることはない
for i in range(k-1, r-k+1):
for j in range(k-1, c-k+1):
#(j, i)マス目が中心のとき
for l in range(-k+1, k):
# 中心から数えて左右k-1マスずつについて判定し条件にあっていれば答えに+1する
if(j+l < 0 or j+l >= c or board[i][j+l] < k-abs(l)):
flag = 0
break
if(flag == 1): ret += 1
flag = 1
print(ret)
D問題
C問題と同じく全探索の部分点解法しか思い浮かばなかったので解説を読んで実装しました。まず、x, y, zの表現を二次元配列を用いて女の子iから男の子jに渡すときの幸福度を示すという形で表現しました。そして、itertools.combinations()を用いて全ての女の子の組み合わせを全列挙し、それに対応する部分の幸福度を抜き出します。そして、幸福度が大きい順にQ人分足し合わしたもので一番大きくなるものを出力しました。
import itertools, time
# 入力
n, m, p, q, r = map(int, input().split())
xyz = [[int(i) for i in input().split()] for j in range(r)]
# relation[j][i] 女の子jから男の子iに渡すときの幸福度
relation = [[0 for i in range(m)] for j in range(n)]
for i in range(r):
relation[xyz[i][0]-1][xyz[i][1]-1] = xyz[i][2]
maxvalue = 0
for e in itertools.combinations(range(n), p):
# 固定した女の子に合わせて幸福度の配列を作成する
v = [relation[i] for i in range(n) if i in e]
# 転置して合計を取ってそれをリストに
# num[i] 男iが参加した時の幸福度
num = list(map(sum, zip(*v)))
# 幸福度を大きい順にソート
num.sort(reverse=True)
# maxvalueにもっとも大きな幸福度を表すように比較
maxvalue = max(maxvalue, sum(num[:q]))
print(maxvalue)
雑感
B問題→文字列処理、スライスが便利
C問題→探索方法を工夫（Pythonだと時間が厳しい…？）
D問題→片側全列挙
