問題概要 長さN( 考えたこと 部分和なので累積和が考えやすい。 サイクリックになっているのは長さを2倍にした数列を考えてやれば良い。 長さ2倍の数列で累積和を考えてやれば、長さNの範囲で累積和の最小値が直前の累積和以上になっていればOKだと判定でき…

問題概要 変数をN( 考えたこと 変数が5つしかないんだから5!全部試せばいい。 構文解析の部分は2項演算子が括弧でまとまっているので易しい。 := '(' ')' | 、 := | op とか？ 書く。動かない。このBNF間違ってるじゃん。 := '(' ')' | | op が正しい。 書き…

問題概要 テニスで、ポイントをとる確率pが与えられる。gameに勝つ確率、setに勝つ確率、matchに勝つ確率をそれぞれ求める問題。 考えたこと 問題文長いけどどうやら一般的なテニスのルールが書いてあるだけらしい。 なのでWikipediaで調べる。 デュースとか…

問題概要 N( 考えたこと 最大値の最小化といえば二分探索が思い浮かぶ。 実際それで行けそう。判定は切り上げの割り算をすればいい。オーバーフローだけに気をつける。

結果。 10問中6問解けた。自分が解けた問題に関してはそこまで難しいということもなく自然な発想で解ける問題が多かったように思う。 コンテスト開始後問題をたくさん開き、問題文が短いのに目を通す。その間にFirst Acceptが出たのでその問題を見に行く。 D…

結果。 UVaを中心としたセット。CodeForces Div1 1000ptくらいの難易度。P9は既に解いててP11は解く気がない。

結果。 LiveArchive, UVa, SGUからの出題。CodeForces Div1 1000位の難易度。もっと簡単なのもある。

結果。 UVaの割と易しめなセット。

問題概要 W*H(W,H 解法 座標を2倍にすると単純なFlood Fillに落ちる。切る順番は考えなくてよい。

問題概要 集合Sが与えられる。要素数N( 考えたこと 一目は半分全列挙。 a*b+cの組み合わせを全部列挙して、d*(e+f), d!=0の組み合わせも列挙して、掛け合わせて足せば良い。 mapを使って実装するもTLE。 equal_range + distanceを使って実装しなおしたらギリ…

問題概要 長さN(区間で両端の値が等しくなるような部分列がいくつとれるか求める問題。ただし端点しか交わってはならない。 考えたこと サンプルが分からない。 ああ端点は交わっていいのか。納得。 貪欲で行けそう。区間スケジューリングみたいな感じで。 …

問題概要 二人用のゲームがある。1*N( 考えたこと 二つの問題を解かなければならないのか。 どちらもプレイヤーの間隔を状態にしてDPっぽく解くんだろう、きっと。 前者の問題について考えてみると、勝つ確率はΣ(1.0 - dp[cur-i])の計算ができれば行ける。 …

問題概要 ノード数V( 考えたこと どこかで、というかCodeForcesで似た問題を解いた記憶がある。 普通のEuler tourだと2*V-2が総経路長になるが、戻ってくる必要がないのでdist(start, goal)の分だけ差っ引くことができる。 なのでstart, goalを最大化してや…

問題概要 長さL( 考えたこと とりあえずuniqueしても良さそうなのでuniqueして考える。 要するに最長回文？ 本当に最長回文だった。Manacherで通した。

問題概要 長さL( 考えたこと 桁数と直前の値を状態としてDP? いやいや、値が小さいんだから全探索で行ける。comb(20, 9)も大した大きさではないし間に合うはず。 分割を全部試した後は単純な組み合わせの問題に落ちるはず。 最初はTLEしてもいいからmap使っ…

結果。 どれも適度に難しかった。 とりあえずGがBITとかRMQとか使えば解けそうだったので飛び込んだら答えが合わない。小さいケースに関しては解が出せるので小さいところを出力して眺めていたら嘘仮定が思いついたのでその仮定の元で解いたらACが貰えた。実…

問題概要 01の値が入ったボード(H,W 解法 何はともあれ累積和を計算しておく。上端、下端、左端について全探索する。右端についても全探索したらさすがにTLEするので、右端については単調性を利用して二分探索すれば間に合う。上端と下端を全探索して左端と…

問題概要 N*N(N 解法 縦、横、斜め*2について独立に考える。例えば縦での衝突を考えるとき、列の違うクイーンはまったく関与しない。同じ列のクイーンを集めてソートしてやると、端のクイーンだけは1つのクイーンの範囲に含まれ、それ以外は2つのクイーンに…

問題概要 ノード数V( 解法 頂点を潰した後は木になるので距離は簡単に求められる。問題は環を潰す部分。次数1の頂点を見つけて減らしていけば残ったのが環になる。

問題概要 男がN(4 解法 もちろん男が何人選ばれるか全通り試せば(前処理を除いて)O(N)で解けるんだけど、なぜか本番中は別の解き方で解いた。選んだ男どもと女どもをそれぞれ番号でソートする。4人目の男と1人目の女がだれになるかを全通り試す。

問題概要 配列X(|X|=:N 解法 X[i]の値の分布を調べておくだけ。0は例外処理する。

問題概要 文字列が与えられる。全てが大文字、または先頭以外の全てが大文字なら大文字と小文字を入れ替えて出力する。 解法 愚直にチェックしても間に合う。1文字目は無視してよいことに気づけばちょっとだけコーディング量が減る。入力が1文字で小文字のと…

結果。 どの問題も方針は見えやすかったと思う。実装や読解に時間をとられはしたけどこれはまあ仕方がない。残り時間ギリギリで6問目を通したけど計算量が結構きわどかった。残り時間がもっと余裕あればカスタムテストで最大ケース試す所だけど。5問目は色々…

問題概要 ノード数V( 解法 まずWarshall-Floydで最短路を求めておく。次に2点を固定する。各辺e=(v,u)に対して、d(start, v) + 1 + d(u, goal) = d(start, goal)ならそれは最短路に含まれると言える。これを利用して数え上げるだけ。

問題概要 牛がN( 解法 愚直にシミュレーションする。LCM(1..10)=2520日経っても取り除かれなかったらもう終了してよい。どの辺にグラフの要素があるのかは謎。

問題概要 N( 解法 各ソフトが今バグを含んでいるかどうかを状態にしてビットDP。バッチが適用できるか、バッチ適用後にどういう状態になるかは適切に前処理をして高速に判定できるようにしておく。計算量はちょっとギリギリ。

問題概要 重み付き有向グラフが与えられる。特殊な状況下ではワープが使える。ワープの使える回数には上限がある。最短路を求める問題。 解法 現在位置、ワープを使った回数を組にしてDijkstraする。

問題概要 ノード数V( 解法 最小費用流

問題概要 コストがdoubleとなる最小重み最大2部マッチングを求める問題。 解法 最小費用流。

問題概要 H*W(H,W 解法 頂点に容量1を持たせた最大流を流せば良い。