先日行われた第一回日本最強プログラマー学生選手権-予選-に参加しました。結果は以下の通りです。
結果:A+B+C 3完 55分+2ペナ
順位:472/3534
パフォーマンス:1803
レート変動:1504→1540
青パフォです、やったー。ただ残念ながら本戦には出場できなそうです(50人くらい辞退してくれないかなぁ...)。
以下問題を振り返っていきます。
A
time 3:00
全探索して条件を満たすものを数えればいいです
M, D = map(int, input().split())
ans = 0
for m in range(1, M+1):
for d in range(1, D+1):
d1 = d%10
d10 = d//10
if d1>=2 and d10>=2 and m==d1*d10:
ans+=1
print(ans)
B
time 7:00
また数え上げですね。O(N^2)が通るので、Aの中の各要素について、それより大きい数字を数え上げ、等差数列の和を求めればできます。焦っていたので結構なクソコードを錬成しました。変数名のセンスをください
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
for i in range(N):
Sum = 0
Sum1 = 0
a = A[i]
for j in range(N):
if A[j]<a:
Sum+=1
if i==j:
Sum1 = Sum
ans+=Sum*(K-1)*K//2+(Sum-Sum1)*K
ans%=mod
print(ans)
300にしては少し面倒ですね
C
よくある反転させる系の問題です。アリ本にも同じようなのがありましたね。こう言う問題は、
- 操作の順序は関係ない
-
端が返されるのは一回限りである
ことから、端から操作を決められる事が多いです。
まず、ポイントは操作の順序を無視して区間の左端でソートした操作の順序で考えても良いという点です。もう一つ重要なポイントは各A[i]についてそこから区間が始まるか、終わるかのいずれかであり、実は左端から順番に見ていくと、偶奇性から各A[i]に関して、そこで区間が終わるのか、区間が始まるのかのどちらかに決まってしまうという点です。
具体的に見ていきましょう。A=BWWBを考えます。まずA[1]は区間が始まることしかありえません。次にA[2]を考えてみると、A[2]はA[1]から始まる区間に含まれるので少なくとも1回はひっくり返ります。しかし、A[2]はWなので、もう一回ひっくり返る必要があります。よってA[2]から新しい区間が始まることがわかります。次にA[3]を考えると、すでにA[1],A[2]から始まっている区間に含まれることは確定しているので、少なくとも2回はひっくり返ります。A[3]は白なのでもうひっくり返る必要はありません。そこでA[3]ではA[1]かA[2]のいずれかの区間が終わることになります。実はこのどちらを終わらせたとしても後々影響はありません（各要素が幾つの区間に含まれているかだけが問題となるため）。よって、ここまでで2通りの区間の定め方があることになります。このように、どの区間を終わらせるかの組み合わせは独立なのでその積をとることにより、答えがわかります。一つ注意しなければいけないのは数列を全て見終わった時、全ての区間が閉じていなければいけないということです(BBBWなどがダメ)。以下のコードのようにcnt==0を確認する必要があります。僕は一回これを忘れてWAをとりました...
mod = 10**9+7
N = int(input())
S = input()
cnt = 0
ans = 1
for i in range(N*2):
if S[i]=='W':
if cnt%2 == 0:
ans*=cnt
ans%=mod
cnt-=1
else:
cnt+=1
else:
if cnt%2 == 0:
cnt+=1
else:
ans*=cnt
ans%=mod
cnt-=1
if cnt==0:
for i in range(1, N+1):
ans*=i
ans%=mod
print(ans)
else:
print(0)
ところで組み合わせが莫大になるので、modをとる問題は、逐一modを取っておかないと、TLEで死にます。死にました。反省。
もう少し早く解けるべきでしたね。
D
構成の問題なので天才すれば解けるかなぁなどと色々考えてみましたが、わからず。
以下解説を参考に書きました。
この問題で重要となるのは以下の事実です。
各レベルの通路に関して、
「任意の閉路の長さが偶数」=「奇閉路が存在しない」＝「グラフが二部グラフである」
二部グラフとは、二色で、隣接する辺を塗り分けられるグラフのことです。
ここで、各頂点に関してその各レベルに関する色の塗り方を考えます。もし、全てのレベルに関して同じ塗り方をするような頂点が2つ存在するとするとそれらを結ぶ頂点がどのレベルであっても上の条件を満たさないので矛盾します。よって全ての頂点の塗り分け方は異なります。ここで、色を0, 1と翻訳してみると、それぞれの頂点について、その塗り分け方は二進法表示のようにみることができるので、k-levelまでで塗り分けられる頂点数は2^kであることがわかります。グラフの構成についてですが、上の考察を踏まえれば、各頂点に0~2^k-1の番号を振り、任意の二頂点について、一方のみが１であるようなビットの桁をレベルとする通路を、その頂点間にはれば良いことがわかります。
N = int(input())
for i in range(N-1):
print(*[(i^j).bit_length() for j in range(i+1, N)])
考察さえできれば実装は簡単すぎますね。まさかの３行です。bit_length()は二進数で何桁かを意味します。
あと、解説動画はわかりやすいですね。pdf何回読んでもわからなかったのが一発で理解できました。やっぱり図は重要。
メモ
二部グラフ、bit_length、端から決まる、逐一mod