問題概要 SRM 521 500pt: RangeSquaredSubsetsの類題。違いは、正方形の辺の長さが固定。N 考えたこと 辺の長さが固定ならTLEの心配がない。昨日のTLEしたコードが使える。 一応スクラッチから書く。途中4ヶ所コピペがあって後ろめたい気になりながらも無事…

問題概要 R,Gからなる文字列(L 考えたこと 区切りの場所に関して全探索するだけっぽい。 無事通った。一発コンパイルで成功させたかったけどalgorithmをincludeし忘れてた。

問題概要 2次元平面上に点がN( 考えたこと N=40とかO(N^5)か半分全列挙。 あるいは、うまく組めばO(N^4)くらいになるけど手抜きでO(N^5)でもいいよ、みたいなことが多い気がする。 というかこれ返り値64ビットもいらないよね。きっと数え上げで行けるはず。 …

問題概要 ')', '('からなる長さL( 考えたこと 典型っぽい。 ICPC国内予選Bみたいにスタック使うのかな？ まあスタックといっても実際は数をカウントするだけでいいんだけど。 スタックが空の時は')'に対応するのをそれより前につける必要があるから答えをinc…

問題概要 2次元平面で、(1,1)から(r,c)(r,c 考えたこと modの値が妙に小さい。二項係数を求めやすくなったりしてるんだろうか。 しかし二項係数(n,k)って最大でも50なんだから普通に求められるような。 まあいいや。普通に考えると状態は(踏んだ個数、最後に…

問題概要 x, yが与えられる。xとyが2回ずつでてくるような式で、演算子が+,-,*のいずれかで、左結合になっているとき、式を評価した値がvalに等しくなるようなものは何通りあるか求める問題。 考えたこと サイズ小さいので全探索行ける。 でも積を最初に計算…

問題概要 カードがN( 考えたこと (当時はeasyに全部時間をとられていたのでこの問題は初めて見た) 何か一目解けそうな気はするけどどうせ600だし難しいんだろうなあ。 しばらく考えたけど全然分からなかったので小さいケースを全探索で解く。 どうせ巡回置換…

問題概要 芋がn( 考えたこと (当時は解けなかった。これくらい解答がシンプルだと記憶に残りやすい) 4=-1 (5)なので、4のべきとるというのはmod 5での値を1増減させることに対応している。 mod 5 で 1, 3, 4の状態からは0, 2の状態に必ず遷移できる。

問題概要 n( 考えたこと えっ。こんなシンプルなのとりあえずググるでしょう。 数式一発というのは相当無理そう。 多項式で漸化式作れば行けるけど面倒過ぎる。 分割統治とか色々考えたけど賢い方法が思いつかない。 しかたないので多項式で漸化式行こう。 c…

問題概要 長さN( 考えたこと N=8とかどう見ても全探索の雰囲気。 幅優先で行けるけど状態に番号付けるのが面倒くさい。 8!ってそんなに多くないしmapにvectorそのままつっこんで行くか。 書く。無事通った。

問題概要 一列に部屋がつながっていてドアがN( 考えたこと (久しぶりの競技プログラミング。リハビリ気分) (本番は貪欲か何かで解いた気がする) 自分だけが開けた方が色、開けない方が良い色などを選ぶようにすれば簡単にシミュレーションできるような気がす…

問題概要 n( 考えたこと (本番は解けそうだなあと思っていたけど解けなかった。当然当時の「解けそう」は単なる勘違い) 期待値の線形性？ 固定されてるものどうし、片方固定されているもの、両方自由の組み合わせをそれぞれ別個に期待値計算して足し合わせれ…

問題概要 高さの異なるN( 考えたこと 最も高いビルはいつでも見える。 なので最も高いビルがどこに来るか全探索しよう。 最も高いビルの右側と左側で分けて再帰的に処理すれば行けそう。 このとき、右側と左側の計算は同じことをしている。 状態を(ビルがい…

問題概要 2次元格子があって、今原点にいる。縦か横に移るのにW, 斜めに移るのにSのコストがかかる。(X,Y)(X,Y 考えたこと O(1)じゃないと無理っぽい。まさかlogが出てくる訳でもないし、答えに関して二分探索というのもちょっと変だ。 場合分けが出てくるの…

問題概要 文字列A,B(長さ 考えたこと (Bを提出した時点で結構順位が高くて、このsmallを出したら賞金圏内だったので必死になった)。 smallはどう見ても全探索。Aのどの文字を*に対応させるか2^10通り試してやればよい。隣合う*は一つにまとめる。 で、作った…

問題概要 配列Aが与えられる(長さL 考えたこと 何か答えが小数で一瞬嫌な気がしたけど、すぐに最後に0.5*sin(2*PI/K)を掛ければよいことに気づいた。 この手のはどうせソートっぽいことをするはず。掛け算は値の差が大きいほど損するとかそんなの。 とはいえ…

問題概要 X[0]=A( 考えたこと 全部mod Cでやるだけじゃダメなの？ ダメだ。指数の部分はmod Cだと値が変わる。 ということはX[i] mod Cの値だけ持っておいてもダメなのか。 指数の部分もループに入るのでループの長さをLとするとX[i] mod Lの値も覚えておく…

問題概要 映画がN( 考えたこと (当時は手も足もでなかった問題。そもそもmediumは解けなくて当たり前だと思っていた節があるし、純粋に知識も皆無だった。当時の自分はビットDPとか知っていなかった気がする) N=20とかビットDP臭。 これ問題文には小数とか出…

問題概要 n*m(n,m 考えたこと (当時も時間はかかったけど特に問題無く解けてた気がする) 何も埋まってない行は簡単に計算できる。 何かが埋まってる行に関しては、間隔を取り出してやれば簡単に解けそう。 番兵を置いたら少し簡単になるかもしれない。 こう…

問題概要 番号0~N( 考えたこと (本番中何考えたか全然覚えていない。たしかチャレンジフェーズにMLE狙いで落とせずに2失敗位した記憶がある) 問題のサイズとか、性質的に一目DP。 状態を(i番目の街、飛行機を使った回数)と最も素朴にとるとO(K*N^2)。 今のま…

問題概要 いわゆるT9の入力形式と辞書が与えられるので、変換後の文字列を求める問題。 考えたこと (本番中も実装するだけのつまんない問題だと思いながら解いていた記憶がある) 辞書を前処理しておいて後はやるだけに見える。 計算量はどんな方法でやっても…

問題概要 システムテスト終了時の順位とそれぞれ何を解いたかの表が与えられる。各問題の正当な結果の組み合わせが何通りあるか求める問題。ただし、順位は(通った問題の数、-撃墜された問題の数)で辞書順に定める。参加者はN( 考えたこと とりあえずスコア…

問題概要 N( 問題概要 激しくやるだけ。しかしこのセット徹底してるなあ。 愚直にシミュレートしたら通った。

問題概要 easy, medium, hardの得点の最大値([25000, 30000], [45000, 60000], [90000, 110000])が与えられる。また、N( 考えたこと N=20だしビットDP？いや、実際のSRMに合わせてるだけか。 取りあえず得点の総和をMAX_P = 200000とおく。 上の人の総得点で…

問題概要 75分間のSRMがあり、easy, medium, hardの配点([250,300], [450, 600], [900, 1100])と、各問題を解くのに必要な時間が与えられる。問題iをt分で解いたときの得点はpoint[i] - 2^i * tである。あなたは全部で総和がL( 考えたこと 何この問題おもし…

問題概要 1~N( 考えたこと グラフ臭がする。ベルマンフォードは間に合わないし、強連結成分分解？ サイクルは葉の部分にしかできないので特に問題はない。こういうのは夏合宿で見たことある(Alien's Counting)。 DAGに落としてメモ化再帰すれば良さそう。 た…

問題概要 長さ50以下の文字列が2つ与えられる。どちらも一つだけ*を含んでいる。どちらの文字列にもマッチする文字列があればそのうち長さ最小のものを出力する問題。 考えたこと *がついてないところは前と後ろから貪欲に固定させていけば行けそう。 場合分…

こことか蟻本を参考にして、色々実装を試してみた。 RMQ まず、インターフェースをはっきりさせよう。とりあえずD言語で書くけど、そこまで言語依存な書き方はしていないのですぐにC++なりJavaなりに移せるはず。D言語とかコンテストでは大抵使えないし言語…

問題概要 a + b = N( 考えたこと とりあえずsmallは本当に書くだけなのでさっさと書く。 Dに64ビットのpopcntが無かったので真面目に書く。 largeを考えよう。こういうのは大抵桁でDPだ。 でももっと楽に行けそう。片方は111..11になるように仮定して良さそ…

問題概要 N( 考えたこと これはgreedyっぽい。 どれをどれだけ飲むか決めれば、後は消費期限の短いやつから飲んでいけばいいので消費期限でソート？ いやいやそれは動的計画法の考え方だ。もちろん満足度の大きい順にソートすべきだ。 ちょっと落ち着くため…