2022年8月27日開催のABC266 解説＆反省会。D問題、後少しというとこで時間ぎれでした。。B問題で焦ってもたついたのも反省です。
DPとかも元々苦手でしたが、徐々に解けるようにはなってきています。ですが、歩みが遅すぎて自分に嫌気がさしますが、めげずにマイペースに今後も頑張っていきます！
バックナンバーはこちらから！
コンテンツ一覧
A - Middle Letter
問題
英小文字からなる長さが奇数の文字列\(\ S \) が与えられます。
\(\ S \) の中央の文字を出力してください。
制約と入力形式
- \(\ S \) は英小文字からなる長さが奇数の文字列
- \(\ S \) の長さは\(\ 1 \) 以上 \(\ 9999 \) 以下
回答アプローチ
奇数で与えられることが決まっているので割と簡単です。偶数の場合は中心２文字とかだと若干厄介になりますが。
S = input()
print(S[int(len(S)/2)])B - Modulo Number
問題
\(\ -10^{18} \leq N \leq 10 ^{18} \)となる整数\(\ N \) が与えられます。
以下の条件を満たす\(\ 0 \) 以上 \(\ 998244353\) 未満の整数 xx を求めてください。なお、答えが一意に定まることが証明できます。
- \(\ N-x\) は \(\ 998244353\) の倍数
制約と入力形式
- \(\ -10^{18} \leq N \leq 10 ^{18} \)
- \(\ N\) は整数
回答アプローチ
マイナスの場合を考慮しなきゃなどと、なぜか色々複雑に考えてしまいたした。普通にPythonは剰余を取れば行けたみたいですね。
import math
N = int(input())
k = 998244353
if N > 0:print(N-(int(N/k))*k)
else:
if N-(math.ceil(N/k)*k)<0:
print(N-(math.ceil(N/k)*k)+k)
else:
print(N-(math.ceil(N/k)*k))Pythonなら、普通にこれでOKです。馬鹿でした。。
N = int(input())
print(N%998244353)C - Convex Quadrilateral
問題
\(\ 2 \) 次元座標平面があります。\(\ x \) 軸正方向を右向き、\(\ y \) 軸正方向を上向きとします。
この平面上に自己交差のない四角形があります。
\(\ 4 \) つの頂点の座標は反時計回りに\(\ (A_x,A_y),(B_x,B_y),(C_x,C_y),(D_x,D_y) \) です。
この四角形が凸であるか判定してください。
なお、四角形の\(\ 4 \) つの内角が全て\(\ 180 \) 度未満であるとき、かつ、その時に限り、その四角形は凸であるといいます。
制約と入力形式
- \(\ -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\leq100 \)
- 入力に含まれる値は全て整数である
- 与えられる\(\ 4 \) 点は四角形の\(\ 4 \) 頂点を反時計回りに並べたものである
- 与えられる\(\ 4 \) 点のなす四角形は自己交差がなく退化していない。すなわち
- どの\(\ 2 \) 頂点も同じ座標にない
- どの\(\ 3 \) 頂点も同一直線上にない
- 隣接しない\(\ 2 \) 辺は共有点を持たない
回答アプローチ
最初は単純に、３点の情報から内積の式より \(\ cos\theta \) を導き出して、逆三角関数を取れば良いなと思ってました。
\(\ \vec{a} = (a_1,a_2),\vec{b} = (b_1,b_2) \)
\(\ cos\theta = \frac{a_1 \times b_1+a_2\times b_2}{\sqrt{a_1^2 + a_2^2}\sqrt{b_1^2+b_2^2}} \)
しかし結局これでは、その角が四角形として\(\ 180 \)度以上か否かが不明です。（結局小さい方の角度が出てきてしまいます。）
そこで、4つの角の合計の角度が\(\ 360度(2\pi) \) に満たない場合は、\(\ 180 \)度以上の角度が含まれるとして、凸か否かを判定する形としました。（まあ、誤差の部分でちょっとズルが入ってますね）
import math
ax,ay = map(int,input().split())
bx,by = map(int,input().split())
cx,cy = map(int,input().split())
dx,dy = map(int,input().split())
def arc_cos(a1,a2,b1,b2):
return math.acos((a1*b1+a2*b2)/(math.sqrt(a1**2+a2**2)*math.sqrt(b1**2+b2**2)))
if arc_cos(dx-ax,dy-ay,bx-ax,by-ay) + \
arc_cos(ax-bx,ay-by,cx-bx,cy-by) + \
arc_cos(bx-cx,by-cy,dx-cx,dy-cy) + \
arc_cos(ax-dx,ay-dy,cx-dx,cy-dy) < 2*math.pi-0.01:
print("No")
else:
print("Yes")上記のやり方だと逆三角関数を使っちゃうので、誤差が発生しやすいです。極めて直線に近い角度をなす角があると誤った判定が出てしまいます。「角度」で考えるとラジアンでも度数法でも誤差が生じやすくなります。
そこで、四角形の２本の対角線が交わるか否かという点で考えます。交わるか否かの判定として、対角線を形成しない残り２つの点が対角線のどちら側（右か左かのような）のあるかを判定します。残り２つの点が一方に偏っていると、それは交わっていないということになります。
この対角線のどちらにあるかという判定は外積を用いて求めます。
例えば、今回の問題の四角形\(\ A,B,C,D \) の対角線 \(\ \vec{A,C} \) について、\(\ \vec{A,B} \) と\(\ \vec{A,D} \) それぞれとの外積を求めます。それぞれの外積が両方とも正または負の時は、対角線に対して残り２つの点が偏った配置になっていることがわかるので、四角形は凸ではないことになります。この判定をもう一方の対角線に対しても行い、凸になる配置ではないことを確かめます。
むやみにnumpyを使うと実行速度が遅くなりますが、今回の様に外積計算を数回使う程度ならばベクトル計算が楽なnumpyを使っても良いでしょう。numpyでは外積を np.cross で求められます。
import numpy as np
P = {}
for x in ["a","b","c","d"]:
P[x] = np.array(list(map(int,input().split())))
vec=lambda s: P[s[-1]]-P[s[0]]
if np.cross(vec("ac"),vec("ab"))*np.cross(vec("ac"),vec("ad"))<0 \
and np.cross(vec("bd"),vec("ba"))*np.cross(vec("bd"),vec("bc"))<0:
print("Yes")
else:
print("No")D - Snuke Panic (1D)
問題
高橋君はすぬけ君たちを捕まえようとしています。
数直線上の座標 \(\ 1, 2,3,4,5 \)の\(\ 5 \)箇所に穴があり、すぬけ君たちの巣につながっています。
これから\(\ N \) 匹のすぬけ君が穴から出てきます。\(\ i \) 番目のすぬけ君は時刻\(\ T_i \) に座標\(\ X_i \) の穴から出てきて、大きさは\(\ A_i \) であることがわかっています。
高橋君は時刻\(\ 0 \) に座標\(\ 0 \) におり、数直線上を単位時間あたり\(\ 1 \) 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。
高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。
制約と入力形式
- \(\ 1 \leq N \leq 10^5 \)
- \(\ 0 < T_1 < T_2 < \ldots < T_N \leq 10^5 \)
- \(\ 0 \leq X_i \leq 4 \)
- \(\ 1 \leq A_i \leq 10^9 \)
- 入力に含まれる値は全て整数である
回答アプローチ
動的計画法で解いていきます。各時刻について、それぞれの座標上に居る時に捕まえることのできる合計値の最大値を保存していくDPで解いていきます。
ある時刻において存在することが不可能な座標（時刻１の時に座標４には存在できない）については、\(\ -1 \) として管理します。
公式解説では、時刻\(\ 1 \) から時刻\(\ 10^5 \) まで時刻\(\ 1 \) 刻みでDPを管理してますが、与えられた\(\ N \) 個の時刻だけで管理した方がパフォーマンスが良いです。\(\ T_{n-1} \) と \(\ T_{n} \) の差分から、その時間内に行動出来る範囲を決定して、その行動範囲内の中から最大値でDPを更新すれば良いです。
N = int(input())
DP = [[-1]*5 for _ in range(N+1)]
T,X,A = [],[],[]
for _ in range(N):
t,x,a = map(int,input().split())
T.append(t)
X.append(x)
A.append(a)
DP[0][0] = 0
t_b = 0
for i in range(N):
t = T[i]-t_b #行動できる範囲のMax
for j in range(5):
DP[i+1][j]=max(DP[i][max(0,j-t):min(5,j+t+1)]) #行動できる範囲内のMAXで更新
if DP[i+1][X[i]]>=0:
DP[i+1][X[i]] += A[i]
t_b=T[i]
print(max(DP[-1]))E - Throwing the Die
問題
サイコロを使ったゲームをします。ゲームは最大\(\ N \) 回のターンからなり、各ターンは次のように進行します。
- \(\ 1,\ldots,6 \) の目が等確率で出る\(\ 6 \) 面ダイスを振り、出目を\(\ X \) とする(出目は各ターンで独立とする)。
- 現在が\(\ N \) ターン目なら、スコア を\(\ X \) とし、ゲームを終了する。
- そうでないとき、ゲームを続行するか終了するか選択する。
- ゲームを終了する場合、スコアを\(\ X \) とし、残りのターンは行わずにゲームを終了する。
スコアの期待値が最大になるように行動したとき、スコアの期待値を求めてください。
制約と入力形式
- \(\ 1 \leq N \leq 100 \)
回答アプローチ
「スコアの期待値が最大になるように行動したとき」というのは、例えば、ある目が出た状態でダイスを振った方が期待値が大きい時はダイスを振るということですね。
例えば、上限を2ターンで考えてみます。まず、1回、サイコロを振ります。この時、幾つ以上の目が出たら2回目を振る必要がないでしょうか？サイコロを一回振る時の期待値は\(\ 3.5 \) です。つまり、この時は1回目のサイコロの目が\(\ 4 \) 以上なら2回目は振りません。これを3回目、4回目と繰り返していくだけです。
\(\ N = 1 \) の時の期待値
$$ \frac{1}{6} + \frac{2}{6} + \frac{3}{6} + \frac{4}{6} + \frac{5}{6} + \frac{6}{6} = \frac{21}{6} = 3.5 \tag{1}$$
\(\ N = 2 \) の時の期待値（出た目が\(\ 3 \)以下ならもう一度降り直した方が良く、\(\ 4 \) 以上なら終了）
$$ (1) \times \frac{3}{6} + \frac{4}{6} + \frac{5}{6} + \frac{6}{6} = \frac{3.5}{2} + \frac{15}{6} = 4.25 \tag{2} $$
\(\ N = 3 \) の時の期待値（出た目が\(\ 4 \)以下ならもう一度降り直した方が良く、\(\ 5 \) 以上なら終了）
$$ (2) \times \frac{4}{6} + \frac{5}{6} + \frac{6}{6} = \frac{4.25\times 4}{6} + \frac{11}{6} = 4.666\ldots \tag{3} $$
と、これを与えられる\(\ N \) まで計算すればOKです。
N = int(input())
dp = [3.5]
for _ in range(N-1):
dp.append(dp[-1]*int(dp[-1])/6+sum([i for i in range((int(dp[-1])+1),7)])/6)
print(dp[-1])