問題はこちら No.27 板の準備 - yukicoder作りたい板の長さが30以下なので用意する板の長さも30以下 ということは用意する３種類の板の長さの組として考えられるものは30C3=4060通り 各場合について、何枚用意すればいいかDPで調べる int main(){ int d[70],…

問題はこちら No.26 シャッフルゲーム - yukicoderシミュレーションするだけ int main(){ int n,m,p,q; scanf("%d%d",&n,&m); while(m--){ scanf("%d%d",&p,&q); n=p==n?q:q==n?p:n; } printf("%d",n); return 0; } n,mの読み込みを省略したいので、最初はn=…

問題はこちら No.25 有限小数 - yukicoder最初の方針 既約分数を小数表示したとき有限小数になるためには、分母が2,5のみを因数に持つことが必要十分 約分をして、分母を10ベキの形に持っていく long gcd(long a,long b){return b?gcd(b,a%b):a;} int main()…

問題はこちら No.24 数当てゲーム - yukicoder答えの可能性が残っているかどうかをbitで保存しておく 質問した4数もbitで保存して、YESならbitand、NOならbitnotしてからbitand 最終的にはbitが残っているのは1箇所だけになるのでそこを出力 int main(){ int…

問題はこちら No.23 技の選択 - yukicoder解説を読んでもみんなDPって言ってるんだけど……必殺技が当たるまでの回数の期待値は1.5回なので、初めから「コスト1.5で命中100%」と考えて良い よって攻撃を繰り出す順序は関係なく「通常攻撃をi回行って、HPが残っ…

問題はこちら No.22 括弧の対応 - yukicoderk番目の文字が「(」なら右へ、「)」なら左へ探すことになる 最初の文字も含めて、「)」に遭遇したら+1、「(」に遭遇したら-1として、初めて0になった箇所が求める位置 int main(){ int n,i,t=0; char s[10010]; sc…

問題はこちら No.21 平均の差 - yukicoder数の集合Xがあるとき、Xの任意の部分集合A対して、Aに属する数の平均はminX以上maxX以下になる（自明） またN,K≧3なので {最大値}{最小値}{その他全て} と分ければmaxXとminXを達成する集合を同時に作ることができる…

問題はこちら No.18 うーさー暗号 - yukicoder最初の方針 文字列を全部読み込んで、編集してからまとめて出力する 普通にやると「1文字目」のindexが0になっていて少々鬱陶しいのではじめから1つずらして読み込むことにする int main(){ int i; char s[1100]…

問題はこちら No.16 累乗の加算 - yukicoder 繰り返し2乗法 普通a^mを計算しようと思ったら、aをm回掛け算しないといけないが mを2進数展開していい感じに工夫するとO(log2(m))くらいで計算できるというやつ―――― a^(2^n)はnが小さい方から計算することで、n…

問題はこちら No.11 カードマッチ - yukicoder与えられたカードたちの、スートの種類をts、数の種類をtkとすると マッチしないものは(W-ts)*(K-tk) なのでマッチするものはW*K-(W-ts)*(K-tk)-N int main(){ int s[101]={},k[101]={},w,h,n,ts,tk,i,j; scanf(…

問題はこちら No.10 ＋か×か - yukicoder メモ化再帰 「i番目までで数sが作れた」という情報を保存することで2^(N-1)とおり全てを試す必要はなくなる x[60][100100],a[60],m,n; char p[60]; void f(int i,int s){ //今i番目まで使ってsを作った、という状態 …

問題はこちら No.8 N言っちゃダメゲーム - yukicoderよくあるやつ 1手目に(N-1)%(K+1)を言い、あとは(K+1)での剰余が(N-1)と等しくなるように返していけばN-1が言えるので勝てる （相手はが1～Kのいずれを足しても、対応するK～1を足せば増分の合計をK+1にで…

問題はこちら No.7 プライムナンバーゲーム - yukicoder「場にある数がnのとき先攻後攻どちらが勝てるか」をnが小さい方から埋めていけばよい 「∃p:素数.場にある数がn-pのとき後攻が勝てる」なら先攻が勝てる。さもなくば後攻が勝つ int main(){ int p[1300…

問題はこちら No.5 数字のブロック - yukicoderソートして小さい方から使っていく int c(int*a,int*b){return*a-*b;} int main(){ int w[10001]={},i,j,l; scanf("%d%d",&l,&n); for(i=0;i

問題はこちら No.4 おもりと天秤 - yukicoderDP 「k番目までのおもりを使って重さiを作れるか」をkが小さい方から調べ 全てのおもりの重さの合計の半分が作れるか否かをチェックすれば良い 100以下の重さのおもりが100個以下なので、配列は0～10000まで用意…

問題はこちら No.3 ビットすごろく - yukicoder最初の方針 「今までに到達可能な場所を元に、次に到達可能なマスを求める」という操作を、 Nマス目に到達可能になるか、「新たに到達可能になったマス」が1つもなくなるまで行う //整数をひいてそのbitpop数を…

問題はこちら No.2 素因数ゲーム - yukicoder整数Nを(2の因数の数,3の因数の数,…)という組と見れば、山崩しゲームとなる。 具体的には 「素因数を1つ選ぶ」が「山を1つ選ぶ」と 「好きな回数だけ割る」が「好き個数だけ取る」と対応する山崩しゲームの必勝法…

yukicoderのことをメモしていく 基本は自分用で、適宜追記