2018-01-01から1年間の記事一覧
C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder豆一つをnimの山として考えられる。 よって、全ての茶碗についてgrundy数を求め、A[i]回xorを取った物たちをxorすればいい。難しいのはgrundy数を求める方法。 区間 [ i - c[i] , i ) に含まれない最小…
C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoderN人の中からK人が勝つのにかかる回数の期待値が分かれば解ける。 N人の内、k人が勝つ確率をp(N,K)、N人のじゃんけんが終わる回数の期待値をENとして 整理してやって P(N,K)を求めるには、N…
G - Perm Query問題文より、全ては周期40以下の巡回群である。 あるli~riが揃うまでにはそれらの周期の最小公倍数回だけ操作が必要である。 区間の最小公倍数はセグ木で持てる。 また、操作の和も調べられるので持てる。Submission #3879423 - Japan Alumni …
D - 一次元オセロ (1D Othello)kmjpさんの実装を参考にしました Submission #3867975 - パ研合宿コンペティション 2日目解法 白黒を区間として持てばひっくり返すのが楽です。 操作中の区間は高々N+1個であり、消える区間は端であるため、dequeを使えば実装…
A - Taro vs. Jiro解法 Kの制約が大きすぎるので、少ない場合と同じに考えられることが予想できる。 実際に考えてみると、Kが1なら隣にBがあれば勝ち。 次にどんな操作をされても、Bに戻せるため、Kが奇数のときと1の時を同視していいと分かる。 Kが偶数の場…
A - YahooYahooYahoo編集距離DPをいじった感じでやる。 y f o o y 0 a h o odp[i][j] := yahoo[i]までを、s[j]までで作れる最小手数とする まず、yahoo[i]までをs[j-1]までで作れる時、jを消せばs[j]までを作れるため 右に+1で遷移できる また、s[j]において…
A - Irreversible operation いくつか紙に書いてみるべきだった 毎回WWWWBBBBのようになる Submission #3806738 - AtCoder Grand Contest 029 signed main() { string s = sin(); N = s.size(); int now = 0; rep(i, N) { if (s[i] == 'W') { cou += i - now…
E - Tough Journey解法 安いところでたくさん買いたいので、貪欲に考えたくなる。考えると 今いる場所をiとして K以内の距離でiより安く買える地点がいくつかあるなら、その中の最も近い地点jで買ったほうが得なので、jまで行ける程度に買い、jに飛べばいい…
D - サプリメントdp[i] := i個目まで食べる組み合わせとする 最後の日に添字iを食べる組み合わせは i i-1,i i-2,i-1,i i-3,i-2,i-1,i …のように分けられる また、上はdp[i-1],dp[i-2],dp[i-3]… である この時添字i以前で同じでない最長の区間を足し合わせれ…
A - Uncommonxと互いに素なものを数える場合、xの約数について、それらの倍数の個数が全て分かれば 素因数の数をcとして、包除原理でO(2^c * c)で解ける今回a1 ~ an よって包除原理が使える ここで素因数分解したとき、その数は高々6個である よって、O(N * …
H - Median Game解法 中央値は二分探索 いつものDPで後ろから解けば解ける vi A, B, C; int dpa[1001];//+ int dpb[1001];//sum以上 - sum 以下を最小で何個に vi rui; bool calc(int v) { fill(dpa, -LINF); fill(dpb, LINF); dpa[N] = dpb[N] = 0; for (in…
E: すぬけ君の地下鉄旅行 / Snuke's Subway Trip - AtCoder Regular Contest 061 | AtCoder解法 路線別にvectorへもたせ、dfsで繋がっているもの同士を超頂点に接続する 毎回、すでに見た頂点をusedしたいが、fillするとTLEするので最後に見たtypeをもたせれ…
D - Practical Skill Test解法 まず、整数から座標を持ってこれるようにする こうすれば次の行き先へのコストがO(1)でわかる また、L からRまでのコストがわかればいいので、累積和を使いたくなる ゴールはD通りしかなく、それぞれのゴールから少ない数へた…
C - チップ・ストーリー ～白銀編～解法 要は全てが掛け合わされるので、max(p) * max(q) 排反に数えるには、pの最大値がpmの場合のpの組み合わせと、条件を満たすqの組み合わせというのを掛けていけばいい pの最大値がpmになる組み合わせは、pm^10-(pm-1)^1…
E - Union解法 漸化的にやりたい。 iまで操作して、iにある数がjになる場合の数というふうにdpを作れば もともと置いてある数kも一つだけ決めればいいので解ける Submission #3671982 - CODE THANKS FESTIVAL 2018int N, K, M, H, W, Q, cou, sum; vi A, B, …
問題概略 H*Wのグリッドがあり、そこにはお金Pと入場料Fがある。 上以外へ移動できる時、[H][1~W]での最大かねを求めよ H p,f 解法 解説見てもよくわからなかったので、kmjpさんの実装をみて理解しました Submission #2022964 - SoundHound Inc. Programming…
問題概略N人の人をチーム分けしたい。 ただしi番目の人はai人以下のチームに配属しなくてはいけない制約 1 1≤ai≤N解法 一人ひとりについてどのチームに属するか考える事はできない。 oo人以下にしか属せない物の数を数えておけばまとめて考えることが出来る…
No.409 ダイエット - yukicoder 問題概略N日あり、毎日ドーナッツiを食べるか食べないかを選択できる。iを食べるとDi体重が増えるがストレスが0に、食べないと、体重がA減る代わりにストレスが1増え、体重がB*(ストレス)増える。初期体重はW、最終日の最軽は…
問題概略 N個の点がある。R = 10^10^10^10として、半径R内の円無いから無作為に一点を選ぶ際、それぞれの点が一番近い確率を求めよ。制約 2≤N≤100 xi , yi ≤106(1≤i≤N) 与えられる点は全て相異なる解法 それぞれの点が一番近い範囲を書いてみると、凸包上で…
問題概略 木の直径をK以下にしたい。削除するべき頂点の数は最小でいくつか制約 2 1 解法 木には|S|が偶数の時は一つの中心が、奇数の時は2つの中心あり、最大パスがDの時にそれぞれ全体への距離がD/2以下、(D-1)/2以下となる。 最終的な木の中心を決めてや…
D: Robot Arms - AtCoder Regular Contest 103 | AtCoder問題概略 m個の腕があるロボットアームがあり、これらは一つ前の関節からUDLRの方向に曲げることが出来る。 今N個の座標が与えられる。アームの先端がN個全部を指せるような腕の長さと方向の組み合わ…
問題概略 長さNの数列Aと整数Kが与えられる。 以下の操作をQ回行う 連続するK個を選び最小値を取り除く。上の操作で得られた最大値と最小値の差を最小にしたい。制約 1 1 解法 問題をそのまま捉えるとよくわからなくなる。 これは一番いい最大値と最小値を選…
問題概略 1 ~ Nが書かれた、白と黒のボールが2N個並べられている。 隣り合う２つのボールを入れ替えることが出来る時、白黒をそれぞれの色についてソートするのにかかる最小手数はなにか。制約 1 解法 実際にソートする時の事を考えると、左詰めにやっていき…
E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder問題概略 長さNの非負整数列aに対して、数列の最大値がN-1以下になるまで以下の操作を繰り返し行う。 数列の最大値を一つ選びN減らす。それ以外の値を1増やす上の操作は何回行われるか。制…
E - Don't Be a Subsequence問題概略 文字列Sに対して、その中の部分列でない文字列のうち、一番短く辞書順最小のものを求めよ。制約 10^5解法 0文字目からスタートして、a~zについて、自分に一番近いところをとることを文字列の外に出るまで繰り返すことで…
E: Meaningful Mean - AtCoder Regular Contest 075 | AtCoder 問題概略 長さNの数列Aで、算術平均がK以上になる区間はいくつあるか。制約 N 10 ^5 a,K 解法 ある区間の算術平均がK異常かを判定するには、sum - K * len が0以上かを見ればいい。 これはaの各…
問題概略 (sx,sy)から(tx,ty)まで移動しようとしています。好きな向きへ速さ1で移動できる。 平面上にN個のバリアが貼ってあり、それぞれ半径が与えられる。 バリアは互いに重なっていることがある。 ゴールへ向かう時、バリアの外にいる時間は最短で何か。…
D - 通勤 問題概略 x軸上にN個のガソリンスタンドがあり、D地点にゴールがある。 地点0から燃料Fでスタートし、燃料がT未満でスタンドに着いた時、Fまで補充する。 ガソリンスタンドをいくつか壊した時、ゴールまでたどり着ける組み合わせはいくつか。解法 d…
C - Kill/Death 問題概略 1000個の物を100個の箱に入れたい、また、いくつかの区間で昇順になっている必要がある。N,M sum 解法 昇順について考えなければ、桁DPとして解ける。 dp[i][rem] := iまで見ていて、残り使える合計がrem 昇順になっていないといけ…
C: 駆引取引 - 「みんなのプロコン 2018」 | AtCoder制約 1≤N≤18 1≤xi,ci,vi≤10^15 与えられる入力は全て整数解法 この記事を参考にしました というかそのままです 駆引取引 [「みんなのプロコン 2018」C] - はまやんはまやんはまやんn個を売った時に、買え…
