問題概要 W*Hのマットがあり、その中にN個の円(半径はそれぞれ決まっている)を詰める。中心がマットの中に入っていればよい。円同士は重なってはならない。そのような円の配置方法をひとつ出力せよ。マットの面積は円の面積の総和の5倍以上であり、答えが必…

問題概要 問題文は状況を理解しにくいものになっているので、解答を見て問題を想像してください。

結果。 1/4完。最初サンプルの意味が分からずに1時間くらい消費した時点で心が折れた。2問目は証明なしで貪欲というかシミュレーションっぽいのを書いて、手元でちゃんと出力条件満たしてるのに何で通らないの？また読み間違えたのか？と混乱状態になったけ…

問題概要 A[i] 解法 貪欲に選ぶ。S>=B[i]なiがあればそれをクリアし、なければS>=A[i]なiのうちBが最大のものを選べばよい。heapを使えばN*log Nで解けそうな気もするけどN

問題概要 長さBのパスワードがあって、A文字目まで打ち込んでいる。これまでに打った文字が正しいかどうか確率が与えられるので、最適手順をとったときのパスワードが通るまでの手数の期待値の最小値を求める問題。 解法 期待値DP。状態数A、遷移3つなので素…

結果。 2/3完で通過。問題文長くてだるかった。D言語で参加したけど日本人のD使用者が前回より増えていた。

問題概要 文字列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の値も覚えておく…

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

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

問題概要 カードをある手順にしたがってシャッフルして、最後に特定の位置にあるカードを答える問題。 考えたこと (今回は時間の余裕もあるしD言語を試すことにした) これはよくある問題。終了状態から逆にシミュレーションして最初どこにあったのかを答えれ…

解法 P_DやP_Gが0や100の場合は別に考慮してやる。それ以外のとき、Gに制限が無いので通算勝率の方はいくらでも調整できる。なので今日の勝率だけ考えてやればよい。N>=100のときはD=100とすればいつでも達成可能だし、それ以外のときは全探索してやればよい…

解法 既に正しい数字は動かさない、という仮定(これは正しいらしい)を置くと、完全順列などの知識を用いてO(N^3+T*N)のメモ化解法がすぐに思いつく。これで小さいテストケースをいくつか試すと法則性が見えてくる。以下はメモ化解法のほう(本番で提出したの…

問題概要 長さN( 解法 2つの集合のxorが等しいので、元の数列のxorは0になる。これが可能である条件。またこのとき、どのような分割でもxorは等しくなる。したがって、和の最大値は全体の和から最小値を引いたものとなる。

解法 ただのシミュレーション。vectorをstack代わりに使って書いた。

解法 やるだけ。イベントドリブンでも余裕で間に合う。

keyword swap回数 行列 greedy C++ 概要 行列が与えられる。隣接する行を入れ替えることにより行列を下三角化したい。必要なswapの最小回数を求める問題。ただし下三角化できることは仮定してよい。 swapの回数は貪欲にやれば最小回数になるはず。それが分か…

keyword C++ 概要 同じ長さの数列が2つ与えられる。適当に順序を入れ替えてできる内積の最小値を求める問題。 小さい値の寄与を大きくして、大きい値の寄与を小さくすればいいんだから降順と昇順にしたものの内積をとれば良さそう。本当か？取りあえず書く量…