読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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は素数…

yukicoder No.453 製薬会社

問題はこちら No.453 製薬会社 - yukicoder線形計画法とか知らないけど数学で殴るだけ製品Aをxkg、製品Bをykgつくるとすると、問題は 3/4*x+2/7*y≦C 1/4*x+5/7*y≦D x,y≧0 の条件下で1000*x+2000*yを最大化する問題 厳密な証明を書くのが面倒くさくなったので…

yukicoder No.429 CupShuffle

問題はこちら No.429 CupShuffle - yukicoder上下からシミュレーションするだけ 上から順に??の直前までやり、下から順に??の直前までやれば、その前後で変化している場所が答えだとわかる #define swap(x,y)(t=x,x=y,y=t) int main(){ int a[100010],b[1000…

yukicoder No.446 ゆきこーだーの雨と雪 (1)

問題はこちら No.446 ゆきこーだーの雨と雪 (1) - yukicoder0~12345のいずれかと文字列として一致しているかどうかを調べるだけ c++ならto_string関数なるものがあるらしいが、cにはない 文字列を数値にするならatoiという関数があるのでitoaとかないのかと…

yukicoder No.445 得点

問題はこちら No.445 得点 - yukicoder定義式に従って実装するだけ…… と思わせて、小数で誤差が発生する場合がある(challengeケースを参照) そういうわけで、小数を使わないように、式をちょっと変形する int main(){ int n,k; scanf("%d%d",&n,&k); print…

yukicoder No.442 和と積

問題はこちら No.442 和と積 - yukicoderA*Bが64bitに収まらないので、多倍長を持ち出すか、なんか考えないといけない D=gcd(A,B)とし、A=Da、B=Dbとする。ここでa,bは互いに素となる。 gcd(A+B,AB)=gcd(D(a+b),DDab)=D*gcd(a+b,Dab) であり、a,bが互いに素…

yukicoder No.450 ベー君のシャトルラン

問題はこちら No.450 ベー君のシャトルラン - yukicoder2台の電車がすれ違うまでの時間をTとする。 ベー君は速度wで時間Tだけ移動するので総移動距離は明らかにwT。 T=d/(vl+vr)であることから直ちに計算できる。 int main(){ double vl,vr,d,w; scanf("%lf…

yukicoder No.441 和か積

問題はこちら No.441 和か積 - yukicoder場合分けをすれば簡単に分かる。 必要ならAとBを入れ替えることでA≦Bと仮定して良い ・Aが0のとき Bも0なら'E'、さもなくば'S' ・Aが1のとき 必ず'S' ・Aが2のとき Bも2なら'E'、さもなくば'P' ・Aが3以上のとき 必ず…

yukicoder No.437 cwwゲーム

No.437 cwwゲーム - yukicoderdfsするだけ Nの桁数は高々13なので、適当にやってもどうにかなる #define max(p,q)p<q?p=q:0 char s[99]; //今まで使った数を引数とし、残りの数で作れる最大の値を返す関数 int f(used){ int i,j,k,t,m=0; for(i=0;s[i];i++)for(j=i+1;s[j];j++)for(k=j+1;s[k];k++){ if(used>>i&1||used>>j&1||used>>k&1||s[i]=='0'||s[i]==s[j]||s[j]!=s[k])continue; //…</q?p=q:0>

yukicoder No.436 ccw

問題はこちら No.436 ccw - yukicoderやるだけ cが2個以上かつwが1個以上あることがccwが存在するための必要十分条件なので、cを1個以下にするかwをすべて消すか。 つまり「cの個数-1」「wの個数」のminが答え #define min(p,q)(p

yukicoder No.78 クジ付きアイスバー

問題はこちら No.78 クジ付きアイスバー - yukicoder制約が大きいので愚直にシミュレーションすると通らない……はずなのだけど、Cは速いからギリギリ通っちゃうんだなこれが char box[60]; int n,k,cost,stock,p; int main(){ scanf("%d%d%s",&n,&k,box); whi…

yukicoder No.181 A↑↑N mod M

問題はこちら No.181 A↑↑N mod M - yukicoderよく考えればそんなに難しくなくない…?と最初は思ったけれど、考えれば考えるほど泥沼になるタイプの問題だったm=1のとき、及び、n≦2のときは明らか。そうでないとする。 a↑↑nを返す関数をtetra(a,n)、a↑↑n mod …

yukicoder No.291 黒い文字列

問題はこちら No.291 黒い文字列 - yukicoderDPの状態遷移を考えるのに2時間くらいかかってしまった……dp[i][a][b][c][d]=(i文字目まで見て、Kがa個、内KUがb個、内KURがc個、内KUROがd個あるときのKUROIの内数) として配るDPを考える K,U,R,O,Iの各文字がき…

yukicoder No.372 It's automatic

問題はこちら No.372 It's automatic - yukicoderdp[i][j]を「i文字目までを使って作れる数の内、mod Mでjであり、先頭が0(0のみを含む)でなく、空文字列でもないものの個数」として配るDPを考える (i+1)文字目の数をcとすると、dp[i+1]は次のように作られる…

yukicoder No.432 占い(Easy)

問題はこちら No.432 占い(Easy) - yukicoder問題文のとおりに操作をすれば良い char s[1010]; int main(){ int i; gets(s); for(;gets(s);){ while(strlen(s)>1){ for(i=0;i<strlen(s)-1;i++){ s[i]+=s[i+1]-'0'; if(s[i]>'9')s[i]-=9; } s[i]='\0'; } puts(s); } return 0; } まず何の工夫もなく縮めて c</strlen(s)-1;i++){>…

yukicoder No.435 占い(Extra)

問題はこちら No.435 占い(Extra) - yukicoderyukicoder No.434 占い - メモと全く同じ x,a,b,m,n,i,t,ans,c,c3; inv9[]={0,1,5,0,7,2,0,4,8}; f3(n){int i=0;for(;n&&n%3==0;n/=3)i++;return i;} g3(n){for(;n&&n%3==0;n/=3);return n;} main(){ for(gets(&…

yukicoder No.434 占い

問題はこちら No.434 占い - yukicoder い 手順3の「できた数が2桁なら十の位と一の位を足す」という操作は9での剰余を求めることとほぼ等しいことに注意すれば、途中で行われる操作が加算のみであることから、これは最後にまとめてすれば良い。 よって(Σs[i…

yukicoder No.431 死亡フラグ

問題はこちら No.431 死亡フラグ - yukicoderやるだけ 生存するのは、死亡フラグの合計が2未満or生存フラグが1 int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); puts(a+b+c<2|d?"SURVIVED":"DEAD"); return 0; } 少し読み替えて、フラグの合計が2…

yukicoder No.425 ジャンケンの必勝法

問題はこちら No.425 ジャンケンの必勝法 - yukicoder1回目: 勝ち→1/3 負け→1/3 あいこ→1/3なので「前回があいこで、今回必勝法を使う確率がpのときに勝つ確率」をf(p)とすると、求めるべきは当然 1/3+1/3*f(p) となる。前回があいこで、今回必勝法を使う確…

yukicoder No.420 mod2漸化式

問題はこちら No.420 mod2漸化式 - yukicoder/2と%2が並んでいるところを見るといかにも2進法っぽい。 ということで、2進法化した数をfに放り込んだところを想像すると、結局fはbitpop数を数える関数であることが分かる ・個数 0bit目から30bit目までのどのb…

yukicoder No.428 小数から逃げる夢

問題はこちら No.428 小数から逃げる夢 - yukicoderCではたとえ整数でも190桁の数をそのまま扱うことはできないので工夫が必要 幸いNが小さいので、多倍長の乗算のためのなにがしかを持ち出さなくても1桁ごとに筆算していけば良い int main(){ char ans[999…

yukicoder No.427 テレビ

問題はこちら No.427 テレビ - yukicoder H:Wは3:4か4:3なので、大小関係をチェックするだけでよい x;main(y){x=scanf("%d%d",&x,&y)>puts(x

yukicoder No.423 ハムスター語初級(数詞)

問題はこちら No.423 ハムスター語初級(数詞) - yukicoder入力の末尾に"ham"をつけるだけ……ではない 入力が0のとき、かつその時に限り、入力をそのまま出力することになる char s[99]; main(){ gets(s); printf(strcmp(s,"ham")?"%sham":"%s",s); return 0…

yukicoder No.406 鴨等間隔の法則

問題はこちら No.406 鴨等間隔の法則 - yukicoder定義どおりやるだけ ソートして、その間隔が一定かつ0でないことを確かめれば良い c(int*a,int*b){return *a-*b;} int main(){ int x,a[1<<17],s,i,n,f; scanf("%d",&n); for(i=0;i

yukicoder No.415 ぴょん

問題はこちら No.415 ぴょん - yukicoderindexを1ずらして0-basedとする 一度スタートすると同じ方向に進み続けるしかないのでi回目の移動先はi*D%N よって求めるべきはi*D%Nが0となる最小の非負整数iから1引いたもの(実際に移動できる回数なので) 即ちi*D…

yukicoder No.414 衝動

問題はこちら No.414 衝動 - yukicoder素数判定するだけ Mが2や3のときも気にしなくて良い int main(){ long m,i; scanf("%ld",&m); for(i=2;i*i<=m;i++)if(m%i==0)break; if(m%i==0)printf("%ld %ld",m/i,i); else printf("%ld 1",m); return 0; } 出力をい…

yukicoder No.405 ローマ数字の腕時計

問題はこちら No.405 ローマ数字の腕時計 - yukicoder 負の数の剰余にだけ注意すれば良い char a[][5]={"I","II","III","IIII","V","VI","VII","VIII","IX","X","XI","XII"},b[]; i; main(x){ for(scanf("%s%d",b,&x);strcmp(b,a[i++]);); i=!puts(a[(x+i+11…

yukicoder No.419 直角三角形

問題はこちら No.419 直角三角形 - yukicoder必要ならaとbを入れ替えることでa≦bとする 当然、斜辺は他の2辺より長いことに注意する a≠bのとき、bを斜辺とすることで最後の一辺は√(b*b-a*a)となる a=bのとき、a,bを斜辺にすることは出来ないので、最後の一…

yukicoder No.418 ミンミンゼミ

問題はこちら No.418 ミンミンゼミ - yukicoderSはミーン文字列の結合であり、ミーン文字列には'n'がちょうど1つ含まれることから、nの個数を数えれば良い int main(){ char c[110]; int i,s=0; gets(c); for(i=0;c[i];i++)if(c[i]=='n')s++; printf("%d",s)…

yukicoder No.410 出会い

問題はこちら No.410 出会い - yukicoderマンハッタン距離÷2するだけ a,b,c; main(d){a=scanf("%d%d%d%d",&a,&b,&c,&d)>printf("%f",(abs(a-c)+abs(b-d))/2.);} 83B

yukicoder No.61 リベリオン

問題はこちら No.61 リベリオン - yukicoder格子点を「通過」する判定はめんどくさいので、弾の速度をgcd(Vx,Vy)で割り、制限時間をその分伸ばすことにする 反射を考えるのは面倒なので、x軸y軸の各方向を2倍にしてループしていると考えるいつものやつ 格子…

yukicoder No.411 昇順昇順ソート

問題はこちら No.411 昇順昇順ソート - yukicoderが昇順昇順列である 定義よりはそれぞれ昇順列であることに注意せよ1~Nの置換である昇順昇順列のうち、であるものの個数を求めよ、という問題である条件をみたすような昇順昇順列をとる を満たすjをとり、と…

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…