メモ

yukicoderでゆるふわgolf

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…

yukicoder No.544 Delete 7

問題はこちら No.544 Delete 7 - yukicoderCで文字列処理をするのはつらいので数値として扱う。 下の位から順に見ていって、7であるようなところは6と1に分解する。それ以外はそのまま。 例えば72727なら62626+10101にする int s,n,i; main(){ scanf("%d",&n…

yukicoder No.543 命題

問題はこちら No.543 命題 - yukicoder問題文をよく読むと、入力「a b」に対しては「b a」を出力すれば良いことがわかる main(){ char a,b; scanf("%c %c",&a,&b); printf("%c %c",b,a); } 1行まるごとひっくり返せばよい 頭から読んでお尻から出力→main再帰…

yukicoder No.542 1円玉と5円玉

問題はこちら No.542 1円玉と5円玉 - yukicoder5*b+4円以下の範囲については1円玉を5枚以上使うことなく作れるので、その範囲については2重ループ それ以上は5円玉を全て使った上で1円玉で調整する main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<=…

yukicoder No.536 人工知能

問題はこちら No.536 人工知能 - yukicoder後ろ2文字が"ai"かどうかで分ける char s[99]; int n; main(){ gets(s); n=strlen(s); if(s[n-2]=='a'&&s[n-1]=='i'){ s[n-2]='A'; s[n-1]='I'; }else{ s[n]='-'; s[n+1]='A'; s[n+2]='I'; } puts(s); } で、この方…

yukicoder No.532 Possible or Impossible

問題はこちら No.532 Possible or Impossible - yukicoderM+0*(残り) の形が作れれば十分 ●M≧4のとき M+(3-2-1)*(残り) ●M=3のとき ・N=3のとき:3*(2-1) ・N=4のとき:4+2-1*3 ・N≧5のとき:3+(5-4-1)*(残り) ●M=2のとき ・N=2のとき:2*1 ・N=3のとき:3-2…

yukicoder No.531 エヌスクミ島の平和協定

問題はこちら No.531 エヌスクミ島の平和協定 - yukicoderm≧nなら全員で船に乗れば1日で移動できる。そうでないとする。 1回目の移動で船に乗るグループと乗らないグループに分けると、これはどちらも非空集合なので、動物1が船に乗り、動物2が船に乗らない…

yukicoder No.530 年齢って毎年変わるし覚えるの難しいよね

問題はこちら No.530 年齢って毎年変わるし覚えるの難しいよね - yukicoder日付を気にしなくていいので、簡単 y; main(){ scanf("%d",&y); printf("%d",2017-y); } ぎゅ n;main(){printf("%d",2017-atoi(gets(&n)));} 43B

yukicoder No.527 ナップサック容量問題

問題はこちら No.527 ナップサック容量問題 - yukicoderまずは普通に01ナップサック問題を解く必要があるが、そのときのDPのやりかたとして2通り考えられる。1つ目は、問題文の表にあるように、d[i]に「重さi以内で得られる価値の最大値」を保存する方法 #d…

yukicoder No.526 フィボナッチ数列の第N項をMで割った余りを求める

問題はこちら No.526 フィボナッチ数列の第N項をMで割った余りを求める - yukicoder普段より丁寧めに解説。 一般的なフィボナッチ数列とはindexが1つずれていることに注意 ・漸化式に従って再帰的に計算する 詳細は省くがO(φ^N)となりTLE fib(n,m){ if(n==1)…

yukicoder No.525 二度寝の季節

問題はこちら No.525 二度寝の季節 - yukicoder入出力に少し気をつける必要があるが、それ以外は前見た問題とほぼ同じ yukicoder No.296 n度寝 - メモ main(x,y){scanf("%d:%d",&x,&y);printf("%02d:%02d",(x+y/60)%24,(y+=5)%60);} 74B

yukicoder No.524 コインゲーム

問題はこちら No.524 コインゲーム - yukicoderNimなので問題は「1~Nまでxorをとったものが0か否か判定せよ」と読み替えられる。(このことの証明は以前した:yukicoder No.2 素因数ゲーム - メモ) 以下では「1~Nまでのxorをとったもの」をxor和と呼ぶこ…

yukicoder No.523 LED

問題はこちら No.523 LED - yukicoder1~Nを2個ずつ並べる重複順列なので(2N)!/2^N mod Pでの階乗やべき乗、逆元を計算する関数を持っているならこれをそのまま投げても良いでしょう #define ll long long ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n…

yukicoder No.522 Make Test Cases(テストケースを作る)

問題はこちら No.522 Make Test Cases(テストケースを作る) - yukicodera,b,cの三重ループでやると間に合わないという罠がある a,bを決めればcが自動的に決まるので二重ループで書ける 似たような話は前にNo.250 atetubouのzetubou - yukicoderの問題文で見…

yukicoder No.521 Cheeses and a Mousetrap(チーズとネズミ捕り)

問題はこちら No.521 Cheeses and a Mousetrap(チーズとネズミ捕り) - yukicoderK=0及びK>Nのときは0。 そうでないとき、該当する箱はK番目かN+1-K番目。この2つが一致するとき危険は箱は1つで、一致しないとき2つ。 n,k; main(){ scanf("%d%d",&n,&k); if(k…

yukicoder No.513 宝探し2

問題はこちら No.513 宝探し2 - yukicoder制約の厳しいバージョンと全く同じなので詳細はそちら yukicoder No.514 宝探し3 - メモ a,b;main(i){for(;i%2^!a^!b&&fflush(!printf("%d %d\n",a-b/2,b/2))+scanf("%d",&b+i++%2););} 89B

yukicoder No.514 宝探し3

問題はこちら No.514 宝探し3 - yukicoderN=100000とおく (0,0)及び(N,0)の2点からの距離が分かれば特定できる。 なぜなら、それぞれの点からの距離をd1,d2、宝の位置を(x,y)とすれば x+y=d1 (N-x)+y=d2 となるので、この連立方程式を解く事により x=(d1-d2…

yukicoder No.516 赤と青の風船

問題はこちら No.516 赤と青の風船 - yukicoder入力を読み込んで、それがBLUEかREDか判別する char s[10]; b,r; main(){ for(int i=0;i<3;i++){ scanf("%s",s); if(strcmp(s,"BLUE")==0)b++; else r++; } if(b

yukicoder No.512 魔法少女の追いかけっこ

問題はこちら No.512 魔法少女の追いかけっこ - yukicoder追いかける側がA[i]地点にあるi番目の交差点にたどり着いた時、追いかけられる側はA[i]/X*Y地点にいる。これがA[i+1]より真に大きければ見失う。 除算をすると誤差で落とされるケースが多数あるらし…

yukicoder No.509 塗りつぶしツール

問題はこちら No.509 塗りつぶしツール - yukicoderまた、白でも黒でもない3つ目の色を赤と呼ぶことにする。 領域を「背景」「文字」「穴」の3つの領域に呼び分ける。 背景を塗りつぶすのは1回、文字をすべて塗りつぶすには文字数回、穴をすべて塗りつぶすに…

yukicoder No.508 超ゆとり教育

問題はこちら No.508 超ゆとり教育 - yukicoder 正確な値は√(N/π)だが、√(N/π)≦√N≦10^6なので、誤差制約から1~10^6の何を出力しても正解になることがわかる。 むしろ真面目に√(N/π)を計算してしまうとN≦3のときに0となってWAの原因になる。 main(){puts("1"…

yukicoder No.507 ゲーム大会(チーム決め)

問題はこちら No.507 ゲーム大会(チーム決め) - yukicoderK君以外の人のスコアを昇順にソートしておく 何点の人と組めばよいかを二分探索で求める。 X点の組がM位タイ以内に入れるというのは、X点より真に大きな点の組がM組未満であることと同値 これは尺取…

yukicoder No.504 ゲーム大会(ランキング)

問題はこちら No.504 ゲーム大会(ランキング) - yukicoder最初は1位で、自分より真に大きなスコアがでたら順位が1つ下がる。 n,s,t,rank; main(){ scanf("%d%d",&n,&s); rank=1; puts("1"); for(int i=1;i<n;i++){ scanf("%d",&t); if(t>s)rank++; printf("%d\n",rank); } } 1番目,2番目の</n;i++){>…

No.501 穴と文字列 - yukicoder

問題はこちら No.501 穴と文字列 - yukicoderできるだけ多くAを使えば良い また穴が2個,0個の文字が必要なときは、それぞれB,Cを使えば良い(辞書順最小なので)。 ・D≧Nのとき Aだけでは穴が足りないので末尾にBを増やす必要がある。 Aを1つBに取り替える毎…

yukicoder No.500 階乗電卓

問題はこちら No.500 階乗電卓 - yukicoderN≧50以上のとき、N!は2,5の素因数をそれぞれ12個以上もつのでN! mod 10^12=0 それ以下のときだけ計算すれば良い 14!<10^12<15!なので、Nが15以上のときには先頭を0埋めする long s=1,n; main(){ scanf("%ld",&n); i…

yukicoder No.499 7進数変換

問題はこちら No.499 7進数変換 - yukicoder基数変換するだけ。 ……と見せかけてN=0がコーナーケースになりうるので注意 long s,n; main(){ scanf("%d",&n); s=7; while(s<=n)s*=7; while(s/=7)putchar('0'+n/s%7); } n%7,n/=7;とすることで下の桁から順に求…

yukicoder No.498 ワープクリスタル (給料日編)

問題はこちら No.498 ワープクリスタル (給料日編) - yukicoder各クリスタルをni個使う時、それらを使う順序は(Σni)!/Π(ni!)通りある(重複順列) Niが小さいので、各クリスタルを何個使うかを全探索すればよい。for文を5重に書くのが面倒だったので以下では…

yukicoder No.496 ワープクリスタル (給料日前編)

問題はこちら No.496 ワープクリスタル (給料日前編) - yukicoderDPやるだけ #define min(p,q)(p<q?p:q) d[110][110]; x,y,n,f,a,b,c,t; main(){ scanf("%d%d%d%d",&x,&y,&n,&k); //初期化 for(int p=0;p<=x;p++)for(int q=0;q<=y;q++)d[p][q]=(p+q)*f; while(n--){ scanf("%d%d%d",&a,&b,&c); //1度しか使えないので大きい方から配る for(int p=x;p>=a;p--)for(int q=y…</q?p:q)>

yukicoder No.495 (^^*) Easy

問題はこちら No.495 (^^*) Easy - yukicoder 5文字毎に区切って2文字目をチェックすれば十分 char s[1<<17]; l,r; main(i){ gets(s); for(i=1;s[i];i+=5){ if(s[i]=='^')l++; if(s[i]=='*')r++; } printf("%d %d",l,r); } ぎゅ char s[1<<17]; l,r; main(i)…

yukicoder No.494 yukicoder

問題はこちら No.494 yukicoder - yukicoder頭から順にチェックし、'?'が何番目か見れば良い char s[]="yukicoder"; main(){ for(int i=0;1;i++){ char x=getchar(); if(x=='?'){ putchar(s[i]); return 0; } } } "yukicoder?"から1文字足りないと考えると、…

yukicoder No.492 IOI数列

問題はこちら No.492 IOI数列 - yukicodermod 101010101010101010101の方は睨むと周期性がわかる(頭のなかで筆算を思い浮かべてみる)anは初項1公比100の等比数列の第n項までの和なので、和の公式からになっていることがわかる ということで繰り返し二乗法…

yukicoder No.490 yukiソート

問題はこちら No.490 yukiソート - yukicoder 制約が小さいので、問題文の指示通りに実装すれば良い。 以下ではO(n^2)より早い解法を考える。いくつか実験してみれば分かる通り、yukiソートをおこなうと「ほぼ」通常の昇順ソートになっていることがわかる。 …

yukicoder No.491 10^9+1と回文

問題はこちら No.491 10^9+1と回文 - yukicoders<10^9に対して、s*(10^9+1)は、文字列としては「s,(いくつかの0),sを連結したもの」と一致する これが回文数であることはsが回文数であることと同値 よって問題は「N/(10^9+1)以下の回文数の個数を求めよ」と…

yukicoder No.487 2017 Calculation(2017の計算)

問題はこちら No.487 2017 Calculation(2017の計算) - yukicodermodpow関数があればそれを使うだけ #define ll long long ll modpow(ll a,ll n,int m){return n?modpow(a%m*(a%m)%m,n/2,m)*(n&1?a%m:1)%m:1;} int main(){ int m; scanf("%d",&m); printf("%d…

yukicoder No.486 3 Straight Win(3連勝)

問題はこちら No.486 3 Straight Win(3連勝) - yukicoder strstr関数を使うのが一番素直だと思う #include <string.h> int main(){ char s[110],*x,*o; gets(s); x=strstr(s,"XXX"); o=strstr(s,"OOO"); if(x==NULL&&o==NULL)puts("NA");//どっちも見つからない else i</string.h>…

yukicoder No.485 方程式のお勉強

問題はこちら No.485 方程式のお勉強 - yukicoderやるだけ B%A==0のときかつそのときに限り整数解がある int main(){ int a,b; scanf("%d%d",&a,&b); if(b%a!=0)puts("NO"); else printf("%d",b/a); return 0; } ぎゅ a;main(b){scanf("%d%d",&a,&b);a=!prin…

yukicoder No.482 あなたの名は

問題はこちら No.482 あなたの名は - yukicoder「1~Nの置換が与えられたとき、その逆置換がちょうどK個の互換の積で書けるか判定せよ」という問題 まずは与えられた置換を最も少ない個数の互換の積で書くときの個数を考える これは先頭から順に貪欲に交換し…

yukicoder No.481 1から10

問題はこちら No.481 1から10 - yukicoder和を求めて55から引くのが一番簡単なように思う int main(){ int i,t,s=0; for(i=0;i<9;i++){ scanf("%d",&t); s+=t; } printf("%d",55-s); return 0; } 入力が昇順で与えられるので、1個ずつ読み取って、食い違いが…

yukicoder No.480 合計

問題はこちら No.480 合計 - yukicoder 和の公式を使う。Nが小さいので1~Nまでをそのまま足しても間に合う int main(){ int n; scanf("%d",&n); printf("%d",n*(n+1)/2); return 0; } ゴルフ的にも特に工夫の余地はなく n;main(){n=scanf("%d",&n)>printf("…

yukicoder No.424 立体迷路

問題はこちら No.424 立体迷路 - yukicoder標準的な迷路を解く問題にちょっとだけ条件が加わったもの。 素直なDFS/BFSで解ける。以下はDFS char s[99][99]; int a[99][99],h,w; //(x,y)に到達可能かをa[x][y]に保存 void f(int p,int q){ if(!a[p][q]){ a[p]…

yukicoder No.413 +5,000,000pts

問題はこちら No.413 +5,000,000pts - yukicoder余談 サンプル出力の数がどうみても日付なのだけど、何なのかわからず気になっているので、わかる方がいましたら教えてください(※以下は試行錯誤により解く過程を記したものです。ちゃんとした解説が読みたい…

yukicoder No.467 隠されていたゲーム

問題はこちら No.467 隠されていたゲーム - yukicoder対称性からx,yは0以上としてよい ・0手で移動可能⇔原点 ・1手で移動可能⇔チェビシェフ距離がdiのいずれかと等しい であることは明らか それ以外の場合を考える。d=max{di}とする (★)チェビシェフ距離がX…

yukicoder No.477 MVP

問題はこちら No.477 MVP - yukicoder(「N人が選挙権を持っている時、上位K位以内に入るには何票獲ればよいか」という問題と同値) 「上位K位以内に入る」⇔「自分より上にK人以上いる、ということはない」なので、N/(K+1)より真に大きなダメージを与えれば…

yukicoder No.476 正しくない平均

問題はこちら No.476 正しくない平均 - yukicoderやるだけ 入力が全て整数なので、平均×個数=合計 となっているかどうかで調べると、小数を使わずに済む 10^9*10=10^10>2^32なので32bitでは足りない事に注意(撃墜ケースも用意されている) int main(){ int…

yukicoder No.478 一般門松列列

問題はこちら No.478 一般門松列列 - yukicoder要するに「長さnの数列であって、その長さ3の連続部分列のうち、門松列でないものがちょうどk個であるようなもの」を答えれば良い サンプル3を眺めると、どうやら「1,3,2,4」を繰り返したものは必ず門松列列に…

yukicoder No.457 (^^*)

問題はこちら No.457 (^^*) - yukicoder ・O(|S|^3) 各カッコ対に対して、その間に'^^*'があるかどうか判定する 当然TLE・O(|S|^2) 各'('について、そこから右に見て'^^*'があった以降にある')'の数を数える (*^^)も同様 17/01/31修正 char s[10010];i,j,L,R…

yukicoder No.456 Millions of Submits!

問題はこちら No.456 Millions of Submits! - yukicoderいろいろな知見が得られた見出し ・愚直二分探索(TLE) ・W関数を使う二分探索 ・ニュートン法(賢い) ・W関数をなんか凄い方法で求める a,bの一方が0のときは自明。そうでないとする とおく b≠0の仮…

yukicoder No.454 逆2乗和

問題はこちら No.454 逆2乗和 - yukicoder実験しながら適当に投げたら通ってしまった愚直でいけたり?→n=10^9近くまで計算しないとダメっぽい n=10^7くらいまでで様子見→サンプルに関しては10^-7を足せばちょうどいい感じ じゃあとりあえずそれを投げてみる→…

yukicoder No.117 組み合わせの数

問題はこちら No.117 組み合わせの数 - yukicoder素直に階乗で計算するだけ C(N,K)はによる単純なループによりO(K)で計算できるけど、KTが大きいのでこれではTLEになる なので、事前に階乗を計算しておけば、各クエリは定数時間で答えられるP:=10^9+7は素数…