メモ

yukicoderでゆるふわgolf

yukicoder No.243 出席番号(2)

問題はこちら No.243 出席番号(2) - yukicoder出席番号を1ずらして1-based index、すなわちとする。 とおく。 をのべき集合、すなわちとする。 を が嫌いな人の数 とする。 を (「が嫌いな人に出席番号が割り当てられている」を満たす割り振りの個数 とする…

yukicoder No.565 回転拡大

問題はこちら No.565 回転拡大 - yukicoder90度回転する操作により(i,j)にうつるようなマスは(h-1-j,i)である。(0-based index) よって new[i][j]=old[h-1-j][i]; という感じのことをi,jについてループでやればよい。 180度、270度回転はこの操作を繰り返…

yukicoder No.326 あみだますたー

問題はこちら No.326 あみだますたー - yukicoder{1,…,N}上の順序 " このとき、「あみだくじによって数列{Ai}を作ること」と「順序"バブルソートをすること」が対応する (完成するあみだくじにおいて左にある数ほど"小さい"と考えるということ)ということ…

yukicoder No.556 仁義なきサルたち

問題はこちら No.556 仁義なきサルたち - yukicoderUnion-Findするだけ int uniroot[10010],unicnt[10010]; void ufinit(int n){for(int i=0;i

yukicoder No.553 AlphaCoder Rating

問題はこちら No.553 AlphaCoder Rating - yukicoderほとんどそのまま数式を計算すればよいが、g^(-1)とF(∞)だけは非自明。 gの逆関数はにぶたんで、F(∞)は適当に大きなxを用いてF(x)で近似することで、問題文の数式をそのまま実装して答えを得ることもでき…

yukicoder No.588 空白と回文

問題はこちら No.588 空白と回文 - yukicoderまず線対称の軸となるべき場所を固定する。 (そのような場所は、文字の中心か、文字と文字の間となる) 中心から外側へ向かって、各文字が回文を構成するかどうかをチェックする。 中心に対して対称な位置にある…

yukicoder No.571 3人兄弟(その2)

問題はこちら No.571 3人兄弟(その2) - yukicoderその1と同様 a[身長][体重]=人 という配列を作っても良いが a[身長*(大きな数)-体重]=人 とすることで1次元配列にできる a[30010],t,s; main(){ for(int i=1;i<=3;i++){ scanf("%d%d",&t,&s); a[t*101-s]…

yukicoder No.570 3人兄弟(その1)

問題はこちら No.570 3人兄弟(その1) - yukicoder場合分けでも簡単に解けるが、別の方針で考える a[身長]=人 という配列を作って身長が大きい方からチェックする a[999],t; main(){ for(int i=1;i<=3;i++){ scanf("%d",&t); a[t]=i; } for(int i=200;i>10…

yukicoder No.587 七対子

問題はこちら No.587 七対子 - yukicoder各文字が何個あるかを数える。 ちょうど2個ある文字がちょうど6種類あるとき、その時に限り、残りの1種類と同じ文字を加えることで7ペアにできる a[999],ans,c,i; main(){ for(i=0;i<13;i++)a[getchar()]++; for(i='a…

yukicoder No.589 Counting Even

問題はこちら No.589 Counting Even - yukicodernを2進法で表したときの1の個数をpopcnt(n)とおく 結論からいうとN+1-2^popcnt(N)が答え 方針はいろいろあるがいずれの場合も奇数が2^popcnt(N)個あることを示す・パスカルの三角形 (以下、「n段目の左からm…

yukicoder No.586 ダブルブッキング

問題はこちら No.586 ダブルブッキング - yukicoder各部屋について最初の1人で部屋を予約することにする。 2人目以降は振替により(P1+P2)円の損失が発生する。 a[1000],p1,p2,n,x,s; main(){ scanf("%d%d%d",&p1,&p2,&n); for(int i=0;i

yukicoder No.581 XOR

問題はこちら No.581 XOR - yukicoderXORを表す演算子を^とする。XORの基本的な性質を確認する ・順序に依らない(可換かつ結合的) ・任意のXについてX^X=0C=A^Bの両辺にAをXORすることでA^C=A^A^B=Bが得られる long a,b;main(){scanf("%ld%ld",&a,&b);prin…

yukicoder No.555 世界史のレポート

問題はこちら No.555 世界史のレポート - yukicoderDP解法との賢い数学解法がある・DP解 N文字以上を作る最小コスト=min{ちょうどK文字を作る最小コスト|K≧N} K文字を作る際には、その過程で必ずK/2文字以上の状態を経由するので、Kの上限は2Nとしてよい。 …

yukicoder No.566 だいたい完全二分木

問題はこちら No.566 だいたい完全二分木 - yukicoder○激ヤバ解法 シャッフルすれば高確率で通る○まじめな解法 普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする ・方針1 完全二分木を作る過程で、2と3を入れ替える。 そうす…

yukicoder No.567 コンプリート

問題はこちら No.567 コンプリート - yukicoder包除原理やるだけ(説明は後述) main(n){ scanf("%d",&n); printf("%.9f", 1 - 6*pow(5/6.,n) +15*pow(4/6.,n) -20*pow(3/6.,n) +15*pow(2/6.,n) - 6*pow(1/6.,n) ); } 事象A1,…,A6を、 A1:1が出ない … A6:6…

yukicoder No.564 背の順

問題はこちら No.564 背の順 - yukicoder最初は1位で、高い人が現れるたびに順位は1つ下がる h,n,t,S; main(){ scanf("%d%d",&h,&n); S=1; for(int i=1;i<n;i++){ scanf("%d",&t); if(t>h)S++; } printf("%d",S); if(S%10==1)puts("st"); else if(S%10==2)puts("nd"); else if(S%10==3)puts</n;i++){>…

yukicoder No.549 素材合成システム

問題はこちら No.549 素材合成システム - yukicoder合成素材の側の経験値の最終的な寄与度は高々floor(a/2) 実際に、一番経験値が高い奴をベースにし、残りを素材として順次合成していくことで最大になる。 c(int*a,int*b){return*b-*a;} a[100010],n,S; mai…

yukicoder No.561 東京と京都

問題はこちら No.561 東京と京都 - yukicoderDPやるだけ(といいつつ、後ろから見る方法しか思いつかなかったので要反省)(i-1)日目が終了した時点で東京にいるときの最大利益をT、京都にいるときの最大利益をKとおく。 i日目に東京でt、京都でk得られる場合…

yukicoder No.537 ユーザーID

問題はこちら No.537 ユーザーID - yukicoder2つの数A,Bを連結するのは、文字列として処理するのでも良いが、Cだと面倒なので計算をする 数Bの桁数はで得られるので、AとBをこの順で連結したものはで求められるNが大きいので1~√Nまでを調べる long n,s[2000…

yukicoder No.560 ふしぎなナップサック

問題はこちら No.560 ふしぎなナップサック - yukicoder算数やるだけ ナップサックの中にM円入っているとき、1回叩いた後は (2M+(M+1)+0)*1/3=M+1/3 より(M+1/3)円になる。 これはMに依らないのでこの操作をN回行うとM+N/3円になる。 (写像f(M)=M+1/3をN回…

yukicoder No.559 swapAB列

問題はこちら No.559 swapAB列 - yukicoder求めるものは転倒数と同値 先頭から見ていってAが登場する度に、それ以前に登場したBの個数を数えれば良い char s[99]; b,ans,n; main(){ gets(s); n=strlen(s); for(int i=0;i

yukicoder No.558 575検出するやつ

問題はこちら No.558 575検出するやつ - yukicoderstrstrするだけ char s[110]; main(){ gets(s); puts(strstr(s,"575")?"YES":"NO"); } 100文字をintに読み込んでも幸いREにはならず a;main(){puts(strstr(gets(&a),"575")?"YES":"NO");} 50B aをmain引数に…

yukicoder No.305 鍵(2)

問題はこちら No.305 鍵(2) - yukicoderwriter解と同じ発想 ある桁の数字を変えた時、当たり数が大きくなれば新しい方が当たり、小さくなれば古い方が当たり。これを繰り返して上の桁から順に調べていく char s[]="0000000000"; n,k,i; main(){ puts(s); ffl…

yukicoder No.557 点対称

問題はこちら No.557 点対称 - yukicoder回文と同様、上半分を決めると下半分は自動的に決まる ・n=1のとき 1,8の2通り ・nが偶数のとき 上位n/2桁を決めると、下位は自動的に決まる 先頭の位に使えるのは1,6,8,9の4通り それ以外は0,1,6,8,9の5通り よって4…

yukicoder No.554 recurrence formula

問題はこちら No.554 recurrence formula - yukicoderとする このとき よりとなりの漸化式が得られる でありなので、これにより計算できる long s[100100]; n,ans,m=1e9+7; main(){ scanf("%d",&n); if(n==1)ans=1; else{ s[1]=1; for(int i=2;i<=n;i++)s[i]…

yukicoder No.552 十分簡単な星1の問題

問題はこちら No.552 十分簡単な星1の問題 - yukicoder値が大きいので文字列として読み込む。 0のときはそのまま出力し、それ以外のときは末尾に0をつける char s[99]; main(){ gets(s); if(strcmp(s,"0")==0)puts("0"); else printf("%s0",s); } 20文字くら…

yukicoder No.548 国士無双

問題はこちら No.548 国士無双 - yukicoder「a~mのうち、いずれか1種を2つ、残りの12種を1つ含む」というのは「a~mのうち、13種いずれもを1つ以上含み、これら以外を含まない」と同値 よって、与えられた13文字にa~mを加えたものが条件をみたすかをチェッ…

yukicoder No.547 未知の言語

問題はこちら No.547 未知の言語 - yukicoderscanfを使うと空白区切りで読み込めるのでstrcmpで比較するだけ char s[11][22]; char t[11][22]; main(){ int n; scanf("%d",&n); for(int i=0;i

yukicoder No.533 Mysterious Stairs

問題はこちら No.533 Mysterious Stairs - yukicoder初期値にちょっと気をつける必要があるがDPやるだけ。 dp[昇った段数合計][直前に段数]=場合の数 dp[1000010][4];n; mod=1000000007; main(){ dp[1][1]=1; dp[2][2]=1; dp[3][1]=dp[3][2]=dp[3][3]=1; sca…

yukicoder No.538 N.G.S.

問題はこちら No.538 N.G.S. - yukicoder数学するだけ連立方程式 を解き を得る。求める答えはであるからこれに代入して となる。 は最大10^5なので2乗すると32bitの範囲に収まらないことに注意する long a,b,c; main(){ scanf("%ld%ld%ld",&a,&b,&c); print…