C - 高橋君とカード / Tak and Cards 問題概略 N枚のカードがあり数字が書かれている。これらの中から1枚以上を選び、数の平均をAにしたい。選び方は何通りあるか。制約 1 1 1解法 まず普通にナップザックとして解いてみる。 つまり、boolean[i][j]:=i枚目ま…

問題概略 高々2000個の点が与えられる、3点を選んだ時、鈍角三角形、直角三角形、鋭角三角形の数を数えよ。制約 任意の三点は同一直線上にない。解法 ある点について、偏角でソートすればいい。 角度が2周するように配列を追加してやって、自分＋180度以内に…

問題概略 A~Bの中で4か9が含まれる物の個数を答えよ。制約 A,B 解法 4か9が一つでも含まれてればいいなら包除原理使うか！と思ったけど、大変そうなので桁DPで解いた。 まとめ上げるのに必要な条件は 何桁目を見ているか 数が上限ギリギリかどうか すでに4,9…

問題概略 H*Wのマス目がある。好きなマスから好きなだけ自分より大きいマスへ隣に動ける。 移動経路の個数の余りを求めよ。制約 HW 解法 自分より大きいところへしか進めないため、閉路はない。 よって経路の数をマスごとにメモできる。 dpに-1を入れておき…

問題概略 風船がN個H[i]にあり、秒速S[i]で高さが上昇していく。 1秒に一回風船を割れるとして、割った時の最大の高さの最小値を求めよ。解法 2分法で解きたくなる。 それぞれの風船について、今まで使っていない秒数の内ぎりぎりセーフの秒数を選んでいく貪…

問題概略 ２つの整数u,v 制約 N 解法 aとbを適当に選んで、出てきたu,vを数えていきたくなる。しかし、これでは重複してしまうし、メモできるような数ではない。 ある桁のビットが1,0の時に0,1にしてもu,vが等しいと気づく。 よって1,0 は許すが0,1は許さな…

D: Median of Medians - AtCoder Regular Contest 101 | AtCoder 問題概略 長さMの数列の任意の区間[lr]の中央値でなる数列の中央値を求めよ。 10^5 N 10^9 A解法 xが中央値が満たす条件について考えてみる。 x以上の要素がs/2以上ある。 そのような物の内最…

http://www.igaris.com/math/c.pdfr個の物をN個の箱に分配するhttps://drive.google.com/file/d/1WC7Y2Ni-8elttUgorfbix9tO1fvYN3g3/view数え上げテクニック 整数問題もこれで攻略！生徒に"鳩の巣原理"を教えよう！【知っていると必ず得】｜塾講師ステーショ…

問題概略 長さKの数列A,Cが与えられる。 n >= 1で An+k = (c1 & An+k-1) xor (c2 & An+k-2) xor .....(ck & An)である時、 Amを求めよ制約 M N A &とxorが*,+なら行列のべき乗の形にして高速に解ける。 実は今回も同様に出来る。 32ビットの非負の数は&,xor…

問題概略長さ2^Nの数列がある。 (i | j) 制約 N Ai 解法 i or j が K以下ということについて考える時、i or j が0の時、1の時、...Kの時という風に分けて考えたくなる。（使い回せるし） i or j が K となるものを列挙するのは難しいが、今回知りたいのはK以…

問題概略盤面に金塊が並べてある。 また、回収装置がいくつか置いてあり上下左右の自分から連続した金塊を回収することが出来る。 好きな順番で回収装置を作動させる時、最大の金塊回収数を求めよ。制約 W,H 回収装置N 解法 回収装置を使うと4つの小さい盤面…

