総括
ABC解けました。
D,Eは方針まで立てられたのですが時間内に解けず。
今回は初めてF問題まで考えることができました（解けるか否かはまた別の話・・・）
後日Eは解けましたが、DはWAをつぶしきれずいまだACしていません。
#問題
https://atcoder.jp/contests/abc175
A. Rainy Season
回答
S = tuple(input())
if S == ('R', 'R', 'R'):
print(3)
elif S == ('R', 'R', 'S') or S == ('S', 'R', 'R'):
print(2)
elif S == ('S', 'S', 'S'):
print(0)
else:
print(1)
上手い具合の解き方がないか考えましたが、思いつかず。
全部列挙してif文で解きました。
コンテスト時はわざわざtupleにいれましたが、文字列をそのまま判定してよいですね。
B. Making Triangle
回答
from itertools import combinations
N = int(input())
L = list(map(int, input().split()))
count = 0
for C in combinations(L, 3):
l_list = list(C)
l_list.sort()
if l_list[2] > l_list[1] and l_list[1] > l_list[0]:
if l_list[2] < l_list[1] + l_list[0]:
count += 1
print(count)
三角形の条件なので、最大の辺 < その他の2辺の和で解けます。
制約が小さいので全部列挙しました。
C. Walking Takahashi
回答
X, K, D = map(int, input().split())
new_X = abs(X) % D
new_K = K - abs(X) // D
if new_K <= 0:
answer = abs(X) - K*D
else:
if new_K % 2 == 0:
answer = new_X
else:
answer = abs(new_X - D)
print(answer)
まず制約がきつすぎるので、for文は絶対に使いたくないです。
これだけ大きい数字を処理するのですから、「大きい数を何かの数で割り算を行う」という処理がどこかに入ってくると予想ができます。
そう考えると、座標Xを移動距離Dでとりあえず割ってみたくなります。
X // Dの意味を考えてみると、「X距離進むために必要な距離Dの移動の回数」であるとわかります。
「移動の回数」ときたらKから引き算をしたくなりますね。
次に、いくつか入力サンプルで実験すると、DがXより十分に大きい場合は原点付近で振動することがわかります。
振動するということは、答えは二通りだなとわかります。
ここまでくるとだいぶ方針が固まってきました。
-
K - X // Dを行い残りの回数を算出 - 原点付近で振動するのでその2通りの場合分けを行い、答え算出
- あとは正負の扱いに注意して、XがDより十分に大きい場合の例外を処理
これをコードに落とします。
D. Moving Piece
回答（これは半分WAとなります）
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
answer = -float('inf')
for start_p in range(1, N+1):
cycle_total_score = 0
cycle_in_score = -float('inf')
cycle_count = 0
next_p = P[start_p]
while True:
cycle_total_score += C[next_p]
cycle_in_score = max(cycle_in_score, cycle_total_score)
cycle_count += 1
if next_p == start_p:
# print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
break
next_p = P[next_p]
max_score = 0
if K == cycle_count:
max_score = cycle_in_score
else:
#あふれたK % cycle_count回数分だけスコアを足すためにmaxを探さす
add_max_count = K % cycle_count
add_total_score = 0
add_score = -float('inf')
add_count = 0
add_next_p = P[start_p]
while True:
add_total_score += C[add_next_p]
add_score = max(add_score, add_total_score)
add_count += 1
if add_count == add_max_count:
break
add_next_p = P[add_next_p]
if K < cycle_count:
#最大の試行回数がcycle_countよりも小さい場合K % cycle_countまでで一番良いところでbeak
max_score = add_total_score
else:
if cycle_total_score >= 0:
#1サイクルでプラスの場合はできるだけサイクルを回してK % cycle_countまでで一番良いところでbeak
max_score = (K // cycle_count) * cycle_total_score + add_total_score
else:
#1サイクルでマイナスの場合はサイクルを回さないで、K % cycle_countまでで一番良いところでbreak
max_score = add_total_score
# print('max_score', max_score)
answer = max(answer, max_score)
print(answer)
いまだにACをとることができていません。上記コードではテスト入力はすべて通るのですが、本番では半分がWAとなります。
考え方はあっていると思うのですが、WAの原因を特定しきれていません・・・。
文字だけだと何を言っているかわからないので図を描きます。下記は入力例１を図示化したものです。
この図の特徴を考えると、サイクルを持ったグラフが1つ以上作成できることがわかります。
解く方針は愚直に全通りを試します。
- まずはスタートする場所を決める=>これをN通り試す
- スタートから一回りしてみて、下記のスコアを記録しておく
2.1 . 1サイクルの合計のスコア
2.2. 1サイクル内で最大となる瞬間のスコア
2.3. 1サイクルに必要な移動の数 - Kが1サイクルの移動数の整数倍であれば簡単ですが、中途半端の時があり得るのでその場合に下記スコアを探しに行きます
3.1. 中途半端となる数
3.2. 中途半端となる数のなかで最大となるときのスコア
たぶんこれで解けるはずなのですが、最後まで解けきれていません（ということはこれで解けないのでは？）。
E. Picking Goods
回答（通常版 TLEです）
R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
r, c, v = map(int, input().split())
scores[r][c] = v
dp = [[[0] *4 for _ in range(C+1)] for _ in range(R+1)]
for i in range(1, R+1):
for j in range(1, C+1):
for k in range(4):
dp[i][j][k] = max(dp[i][j-1][k],
dp[i-1][j][3])
for k in range(3, 0, -1):
dp[i][j][k] = max(dp[i][j][k],
dp[i][j][k-1] + scores[i][j])
answer = dp[R][C][3]
print(answer)
回答（高速化ver ACです）
from numba import jit
import numpy as np
@jit
def main():
R, C, K = map(int, input().split())
scores = np.zeros((R,C), np.int64)
for _ in range(K):
r, c, v = map(int, input().split())
scores[r-1][c-1] = v
dp = np.zeros((R+1,C+1,4), np.int64)
for i in range(1, R+1):
for j in range(1, C+1):
for k in range(4):
dp[i][j][k] = max(dp[i][j-1][k],
dp[i-1][j][3])
for k in range(3, 0, -1):
dp[i][j][k] = max(dp[i][j][k],
dp[i][j][k-1] + scores[i-1][j-1])
return dp[R][C][3]
print(main())
これは時間内に解きたかったです。
Pythonで普通に組んでしまうと時間がギリギリ間に合いませんが、numpyと@jitでもとのコードを改良すれば通ります。
まずは問題を読んでDPであることがわかりました。しかし僕が解けるのはまだ2次元のDPまで・・・。
とりあえず「同じ行で3個まで」の制約を無視してDPを書いてみます。
すると下記のようになります。
（2次元のDPテーブルを可視化する際はpandasを使うと縦横が見やすくなるのでデバック用としてpandasとnumpyをいれてます)
R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
r, c, v = map(int, input().split())
scores[r][c] = v
dp = [[0] *(C+1) for _ in range(R+1)]
for i in range(1, R+1):
for j in range(1, C+1):
dp[i][j] = max(dp[i-1][j] + scores[i][j],
dp[i][j-1] + scores[i][j])
print(dp[R][C])
# import numpy as np
# import pandas as pd
# show_dp = np.array(dp)
# show_dp = pd.DataFrame(show_dp)
# print(show_dp)
ここまでは簡単です。
コンテスト時はここから「同じ行で3個まで」の制約を組み込むことができませんでした。
dpテーブルの次元を一つ増やして「何か」すればよいということはわかったのですが、この「何か」を思つくことができませんでした。
「横に行くときは3回目まではscoreを追加し、それ以外は追加しない」をそのまま書いてみます。
僕はdpを解くときは実際にdpテーブルを紙に書いて視覚化しないとうまくイメージがつかないので、3次元のdpテーブルはなかなかしっくりこないです・・・。
習うより慣れろというところでしょうか。
ところで、pythonでは普通にdpでコード化するとTLEになります。
方針としてはnumpyを使ってfor文で書いているところを一括で計算するか、pypyを使うか、jitを使うか、と思います。
強い人は当然にnumpyで上手いこと計算しているようですが、僕はまだそこまでは書けません。
今回のコードではpypyでも通りませんでしたので、関数化して@jitを使ってみました。
すると、下記のように「少量の計算は格段に遅く、大量の計算は格段に速く」なり、なんとかAC通りました。どうしてこうなるのかわかりませんが、とりあえずdpで通らない場合は同じようにjitで試してみます。
【普通のコードの場合】
【@jitを使用したコードの場合】
