読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

Indeedなう 予選B 全部

AtCoder

リアルタイムで解いた問題です。
開始時間が15分遅れていなければ20位ぐらい上がっていたかも。
何はともあれ全完で一安心。

- A問題「高橋君とマンハッタン」

(http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_1)

問題概要:
京都みたいに格子状に道路が広がる高橋君が住んでいます。
交差点を座標で表したとき、ある交差点(x_1,y_1)から(x_2,y_2)まで移動するのに交差点をいくつ経由しますか。
スタート地点とゴール地点も経由する交差点に含みます。

解法:
タイトルがヒントだということに解いてから気づきました。
マンハッタン距離と進行方向にある交差点の個数は等しいので、その値に1を足してやれば解となります。

ソースコード:
https://indeednow-qualb.contest.atcoder.jp/submissions/360638


- B問題「高橋君と文字列操作」

(http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_2)

問題概要:
前回も文字列系統の問題があったのでくることは予想していました。
ある文字sが与えられます。sの末尾の1文字を先頭に追加、末尾1文字削除、という動作を何回繰り返せばtに一致するかという問題です。

解法:
stringのsubstrを使ってそのまま文字列変換、比較を繰り返しました。
sを二つ繋げてKMP法使ってパターンマッチングするほうが賢かったですね。本番中は気づきませんでした。

ソースコード:
https://indeednow-qualb.contest.atcoder.jp/submissions/360907


- C問題「木」

(http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_3)

問題概要:
木が与えられ、どのような順で木を辿っていけば訪問順が辞書順最小になるかという問題です。

解法:
1の頂点をスタート地点にするのがどう考えても最小です。
次に訪問するのは1からいける範囲の最小の頂点です。
とすると現在行ける未訪問の頂点のうち最小の頂点を選べば良いことになります。
グラフの最短距離を求めるダイクストラ法と動作が似ていますね。
ダイクストラ法と同様に隣接関係を隣接リストで実現し、未訪問の頂点をヒープで管理すればO(N\log N)で実現可能です。

ソースコード:
https://indeednow-qualb.contest.atcoder.jp/submissions/361271
関数名がdyjkstraになっていますが動作が似ているだけでダイクストラ法そのものではないです。

- D問題「高橋君と数列」

(http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4)

問題概要:
1からCまでの数字が現れうる長さNの数列a_1,a_2,,,,a_Nが与えられます。
1 \le i \le Cを満たす任意のiについて、数列中のiを含む区間の個数を答えよ。

解法:
連続部分数列の右端について考えます。
dp(i,r)をrを右端とするiを含む部分列の個数、と定義します。
1.a_r=iのとき、すなわち右端がiなのでr以下のどんな左端lをとってもiを含む部分列となります。したがってdp(i,r)=r。
2.a_r \neq iのとき、r-1を右端とする部分列にa_rをくっつけたもののみがiを含む部分列です。したがってdp(i,r)=dp(i,r-1)
この操作を行って任意のiについて\sum_{j=1}^N dp(i,j)を求めれば解が求められるのですが。
1 \le N,C \le 10^5なのでこの解法だとO(NC)となりTLEとなります。
ここで、dp(i,r)をdp(i)に変更し考え直してみます。
dp(i)が更新されるのはa_r=iのときのみです。
このとき、更新前のdp(i)には前回更新したときのr_{prev}が保存されています。
r_{prev} \le k < rを満たすdp(i,k)の値は全てr_{prev}で、その総和は(r-r_{prev})*r_{prev}となるので、
別の総和保存用配列を用意しておき、値が更新されたときに値を加算しましょう。
こうするとO(N)で計算でき、最後に全てのiについて最終的な値を求めてやれば良いので、計算量はO(N+C)となります。

ソースコード:
https://indeednow-qualb.contest.atcoder.jp/submissions/361601
rの開始位置を1にするのを忘れないようにしましょう。