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

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

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

ABC #021

ABC

ちょっと前だけど実際に参加したコンテストです。
modについてCodeChefでたくさん戯れたおかげで今までで最速の全完出せました。
しかしちょっともたついた部分もあったので反省です。

- A問題「足し算」

(http://abc021.contest.atcoder.jp/tasks/abc021_a)

問題概要:
1,2,4,8を好きなだけ組み合わせてNを作る問題です。問題文に惑わされてはいけない(戒め

解法:
N回1を出力するだけです。なのですが当人は問題文に惑わされてbit演算を使って出力を行っています。

ソースコード:
https://abc021.contest.atcoder.jp/submissions/383375



- B問題「嘘つきの高橋くん」

(http://abc021.contest.atcoder.jp/tasks/abc021_b)

問題概要:
高橋君がここに来るまでに通ってきた町の番号を言います。
高橋君は最短路を通ってきたはずなので通ってきた町の中にスタート、ゴールは入りません。また、同じ町を二つ以上通ることもありません。
高橋君が本当に最短路を通ってきているかどうか答えよ。という問題です。

解法:
存在する町の数分だけフラグを用意します。
スタートとゴールのフラグをあらかじめ立てておきます。
あとはパスを辿って通った町のフラグを立てていき、フラグが既に立っているパスに到達した場合ループが存在する証拠なのでNOを出力します。

ソースコード:
https://abc021.contest.atcoder.jp/submissions/383502


- C問題「正直者の高橋くん」

(http://abc021.contest.atcoder.jp/tasks/abc021_c)

問題概要:
今度の高橋君は正直者です。
高橋君は最短路を通ってきたのですが王国には町から町へ移動する最短経路が複数ある場合があります。考えられる最短経路の個数を答えよという問題です。

解法:
dpのような隣接行列ダイクストラのような謎解法です。
道路のコストは全て等しいので1に統一しておきます。
dp(c,j)をc回の移動でjの町にたどり着く経路の数とします。
二つの町i,jをつなぐ道路が存在するときadj(i,j)=1、存在しないときadj(i,j)=0とすると
dp(c,j)= \sum_{i=0}^{N-1} adj(i,j)*dp(c-1,i)
となります。
初期値はdp(0,スタート)=1とすればよいです。
これをc=Nまで求めた後、dp(k,ゴール) > 0でkが最小のものを選べばそれが解になります。
計算量はO(N^3)です。

ソースコード:
https://abc021.contest.atcoder.jp/submissions/383896
解法とは少し違いますが上の解法の方が実装楽な気がします。

- D問題「多重ループ」

(http://abc021.contest.atcoder.jp/tasks/abc021_d)

問題概要:
最初の方は読まなくていいです()。
長さがKで1からNの値を持つ数列のうち、単調増加列となるものはいくつあるかという問題です。

解法:
数学Aの教科書を取り出すと、重複を許した組み合わせとかそういうのが出てくると思います。
○をK個用意して、|をN-1個用意してそれをごちゃ混ぜにして順列を作ると、
||○○|○|○みたいな形になると思います。
このとき、1個目の仕切りより左の○は1,
1個目と2個目の仕切りの間の○は2,
2個目と3個目の仕切りの間の○は3,
3個目と4個目の仕切りの間の○は4,
4個目の仕切りより右の○は5とすると、上の例では3345という数列ができあがります。
この組み合わせの数は○|ごちゃ混ぜの順列が(N+K-1)!
○同士の順番は気にしないのでK!で割り、|同士も同様なので(N-1)!で割ります。
このようにして順列の個数が求められます。
http://www.prefield.com/algorithm/math/invmod.html


ソースコード:
https://abc021.contest.atcoder.jp/submissions/384233
この問題を少し難しくした問題にCodeChef April long2015「CSEQ」があります。
CodeChefで苦しんだおかげで難なく解くことができました。