メモ

yukicoderでゆるふわgolf

2016-05-20から1日間の記事一覧

yukicoder No.256 桁の数字を入れ替え (2)

問題はこちら No.256 桁の数字を入れ替え (2) - yukicoder任意に並び替えられるので元の並びは関係ない なので各数字がいくつ登場するかを記録して、大きい数から上位に配置していけば良い int main(){ int a[10],i; char s[100010]; gets(s); for(i=0;s[i];…

yukicoder No.254 文字列の構成

問題はこちら No.254 文字列の構成 - yukicoder初見では解けずに解説を読んでしまったのだけど、見事な解説が書いてあって思わずなるほどとうなってしまった。 以下ではその解説の方針に従うabab…babaと、a,bが交互に並ぶ文字列はaがn文字ある時、yukicoder …

yukicoder No.253 ロウソクの長さ

問題はこちら No.253 ロウソクの長さ - yukicoderyukicoder No.246 質問と回答 - メモとほとんど同じ ただし単純な2分探索では、例えばXが10の時、特定する前にロウソクが燃え尽きてしまい、11と区別ができず困るということで小さい値は最初に分けておく 最…

yukicoder No.251 大きな桁の復習問題(1)

問題はこちら No.251 大きな桁の復習問題(1) - yukicoderやることはyukicoder No.167 N^M mod 10 - メモと同じ N^Mをmod pで求めるのには Nはmod pの情報が Mはオイラーの定理(あるいはフェルマーの小定理)からmod p-1の情報があれば良い N,Mとも巨大な数な…

yukicoder No.249 N言っちゃダメゲーム (2)

問題はこちら No.249 N言っちゃダメゲーム (2) - yukicoder問題文中に「このゲームは、NとKが決まったら、先手・後手、どちらが勝つかわかることが知られています」とあるがこれは厳密には誤りで、正しくは"互いに最善手を尽くすなら"という条件が必要。 今…

yukicoder No.247 線形計画問題もどき

問題はこちら No.247 線形計画問題もどき - yukicoder問題は次のように読み替えられる 「a[i]円玉がたくさんあるとき、ちょうどC円を払うために必要な硬貨の枚数は最小でいくらか?」 ということで配るDPで書くことができる #define inf 1000000 //解が存在…

yukicoder No.246 質問と回答

問題はこちら No.246 質問と回答 - yukicoder二分探索(10^9<2^30) 整数の二分探索といえば普通は終了条件high-low>1にして(low,high)を (low+(high-low)/2,high)か(low,high-(high-low)/2)に更新していくのだけど d=high-lowとして終了条件をd>0、(low,d)…

yukicoder No.244 ★1のグラフの問題

問題はこちら No.244 ★1のグラフの問題 - yukicoder辺を動いて行き来できる頂点集合を島と呼ぶことにする 問題は「N頂点を1つの島にするには最低何本の辺が必要か?」 2つの島があった時、それぞれの島に属する頂点を1つずつ選び、その2頂点間を辺で結ぶと…

yukicoder No.242 ビンゴゲーム

問題はこちら No.242 ビンゴゲーム - yukicoder5数の組み合わせは通りあり、 N個の数でビンゴになるような5数の組み合わせが通りあるので 各列についてN個目までにビンゴになる確率は5×5のカードは縦横斜めで12ビンゴできるので期待値の線形性より求めるもの…

yukicoder No.240 ナイト散歩

問題はこちら No.240 ナイト散歩 - yukicoder解説には「深さ優先探索」「幅優先探索」の練習問題とあったので、とりあえず深さ優先で実装してみる int x,y, a[8]={1,2,2,1,-1,-2,-2,-1}, b[8]={2,1,-1,-2,-2,-1,1,2}; void f(int p,int q,int n){ //n回動い…

yukicoder No.239 にゃんぱすー

問題はこちら No.239 にゃんぱすー - yukicoder各文字列を読み込んでstrcrpで"nyanpass"と比較し、各人物が何回"nyanpass"と言っているか調べる 全員に対して"nyanpass"と言えば、その回数はN-1になっているので そのような人物がちょうど1人いるかどうかを…

yukicoder No.237 作図可能性

問題はこちら No.237 作図可能性 - yukicoder問題文からリンクされている定規とコンパスによる作図 - Wikipediaによれば、n≧3に対し、正n角形が作図可能であることの必要十分条件は nが0個以上の相異なるフェルマー素数と2ベキ(1含む)の積で表されているこ…