メモ

yukicoderでゆるふわgolf

2016-07-01から1ヶ月間の記事一覧

yukicoder No.402 最も海から遠い場所

問題はこちら No.402 最も海から遠い場所 - yukicoder初見では解説の「無駄解法」と同じことしか思いつけなかったので、解説を見て回答陸の部分からなる最大の正方形を見つける問題と同値になる #define max(p,q)(p>q?p:q) #define min(p,q,r)(p

yukicoder No.403 2^2^2

問題はこちら No.403 2^2^2 - yukicoderフェルマーの小定理を使ってpowmodするだけ ……と見せかけて、「AがPの倍数かつBがP-1の倍数」に気をつける必要がある (剰余をとってから累乗を計算すると0^0となるが、0を返すのか1を返すのか)先日ライブラリ化したp…

yukicoder No.401 数字の渦巻き

問題はこちら No.401 数字の渦巻き - yukicoder えっと、2次元配列を作って、その上を指定の順番に移動していって…… ええい面倒くさい。(x,y)の位置にある数を一発で求めればそんな面倒な事をしなくて済むぞ 例えばn=6のとき下図のようになる(x,yの座標は0-…

yukicoder No.400 鏡

問題はこちら No.400 鏡 - yukicoder後ろから順に左右を逆にして出力 int main(){ char s[99]; int n,i; gets(s); n=strlen(s); for(i=n;i--;)putchar(s[i]=='<'?'>':'<'); return 0; } '>'と' char s[];i;main(){for(i=strlen(gets(s));i--;putchar(s[i]^2)…

yukicoder No.398 ハーフパイプ(2)

問題はこちら No.398 ハーフパイプ(2) - yukicoder2通りの解がある ・DP解 dp[人数][最低点][最高点][合計点]でDPしてΣ{dp[6][m][M][s]|s=X*4+m+M}を求める #define min(a,b)(a<b?a:b) #define max(a,b)(a>b?a:b) long d[7][101][101][601],a; i,m,M,s,k; int main(){ for(m=0;m<101;m++</b?a:b)>…

yukicoder No.391 CODING WAR

問題はこちら No.391 CODING WAR - yukicoder包除原理で殴るだけ i(≦M)問以下にしか割り当てられないようなパターンは i問の選び方が、割り当て方がi^Nある。 よって求めるべきは (もちろんシグマはi=0からでも構わない)コンビネーションは、前から何度も…

yukicoder No.390 最長の数列

問題はこちら No.390 最長の数列 - yukicoderコンテスト中にはO(N^2)解しか思いつかずに撃沈。解説を見た (以下maxφ=0とする) ・O(N^2)解 xiが小さい方から順に、dp[i]=1+max{dp[j]|xjはxiの約数}としてmax{dp[i]}が答え 配るDPに書き換えて、iが小さい方…

yukicoder No.397 NO MORE KADOMATSU

問題はこちら No.397 NO MORE KADOMATSU - yukicoderソートするだけ int main(){ int n,i,j,s,a[110],b[5000]={}; for(scanf("%d",&n);i<n;i++)scanf("%d",a+i); for(i=0;i<n;i++)for(j=1;j<n;j++)if(a[j-1]>a[j]){ b[s++]=j; a[j]^=a[j-1]^=a[j]^=a[j-1]; } printf("%d\n",s); for(i=0;i</n;i++)scanf("%d",a+i);>

yukicoder No.396 クラス替え

問題はこちら No.396 クラス替え - yukicoder折り返しまで込めて周期は2M 以下、手順2を「行き」、手順3を「帰り」と呼ぶことにする。 ・2人が共に「行き」または共に「帰り」で同じクラスに割り振られることと X≡Y mod 2M は同値 ・1回目の「行き」と1回目…

yukicoder No.395 永遠の17歳

問題はこちら No.395 永遠の17歳 - yukicodern進法で17と表される数はn+7。 7が使われているので基数は8以上。 このことからAが14以下なら-1を出力、15以上ならn-7のみが解になることが分かる。 n;main(){n=scanf("%d",&n)>printf("%d",n>14?n-7:-1);} 52B

yukicoder No.394 ハーフパイプ(1)

問題はこちら No.394 ハーフパイプ(1) - yukicoderソートして真ん中4個の平均 int c(int*a,int*b){return*a-*b;} int main(){ int a[1000],i; for(i=0;i<6;i++)scanf("%d",a+i); qsort(a,6,4,c); printf("%.2f",(a[1]+a[2]+a[3]+a[4])/4.); return 0; } ソー…

yukicoder No.392 2分木をたどれ

問題はこちら No.392 2分木をたどれ - yukicodern+1に対してyukicoder No.104 国道 - メモの逆をするだけ 具体的には、n+1を2進数表示して最上位の1を落とした物を、1→R、0→Lと変換したものを出力する出力を逆にするのは再帰と相性が良い i; f(n){n&&f(~-n/2…

yukicoder No.389 ロジックパズルの組み合わせ

問題はこちら No.389 ロジックパズルの組み合わせ - yukicoderヒントが0のみだった場合は1通り。これだけ例外処理 k-1+ΣHi>MのときNAになるのは明らか。 そうでないとき、必要な分(=黒マスとその間の白1マス)だけ先に並べると、残った(M-(k-1+ΣHi))個の白…

yukicoder No.388 階段 (1)

問題はこちら No.388 階段 (1) - yukicoderやるだけ だいたいN/Kっぽい何かをすればいい。 切り捨てなのか切り上げなのか、1足したり引いたりしなくていいのか、といったことはサンプルを見れば分かる n; main(k){ scanf("%d%d",&n,&k); n=!printf("%d",n/k+…

yukicoder No.385 カップ麺生活

問題はこちら No.385 カップ麺生活 - yukicoderまずは「ちょうどk円で買えるカップ麺の最大個数」を求める。 これは要するに「Ci円玉でちょうどk円払う時、最大で何枚の硬貨が使えるか」なので、DPでできる。 (c.f.yukicoder No.247 線形計画問題もどき - …

yukicoder No.384 マス埋めゲーム2

問題はこちら No.384 マス埋めゲーム2 - yukicoderyukicoder No.166 マス埋めゲーム - メモよりも少し頭を使う。 全てのマスが埋まった⇔「全ての列が選択された」または「全ての行が選択された」 となる また、「選択されていない列の数+選択されていない行…

yukicoder No.383 レーティング

問題はこちら No.383 レーティング - yukicoderやるだけ int main(){ int n,k; scanf("%d%d",&n,&k); if(k-n>0)printf("+"); printf("%d",k-n); return 0; } ところでprintfには %+d という便利なフォーマットがあって、値が正の時には頭に+を付けてくれる。…

yukicoder No.366 ロボットソート

問題はこちら No.366 ロボットソート - yukicoder幅kのバブルソートをする 普通のバブルソートで for(i=0;i<n;i++)for(j=0;j+1<n;j++)if(x[j]>x[j+1])swap(x[j],x[j+1]); とするところを for(i=0;i<n;i++)for(j=0;j+k<n;j++)if(x[j]>x[j+k])swap(x[j],x[j+k]); とすればよい (あとで縮める都合上、普通のバブルソートより定数倍</n;i++)for(j=0;j+k<n;j++)if(x[j]></n;i++)for(j=0;j+1<n;j++)if(x[j]>…