問題はこちら No.129 お年玉(2) - yukicoderあまりはN/1000%Mで求めることができるので、M個のぽち袋からN/1000%M個選んであたりにするので、求めるべき答えは二項係数C(M,N/1000%M) 剰余が素数なら逆元を使うことでちゃちゃっと求められるのだけど、そうじ…

問題はこちら No.128 お年玉(1) - yukicoder割り算するだけ long a; main(b){ scanf("%ld%d",&a,&b); a=!printf("%ld",a/1000/b*1000); } 68B2017/07/30追記 計算式を工夫して1B短縮 計算結果は最大10^16なのでdoubleの精度53bitに収まらないが、1000の倍数…

問題はこちら No.126 2基のエレベータ - yukicoder場合分けを丁寧にしないとありとあらゆるケースが殺しに来る k:=abs(s-a)、t:=abs(s-b)とする ○k Aが来るのでそのまま地下1階に降りることができる ○k>tのとき sが1ならこの場合でもAが来る そうでない時はB…

問題はこちら No.123 カードシャッフル - yukicoder愚直にシミュレーション int main(){ int m=51,a[51],t; while(m--)a[m]=m; //1-based scanf("%*d%d",&m); while(m--){ scanf("%d",&t); a[0]=a[t]; //t番目の札が一番上にいく while(t--)a[t+1]=a[t]; //t…

問題はこちら No.118 門松列(2) - yukicoder竹は互いに区別するので、例えば長さが相異なるi,j,kである竹が各a,b,c本あれば、求める値はa*b*cになることがすぐ分かる 竹の長さは100以下なので、各長さの竹が何本あるかを調べて合計を求めれば良い int main()…

問題はこちら No.116 門松列(1) - yukicoder前から順に調べていくだけ int main(){ int a,b,c,n,s=0; scanf("%d%d%d",&n,&a,&b); n-=2; while(n--){ scanf("%d",&c); if(a-c&&(a

問題はこちら No.115 遠足のおやつ - yukicoder出力が-1になるケースは2パターン存在する ・高い方からK個買ってもD円に満たない場合 ・安い方からK個買ってもD円を超える場合 (K>Nであるようなものは必ずどちらかに抵触する) 逆にこれらに触れなければ条件…

問題はこちら No.113 宝探し - yukicoder1文字ずつ処理するだけ int main(){ int a=0,b=0,i; char s[110]; gets(s); for(i=0;s[i];i++){ if(s[i]=='E')a++; else if(s[i]=='W')a--; else if(s[i]=='N')b++; else b--; } printf("%f",hypot(a,b)); return 0; …

問題はこちら No.112 ややこしい鶴亀算 - yukicoder与えられたa[i]たちを全て合計すると、全員の足の数のN-1倍になる （∵全員が自分以外のN-1人に数えられるため） よってこれにより普通の鶴亀算に帰着することができた int main(){ int n,m,x,s=0; scanf("%…

問題はこちら No.111 あばばばば - yukicoderサンプルを見ればなんとなく((L-1)/2)^2だろうとの予測はつくけれど一応考察 長さ奇数の部分列は必ず回文になり、逆に回文ならその長さは奇数 長さLの文字列の中に長さMの文字列はL-M+1個あるので Σ[i=0...(L-1)/…

問題はこちら No.106 素数が嫌い！2 - yukicodera[i]にiがいくつの素因数を持つかを保存していく int main(){ int a[2000010]={},n,k,i,j,s; scanf("%d%d",&n,&k); for(i=2;i<=n;i++){ if(!a[i])for(j=i;j<=n;j+=i)a[j]++; //もしa[i]が0なら、iは素数なので…

問題はこちら No.105 arcの六角ボルト - yukicoder逆三角関数を使えば良さそうだということはすぐに分かるのだが abs(x)>1のケースが紛れているのでacos(x)とするとWAを食らう atan2を使う int main(){ double x,y,t; int n,i; scanf("%d",&n); while(n--){ …

問題はこちら No.104 国道 - yukicoder日本語で説明するのが難しいが、二分木に上から順に番号を振っているので、 n号線は2n号線と(2n+1)号線に分岐する ということで、1文字目から順に処理していく int main(){ int a=1,i; char s[40]; gets(s); for(i=0;s[…

問題はこちら No.102 トランプを奪え - yukicoder「各山の最後のカードを取った場合、相手の手札の半分（切り上げ）を奪う」 「すべての山が無くなったとき、手札が多いほうが勝ち」 という２つのルールから 「最後の山の最後のカードを取れば勝ち」 である…

問題はこちら No.101 ぐるぐる！あみだくじ！ - yukicoderyukicoder No.100 直列あみだくじ - メモで以前述べたとおり置換は巡回置換の積でかける この時これらの位数(=長さ)の最小公倍数が答えとなることはあきらか int gcd(int a,int b){return b?gcd(b,a%…

問題はこちら No.100 直列あみだくじ - yukicoder置換の知識を既知とする 置換σが与えられた時、置換τであってτ^2=σとなるようなものが存在するかを判定する問題 「任意の置換は、同じ文字を含まない巡回置換たちの積で表される」ということを思い出し、まず…

問題はこちら No.99 ジャンピング駒 - yukicoderよく考えると、初期位置が偶数の駒は偶数座標に、奇数の駒は奇数座標にしか動けない ジャンプするには差が1であることが必要なので、消える２つの駒の座標は必ず偶数と奇数がセットになっている 逆に偶数座標…

問題はこちら No.98 円を描こう - yukicoder三平方の定理は既知とすれば floor(sqrt(x^2+y^2)*2)+1が答えとなることは明らか （境界の扱いに注意） doubleで普通に計算すればこの制約の下では誤差は発生しないようだ hypotを呼んで終わり （hypot(x,y)はsqrt…

問題はこちら No.91 赤、緑、青の石 - yukicoderO(1)解 石の色は忘れてR≦G≦Bとしてよい。R個以上作れることは自明 Rの石を2個つかって他の石と交換する操作では、作れるようになるアクセサリーの数が増えることはない なぜなら、もしR2個でGを作ったとすれば…

問題はこちら No.90 品物の並び替え - yukicoder制約的に全探索すればいいだけなのだけど、Cにはnext_permutation的なものはないし 自分で実装するのは面倒なので、先に解いていたNo.357をコピペした いわゆるbitDPと呼ばれている奴 「既に使った商品」をbit…

問題はこちら No.89 どんどんドーナツどーんといこう！ - yukicoderパップス＝ギュルダンの定理 - Wikipedia これによれば、回転体の体積は、「動いたものの面積」×「重心の移動距離」で求まるドーナツ型は、円を、その円を通らず同一平面上にある直線で回転…

問題はこちら No.88 次はどっちだ - yukicoderパスはなかったので、既におかれている石を数えれば良い あるいはまだ石のおかれていないマスを数えれば良い int main(){ int a=0,n=71; char s[7]; scanf("%s",s); if(s[0]=='o')a++; //最後に偶奇で判定するの…

問題はこちら No.87 Advent Calendar Problem - yukicoderNが大きいので毎年曜日をチェックしていると間に合わない うるう年は400年周期だが400年間は365*400+97=146097日であり、これは7の倍数なので 結局400年周期でカレンダーは完全に一致する よって400…

問題はこちら No.85 TVザッピング(1) - yukicoderループを見つける問題なので始点は関係ない 場合分け 少なくとも一方が1の時 他方が2ならYES、3以上ならNO n*mが奇数の時 市松模様による塗り分けを考えれば不可能 n*mが偶数の時 必要なら全体を90度回転させ…

問題はこちら No.84 悪の算盤 - yukicoderR≠Cのとき 回転一致の仕方は2通り 回転により1-based indexの座標により(i,j)で表されるマスは(R+1-i,C+1-j)に移るので R,Cの少なくとも一方が偶数の時、回転により自身と一致することはない よってR*C/2-1 R,Cの両…

問題はこちら No.83 最大マッチング - yukicoderできるだけ桁を増やしたほうが大きな数になる ということで1をたくさん作れば良い マッチ棒が奇数本なら、最上位を7とする int main(){ int a; scanf("%d",&a); while(a){ putchar(a%2?'7':'1'); a-=a%2?3:2; …

問題はこちら No.82 市松模様 - yukicoderi行j列目について順番に見れば良い 'B'+'W'=153なので153から引くことでもう一方の文字に切り替えることができる int main(){ int a,b,c,i,j; scanf("%d%d ",&a,&b);c=getchar(); for(j=0;j

問題はこちら #43377 No.80 四角形を描こう - yukicoder和が一定で積を最大化させる問題 縦+横はfloor(n/2)となる。これをmとおく mが偶数の時(m/2)*(m/2) mが奇数の時((m+1)/2)*((m-1)/2)=(m*m-1)/4=floor(m*m/4)となる n;main(){n=atoi(gets(&n))/2;n=!pri…

問題はこちら No.79 過小評価ダメ・ゼッタイ - yukicoder各レベルごとに人数を集計して、最大値をレベルの高い方から調べていく int main(){ int l[7]={},n,i; scanf("%d",&n); while(n--){scanf("%d",&i);l[i]++;} i=6; for(n=6;n;n--)if(l[n]>l[i])i=n; pr…

問題はこちら No.77 レンガのピラミッド - yukicoder{小さなピラミッド}⊂{大きなピラミッド}なので {小さなピラミッドを作るため動かさないレンガ}⊂{大きなピラミッドを作るため動かさないレンガ} となる。よって可能な限り大きなサイズのピラミッドを作れば…