問題概略 括弧の対応を取る時の最小操作回数 移動回数＋変更回数制約解法 dpは状態の纏め上げだということを忘れていた。 愚直に考えると、2^100になってしまうが、現在見終わった場所、最後に変更した場所、(が開いている数が同じなら一つの状態に纏められ…

A - YahooYahooYahoo問題概略 文字列Sのyahoo....yahooへのレーヴェンシュタイン距離を求めよ。制約 10^5解法 [i]までをy,a,h,o,oにする場合で遷移していく（レーヴェンシュタイン距離を求める時と似た感じで） yahooは循環しているのでo->yへの遷移も出来る…

問題概略 K個の文字列にヒットして、N-K個の文字列にはヒットしない最小の文字列を出力せよ制約 10^5解法 まず、考えうる最高の長さの文字列を探す。 具体的には必要なものの最長の共通部分を二分法で探していく。(1個目と2個目、2と3という風にo(n log n)で…

問題概略 N人の女子とM人の男子がいる。女子はいくつかのチョコを持っており、渡したい男子とその時の幸福度がある。 女子P人と男子R人を選んで幸福度を最大にしたい。制約 1解法 愚直にやると 18c9 * 18c9 で 48000 * 48000 ぐらいになる。 片方を固定した…

https://yukicoder.me/problems/no/200問題概略 お互いのプレイヤーはA枚、C枚のカードを持っていて互いにカードを出していく。 カードを使い切ったら自分が出したカードを手札に加えられる。 相手より大きい数を出したら勝ちの時、N試合で最大何回勝てるか…

AtCoder Beginner Contest 004 - AtCoder Beginner Contest 004 | AtCoder問題概略 無限個の箱が並んでいる。地点-100には赤がR個、地点0には緑がG個、地点100には青がB個ある。マーブルは隣に動かすことができる。 一つの箱に複数のマーブルが無いようにす…

D: プレゼント - AtCoder Beginner Contest 038 | AtCoder 問題概略 x,yでの最大部分増加列 制約 1≦N≦105 1≦hi≦105 1≦wi≦105 解法１ dp[i] := iまでを使ってできる最長の増加列。 1次元の場合はソートして、一つ一つ見ていき小さい場合は自分より大きい最小…

https://beta.atcoder.jp/contests/abc105/tasks/abc105_c 問題概略整数Nの-2進数表現を求めよ 制約 入力はすべて整数である −109≤N≤109 解法 とりあえず正の数の足し算で考える。 上から桁の値を書くと 64 -32 16 -8 4 -2 1 となる ある桁で1 + 1 が行われ…

呼びにくいので適当に名前つけました（ごめんなさい）何気ない 私の疑問が 東大生インターンを きずつけた pic.twitter.com/Wr96JGtfjm— Miku Nozaki (@mikupaccho) August 6, 2018 パリピ誕生日問題とは@mikupacchoさんがtwitterでつぶやいていた問題のこと…

問題概略 A,B,C,?からなる文字列が与えられる。 ?にABCのいずれかを入れてできる任意の文字列について、i,j,kがABCとなるような選び方の合計の余り 制約 10^5 解法 途中まで見て一つも満たされていないもの、Aまであるもの、ABまであるもの、ABCがそろってい…

D - Small Multiple 問題概略 正の数Nにある倍数をかけて桁の和を最小にしたい 制約 2≤K≤1052≤K≤105 KK は整数である 解法 modKで考えるとグラフの遷移で書ける コストの合計が桁の和になればよく、すべての数が作れればよい。*10,+1があればすべての数が作…

D - Checker 問題概略 N個の座標と希望が与えられる。 盤面をK*Kの市松模様で塗るトキ、最大でいくつの希望を叶えられるか 11 ≤≤ NN ≤≤ 105105 11 ≤≤ KK ≤≤ 10001000 00 ≤≤ xixi ≤≤ 109109 00 ≤≤ yiyi ≤≤ 109109 ii ≠≠ jj なら (xi,yi)(xi,yi) ≠≠ (xj,yj)(xj…

問題概略 長さNの数列がある。あるl,rでAl ~ Arのxorと合計が等しくなるようなl,rの組み合わせを数えよう 制約 1≤N≤2×1051≤N≤2×105 0≤Ai<2200≤Ai<220 入力はすべて整数である 解法 しゃくとり。 前回の長さの分を引き、新しい分を足す。という感じ public st…

B - Find Symmetries 問題 N*Nのアルファベットが与えられる。 上にa、右にb動かしたら対称になるようなa,bの数を求めよ 制約 1≤N≤3001≤N≤300 Si,jSi,j ( 1≤i,j≤N1≤i,j≤N ) は英小文字 解法 対称なものを上下にa動かした物も対称である。 対称でないものを動…

B - Mysterious Light 問題概略 制約 2≦N≦10122≦N≦1012 1≦X≦N−11≦X≦N−1 NN と XX はいずれも整数である。 解法 この問題が難しいのは、残された形が三角形、台形、平行四辺形と変化していくから。 一回の操作を平行四辺形を小さい平行四辺形に変えるものだと…

B - Mysterious Light 問題概略 制約 2≦N≦10122≦N≦1012 1≦X≦N−11≦X≦N−1 NN と XX はいずれも整数である。 解法 この問題が難しいのは、残された形が三角形、台形、平行四辺形と変化していくから。 一回の操作を平行四辺形を小さい平行四辺形に変えるものだと…

C - BBuBBBlesort! 問題概略 長さNの数列を3つか２つ選び反転する。2つの最小操作回数は 制約 1≦N≦1051≦N≦105 0≦Ai≦1090≦Ai≦109 i≠ji≠j ならば Ai≠AjAi≠Aj 入力はすべて整数である。 解法 3つの数を反転する操作を使うと偶数項、奇数項で、自由に動かせる。 …

B - Colorful Hats 問題文 NN 匹の猫がいます。 猫には 11 から NN まで番号が振られています。 各猫はある色の帽子を被っています。 猫 ii は「自分を除く N−1N−1 匹の猫が被っている帽子の色の種類数はちょうど aiai である」と言っています。 すべての猫…