NJPC2017
参加しました
ABCの3完でした、3時間は長かった
公式の解説
解説 - Google ドライブ
A - 入力フォーム
A: 入力フォーム - NJPC2017 | AtCoder
問題概要
入力された文字列Sの先頭からL文字目までを出力せよ
制約
- 1 <= L, len(S) <= 10^5
- L は整数
- S は英小文字のみからなる
B - 格子グラフ
問題概要
H行W列の格子点があり、各点の上下左右との点の間は辺で結ばれています
これらの全ての辺に色を塗りたいです
しかし、N個の格子点には×印がついていて、その点に接続する辺には色を塗ってはいけません
このとき何本の辺に色を塗ることができるでしょうか。
制約
- 1 <= H, W <= 10^5
- 0 <= N <= 10^3
感想
まず全ての辺の本数が何本あるか? ということですがこれは
(W - 1) * H + (H - 1) * W
と求めることができます。この全体の本数から×についてる辺の本数を引いていけば答えが求まります。
基本的には×の周りの4本を引いていくんですが、
- ×が上の辺にある
- ×が下の辺にある
- ×が左の辺にある
- ×が右の辺にある
といったケースに当てはまる場合、全体から引く本数が1本ずつ少なくなります。
さらに重複カウントがあるといけないので
- ×の左が×である
- ×の上が×である
これらのケースに当てはまる場合も、さらに引く本数が1本ずつ少なくしておけば重複カウントすることなく正しく引く本数を求めることができます。
考え方はこんな感じで、後は全ての×について調べていけばオッケーです。
……なんですが、「各頂点が×かどうか」を保持するデータを素朴に保持しようとするとH行W列の配列が必要になるんですよね。
これって最大だと10^10の配列になるのでそもそもこんな配列作ってる時点で時間的に無理です。
っていうかそもそもメモリ的に無理なんですかね、あんまり良く分からないですけど……
それでどうしようかなーと悩んでグダグダやってて、よく分からなかったので飛ばしました。
最終的には×を集合にたくわえて、左、上の頂点がその集合に属しているかどうかで判定をすることにしました。
Pythonの集合がどうやって実装されてるか、というか一般に集合ってどうやって実装されるものなのかよく知らないんですけど、要素にあるかどうかを判定するのは何か高速にできるんで多分大丈夫です。
なので感覚的にはO(N)です、もうちょっと悪くてもO(Nlog(N))ぐらいだと思います。
実際に書いたコード
H, W, N = map(int, input().split()) batu = set() nuru = (W - 1) * H + (H - 1) * W for i in range(N): r, c = map(int, input().split()) batu.add((r, c)) for r, c in batu: hen = 4 if r - 1 < 1: hen -= 1 if r + 1 > H: hen -= 1 if c - 1 < 1: hen -= 1 if c + 1 > W: hen -= 1 if (r - 1, c) in batu: hen -= 1 if (r, c - 1) in batu: hen -= 1 nuru -= hen assert nuru >= 0 print(nuru)
最初 if r - 1 < 1 or r + 1 > H みたいな場合分けでやってたんですが、これだと行が一つしかない場合2本減らさなきゃいけないのに1本しか減らしてくれないっていう現象が起きますね。
例にちょうどそういう例があったんで気づくことができてよかったです。
assert入れてるのはマイナスになったときWAじゃなくてREが出るようにするためです。
いっぱいif書いてるとこは
for r, c in batu: hen = 4 hen -= (r - 1 < 1) + (r + 1 > H) hen -= (c - 1 < 1) + (c + 1 > W) hen -= (r - 1, c) in batu hen -= (r, c - 1) in batu
みたいな書き方もできるなあって今思いました。でも分かりにくいので微妙ですね。
それでどうやってやるのが正攻法なんだろう? と思って解説を見てみました。
やっぱりH*Wの配列を用意するのは無理みたいです。C++でやればできるのかと思って変な気を起こさなくてよかった。
考え方としては一旦重複カウントとか気にせずにまずは各×頂点の周りの辺の数を全体から引く。
次に×頂点の全ての2つの組合せについて、それらが隣り合っていたら同じ辺を2回引いていたことになるので+1してつじつまを合わせる。
って感じでやればいいって書いてました。
この方法だとO(N^2)でN <= 10^3なので十分間に合いますね。
というわけで想定解も書いてみました
組合せにはitertoolsのcombinationsを使用しました
隣り合ってる判定があんまりスッキリ書けてないですが……
from itertools import combinations def tonari(batu1, batu2): diff = (abs(batu1[0] - batu2[0]), abs(batu1[1] - batu2[1])) if diff == (0, 1) or diff == (1, 0): return True else: return False H, W, N = map(int, input().split()) batu = set() nuru = (W - 1) * H + (H - 1) * W for i in range(N): r, c = map(int, input().split()) batu.add((r, c)) for r, c in batu: hen = 4 if r - 1 < 1: hen -= 1 if r + 1 > H: hen -= 1 if c - 1 < 1: hen -= 1 if c + 1 > W: hen -= 1 nuru -= hen for batu1, batu2 in combinations(batu, 2): if tonari(batu1, batu2): nuru += 1 else: pass assert nuru >= 0 print(nuru)
C - ハードル走
問題概要
数直線上にN個のハードルが置かれている。各ハードルiの位置はx_iで表され、x_1 < x_2 < ... < x_N となっている。
原点から走り出して、これらのハードルを全て越したい。
あなたは幅Lでジャンプできるが、ジャンプが終わって着地した地点からLの間はジャンプすることができない。
与えられたN, L, x_iに対してそれらのハードルを全て飛び越すことができるかどうか求めよ。
制約
- 入力は全て整数
- 1 <= N <= 10^5
- 1 <= L <= 10^9
- 1 <= x_1 < x_2 < ... < x_N <= 10^9
感想
問題文を読んだ限りでは「ハードルのスレスレに着地するのがよさそうだな」と考える
それで例を見て「まとめて飛べるハードルは全部まとめて飛んだ方がよさそうだな」と考える
これで実はこの問題を解く材料は全て揃っていて、後は前からシミュレートしていけばよい
実際Bより先にCを解いたので「こっちはめんどくさいけどやればできそうだな」と思って取りかかった
まず着地地点をposとすると、[pos, pos + L]間はジャンプ禁止なのでこの間にハードルがあったら無理なのでそこで終了。
この条件をクリアしたら、「どこまでまとめて飛べるか?」ということを考える。
これは最初に飛ぶべきハードルから順に見ていって、そこからL未満のハードルをまとめて飛ぶと考えればよい。
まとめて飛ぶハードルの一番後ろの座標をx_jとすると、理想としてはx_jスレスレに着地するのがよい。
なので、もしx_j - L がジャンプ禁止区間でなければ、x_j - L で飛んでx_jに着地する。
しかし、x_j - Lがジャンプ禁止区間に含まれていたらどうすればよいか?
これはジャンプ禁止区間が解けた瞬間にすぐジャンプするべきだということが分かる。
なのでpos + Lで飛んでpos + 2Lに着地する、と考えればよい。
こういうことを繰り返していって、全部ハードルを飛び越せたらOKである。
ただし、スタートだけちょっと例外なのでそこは場合分けで対処する。
って感じでしょうか。整数座標でなく、任意の点で飛べるってのが厄介そうな感じですがジャンプすべき点はどの場合も整数座標ギリギリなので、まあ整数のとこで飛ぶと考えて問題無いですね。
計算量は前から素朴に見ていくだけなのでO(N)で終わります。
不等号に=が入るか入らないかみたいなのをよく考えないとめんどくさくなりそうな感じです。
実際に書いたコード
Xは0-originになってます
import sys N, L = map(int, input().split()) X = [] for i in range(N): X.append(int(input())) i = 0 pos = 0 while i < N: if i > 0 and pos + L >= X[i]: print('NO') sys.exit(0) j = i while j < N - 1 and X[j + 1] - X[i] < L: j += 1 if i == 0: if X[j] - L < 0: pos = L else: pos = X[j] elif pos + L > X[j] - L: pos = pos + 2*L else: pos = X[j] i = j + 1 print('YES')
今見ると
elif pos + L > X[j] - L:
のところは
elif pos + L >= X[j] - L:
とすべきでしたが結局計算結果は一緒になるので事なきを得ています。
よく考えると初期値をpos = -Lにして、仮想的に-Lで着地したことにすればスタートの場合分けが要らなくなりますね。
i = 0 pos = -L while i < N: if pos + L >= X[i]: print('NO') sys.exit(0) j = i while j < N - 1 and X[j + 1] - X[i] < L: j += 1 if pos + L > X[j] - L: pos = pos + 2*L else: pos = X[j] i = j + 1 print('YES')
解説を見ると、上のような考え方でだいたい合ってるっぽいです。
厳密にいうと「まとめて飛べるとこは飛んだ方がいい」ではなく「まとめて飛ばなければならない」でした。
部分点解法はどんなのか見てみたら、各座標ごとに「ここで飛べる状態になっているとき、この先の全てのハードルを飛び越せるか?」というブール変数を格納する配列を作って、後ろからDPしていくみたいです。
DPはあまり慣れていないのですが、こういう風にも書けるんですね。今回は部分点解法のほうが難しいような気もしますが、どうなんでしょう。
この方法だと計算量がO(N^2)になって部分点は取れるが満点は取れないコードになるようです。
あまり綺麗に書けてないですが一応部分点解法も書いたので載せておきます。Pythonだから結構ギリギリでしたが……
N, L = map(int, input().split()) X = [] for i in range(N): X.append(int(input())) assert 1 <= N <= 2000 assert 1 <= L <= 2000 assert 1 <= X[-1] <= 2000 MAX_ = X[-1] f = [0] * (MAX_+ 1) j = 0 # 区間[0, i]にハードルが何個あるかという累積和を求めておく for i in range(1, MAX_ + 1): if j == N: f[i] = f[i - 1] elif i == X[j]: f[i] = f[i - 1] + 1 j += 1 else: f[i] = f[i - 1] dp = [False] * (MAX_ + 1) for i in range(MAX_, 0 - 1, -1): if i >= X[-1]: dp[i] = True else: for j in range(i, MAX_ + 1): cond1 = (f[j] - f[i]) == 0 and dp[j] kinsi_r = min(MAX_, j + 2*L) kinsi_l = min(MAX_, j + L) cond2 = (f[j] - f[i]) == 0 \ and (f[kinsi_r] - f[kinsi_l] == 0)\ and dp[kinsi_r] if cond1 or cond2: dp[i] = True break ans = 'YES' if dp[0] else 'NO' print(ans)
D - NMパズル
問題概要
N行M列のマス目がある、そこに1,2,...,NMが書かれたNM枚のカードを1枚ずつ置く。
このとき、(各行の転倒数の総和)+(各列の転倒数の総和)がスコアになる。
このとき、ちょうどスコアがKになるカードの置き方を一つ示せ。
転倒数の定義
数列[A_1, A_2, ..., A_N]の転倒数とは、i < j かつ A_i > A_j となる組(i, j)の個数のことである。
制約
- 1 <= N, M <= 100
- 0 <= K <= NM(M-1)/2 + MN(N-1)/2
- スコアKとなるカードの配置は必ず存在する
感想
難しそうだな~、そういえば螺旋本の転倒数の問題飛ばしたなあ、と思いながら他の問題もチラチラ見てみたんですが他も解けなさそうだったのでこの問題に注力することにしました。
結局制限時間内には解けませんでしたが、何とか自力で解くことができました。
どうやって考えたかの経緯を全て説明するのは難しいので天下り式になってしまいます、申し訳ありません。
まずはとっつきやすくするため1次元に落して考えてみました。
たとえば1,2,3,4,5という5枚のカードがあったとしたら
1,2,3,4,5
は転倒数0で、こっから1増やすには1と2を入れ替えればいいです
2,1,3,4,5
さらに1増やすには今度は1と3を入れ替えます、これを繰り返すと
2,3,1,4,5
2,3,4,1,5
2,3,4,5,1
となり、転倒数4まで表現できました。以下
3,2,4,5,1
3,4,2,5,1
3,4,5,2,1
4,3,5,2,1
4,5,3,2,1
5,4,3,2,1
と転倒数10まで表現でき、明らかにこれが最大です。
一般に1,2,...,Mの数列の並び替えで表現できる転倒数は0 ~ M(M - 1)/2 になります。
これを踏まえて、N = 3, M = 4 のケースを考えてみます。
まず転倒数0になる並べ方は
0:
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
です、こっから1ずつ増やすなら列の大小関係を変えずに、上の例のように1番上の行だけ並び替えていくのが簡単でしょう。
この方法でM - 1まで表現します。
1:
2 | 1 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
2:
2 | 3 | 1 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
3:
2 | 3 | 4 | 1 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
それでM - 1まで表現したら、1行目の並びを元に戻して、2行目と入れ替えます。
すると各列で転倒数が+1されるので全体の転倒数はMになります。繰り上がりみたいなことをするんですね。
4:
5 | 6 | 7 | 8 |
1 | 2 | 3 | 4 |
9 | 10 | 11 | 12 |
それでまた+M - 1までは1行目の要素の入れ替えで表現して、+Mするときは行の入れ替えを使って、みたいなことを繰り返していくと
12:
9 | 10 | 11 | 12 |
5 | 6 | 7 | 8 |
1 | 2 | 3 | 4 |
ここまでで一般に転倒数 MN(N - 1)/2 まで表現できます。
Kの上限がMN(N - 1)/2ならこれでいいんですけど、K <= NM(M-1)/2 + MN(N-1)/2なので、後NM(M-1)/2をどうするかという問題があります。
以下、K >= MN(N - 1)/2と仮定し、L = K - MN(N - 1)/2と置きます。
MN(N - 1)/2 の型を基本形とします。
基本形のある1行を逆向きにすれば+M(M - 1)/2されるので、L // (M(M - 1)/2)で反転させるべき行の数が分かります。
後はL % (M(M - 1)/2)は基本形の1行目の要素の入れ替えで何とかすればオッケーです。
上の例でいうと、27を作りたいなら
27 - 12 = 15, 15 // 6 = 2, 15 % 6 = 3
なので、下2行をリバースして、後は一番上の行を転倒数3にするようにすればいいので
27:
10 | 11 | 12 | 9 |
8 | 7 | 6 | 5 |
4 | 3 | 2 | 1 |
とすれば確かに作れています。
全部反転させれば各行の転倒数の総和はNM(M-1)/2になるので、これで何とかできましたね。
……っていうアイデアの素を思いついたのが終了10分前とかでそっからちゃんと形に出来なくて終わりました。
というかこのブログに書く事で初めてまとまりました。
計算量はO(NM)です、N,Mが小さいのでこの方法で何とかなるみたいです。
1-originと0-originで混乱したり、割る数を間違えたり、そもそも入れ替えのアルゴリズムがちゃんとできてなかったりでめちゃくちゃでしたが何とか形にはなりました。
長くて見づらいですが一応載せておきます。
N, M, K = map(int, input().split()) kyokai = M * N * (N - 1) // 2 if K <= kyokai: C = [[j * M + i + 1 for i in range(M)] for j in range(N)] row_c = K // M col_c = K % M cnt = 0 for i in range(N): for j in range(N - 1 - i): if cnt == row_c: break C[j], C[j + 1] = C[j + 1], C[j] cnt += 1 cnt = 0 for i in range(M): for j in range(M - 1 - i): if cnt == col_c: break C[0][j], C[0][j + 1] = C[0][j + 1], C[0][j] cnt += 1 for i in range(N): print(*C[i]) else: K -= M * N * (N - 1) // 2 rev_row = K // (M * (M - 1) // 2) rev_col = K % (M * (M - 1) // 2) C = [] for i in range(N - 1, rev_row - 1, -1): C.append([i * M + j + 1 for j in range(M)]) for i in range(rev_row - 1, 0 - 1, -1): C.append([(i + 1) * M - j for j in range(M)]) cnt = 0 for i in range(M): for j in range(M - 1 - i): if cnt == rev_col: break C[0][j], C[0][j + 1] = C[0][j + 1], C[0][j] cnt += 1 for i in range(N): print(*C[i])
解説見たら表現できる限界を超えたときの処理がちょっと違いました。
最小値から増やしていく、ではなく最大値から減らしていくって考えるといいみたいです。
そっちもコーディングしてみようかと思ってますが、そろそろ疲れたし長いので一旦切ります。