問題概要 長さN,M( 解法 全探索。

問題概要 長さN( 解法 独立な問題をN個解く。各点での最適解は全部まとめるかペナルティを得ない範囲で可能な限り詰め込むかの2択なので小さい方を選べばよい。

問題概要 2次元格子上にn( 解法 とりあえず座標圧縮しておく。y座標の小さい点から順に処理をしていく。数え方としては、蓋をするときにまとめてカウントする感じ。区間に数字を足し込む操作があるのでBITを使って頑張る。

問題概要 解法 力がfのときに脱出までかかる日数の期待値をO(F*N)のDPで計算する。

問題概要 重み付き区間がN(区間を選んで重みの和を最大化する問題。 解法 隣同士5離れているとかは全ての区間で右端を5伸ばせば良い。後は座標圧縮して重み付き区間スケジューリングに落とす。 コード略。

問題概要 1~N(N 解法 max-heapに区間を突っ込んでいけば良い。ただし、heap内の区間を削除したりすることがある。pairing heapなどのheapを使ってもよいが、ポインタを利用して直接中身をいじることでも対応できる。

問題概要 頂点数V( 解法 適当に根を決め打ちしてDFSなどで各部分有向木について向きが逆になっている辺の個数などを求めておく。 この情報があると、各頂点について根に選んだとき入れ替えなければならない辺の本数を求めることができる。 図の青で囲んだ部…

問題概要 AからK文字のアルファベットを使用した長さN( 解法 多分貪欲でも行けるはず。何だけどコンテスト中はDPに走った。dp[i][j]={i-1文字目がjであるときのそれまでの最適値}とすればよい。なぜか愚直なDPの計算量O(N*K)だと勘違いして、書いてる途中でO…

結果。 C,Dを解くのに時間がかかってしまったのと、Eで賢い実装方法を思いつかなかったのがよくない。最初に良くない実装方法を思いついてしまったときの修正能力が低いというのは前から気づいている問題点なんだけど、一度解ける解法が見えてしまうと中々そ…

問題概要 1~N(N 解法 BITを使う典型問題。

問題概要 長さN(区間[l, r]を右から走査していったとき最初に2回出現する数を答える。どれも1回しか現れないなら指摘する。 解法 各iについて、自分より左側で最も近くに現れるindexを持っておく。後は区間内でRMQして最大のindexを取り出し、それが区間内に…

結果。 ICPC現役勢と組んで出場。6/10完。問題そのものは結構好きなんだけど、入力の読み取りが面倒だったり、解釈のしようがない入力がデータに含まれたりしていたのが個人的には苦手だった。

問題概要 分かりにくいけど、サイズ2以上の強連結成分の個数を求める問題。 解法 実際に強連結成分分解する。

問題概要 N*N(N 解法 各点の頂点に流量1,コスト-X[i][j]と流量INF,コスト0の制限を付けて自然に有向グラフをつくり、左上から右下へ流量Kの最小費用流を求めればよい。辺の使用量が一定なので負のコストも簡単に解消できる。

問題概要 W*H(黒か黒->白になっているものをいう。 解法 除原理で重複を排除する。 左が白で右が黒で白の個数が行番号について単調非減少であるようなものは簡単にできて、同様のものが4つ計算できる。その部分は簡単なDP。 で、重複を排除する。全部白や全…

問題概要 数列Xがある。一つだけ-1が入っていてそれ以外は非負整数が入っている。今、0がたくさんつまったスタックがある。-1を適当な非負整数に置き換える。数列を先頭から見ていったとき、0ならトップの二つを和で置き換え、それ以外ならその値を直接プッ…

問題概要 長さN(=0, A[i] = (A[i-1]+A[i+1])/2 - 1 (i in (1,N))となる。A[N]のとりうる最小値を求める問題。 解法 最小値はA[N]について単調なので答について二分探索する。答を決めたらそれ以外の値は連立一次方程式を解くことで求めることができる。

問題概要 問題文がかなり不親切なので適当に補完してまとめるとこんな感じ。 N個の山があるNimがある。同時に1~M個まで山を選んで石を1~K個まで自由に取り除くことができる。最後に取った方が勝ち(=有効手が選べない方の負け)。どちらが勝つか判定する問題。…

問題概要 3つの文字列がある。全ての文字列を部分文字列に含むような最小の文字列の長さを求める問題。文字列長 解法 まず他の文字列に含まれる文字列は消す。その後、Z-algorithmでA-B, B-Cについてlongest prefixを求め、その分をA+B+Cから引く。順番につ…

問題概要 X=0, Y=1が初期状態である。今、X:=X+YかY:=X+Yという操作を繰り返す。ただし初手はX:=X+Y。今、N( 解法 TwoRegisters。によく似た問題。互除法っぽく計算する。長さが丁度Nになるかは、もう一方のレジスタの値がどうなってるか全探索する。このと…

問題概要 平面上にN( 解法 一つの点を置くことによって3つ以上の連結成分をつなげることはできないので、追加前の連結成分の個数を数えるだけでよい。

問題概要 bool演算を考える。ビット演算で定義されたm変数関数f(x1,...,xm)がある。n個の変数X1,..,XN(2 解法 まず、f(0,0,...,0)とf(1,1,...,1)の値が異なるなら当然YESになる。 今、fが恒真(or恒偽)関数だとする。この場合は当然NOになる。そうでないとき…

結果。 1完。数学っぽいBを無視してCをやっていたけど結果的に戦略としては失敗だった。でも、代わりに取り組んでいたC問題は面白かったし方針もそんな悪いわけじゃないのでまあよかった。

問題概要 長さn( 解法 All nearest smaller valuesという有名問題。

問題概要 W*H( 考えたこと 30か。さすがに半分全列挙はないし5~6乗でもいいよ、ということなんだろう。 最も愚直に(累積和使う程度はやるけど)やるとn^8か。係数小さいとは言えこれは無理。 二つの矩形を選ぶのはもう少し分離したいしできそうだなあ。 どこ…

問題概要 赤、青、緑のボールがそれぞれR,G,B( 考えたこと (少し問題の解釈を間違えてサンプルが合わずに混乱していた) ボールの置き方に自由度がほとんどないことは分かる。 とりあえず1個の三角形を作るのに各色がそれぞれいくつ必要か求めよう。 N^2だか…

結果。 久しぶりに2完。撃墜でも稼げて2度目の5位。撃墜云々は運だとしても、確実に通せるように十分チェックできていたのでよかった。システムテスト待ちの間の安心感が違う。mediumはバグ生みにくい方向で書けたのでよい。easyがちょっと場合分け多めにな…

問題概要 頂点数V( 解法 最大次数2以下と聞いた瞬間に線か環になることに気づくので、後は奇数長の閉路の個数+(残りの点数)%2が答になる。

問題概要 六角形のタイルを敷き詰めて六角形を作る。このとき各辺は向かいの辺と長さが等しい。その長さa,b,cが与えられるのでタイルの個数を求める問題。 解法 図をじっと眺める。b*cの部分を取り除くと厚さ(a-1)の層が残る。

問題概要 K( 解法 digital rootはmod (K-1)で考えればよい(0に注意)。後はmapに累積和を詰め込みながらカウントすればよい。B=0やB=K-1のときにdigital rootが0の場合とK-1の場合をちゃんと区別するようにする。