今更気づいたけど、ZOJ3123って蟻本に載ってる問題じゃん。どや顔でO(nlogn)解法書いたけど、O(n)解法がのってるやん…。

問題 シーザーは兵士を整列させるのが大好きで、n1人の歩兵とn2人の騎兵を所有しています。彼にはこだわりがあって、k1人より多く歩兵が連続して並んでいたり、k2人より多く騎兵が連続して並んでいるのは、美しくない並び方だと思っています。n1,n2,k1,k2が…

問題 自然数nが与えられる。各桁が0と1だけで表される数が、1からnの範囲にいくつあるか答えよ。(n 解法 2進表記を10進数とみなした数を作って比較する。 コード int tob(int n){ int b = 0; stack<int> stk; while(n){ stk.push(n%2); n/=2; } while(!stk.empty(</int>…

問題 バーランド国は新しい硬貨を作ろうと考えた。その硬貨は、それよりも安いすべての硬貨で割り切れるものでなくてはならない。一番高い硬貨の値が与えられるので、なるべく硬貨の数が多くなるように硬貨を構成せよ。 解法 1になるまで、割れる素数で割っ…

問題 n人の男と、m人の女がいる。t人の選び方が何通りあるか求めよ。ただし、t人の中に少なくとも4人の男と1人の女が含まなければならない。(n,m 解法 combinationを使って計算。 コード int main(){ ll comb[50][50]; REP(i,50)comb[i][0] = comb[i][i] = 1…

問題 122344→11221324のような変換をする。(1個の1,2個の2,1個の3,2個の4).。 コード int main(){ int n; cin>>n; while(n--){ string s; cin>>s; s += '#'; int count = 1; FOR(i,1,s.size()){ if(s[i]!=s[i-1]){ printf("%d%c",count,s[i-1]); count = 1; …

ZOJ :: Problems :: Show Problem 問題 n個の文字列が与えられる。ある文字列が、もう一方の文字列のprefixになるような２つの文字列が存在するか判定する。 解法 O(n^2)の全探索だと間に合わない。sortして隣り合う文字列を調べるとo(nlogn)で判定できる。 …

問題 多項式の微分をする。入出力は係数。 解法 やるだけ。 コード int main(){ int T; cin>>T; while(T--){ int n; cin>>n; REP(i,n){ int C; cin>>C; printf("%d",C*(n-i)); putchar((i==n-1)?'\n':' '); } if(!n)cout<<0<<endl; cin>>n; } return 0; }</endl;>

問題 長さNの数列a[0],..,a[N]が与えられる。総和がSを超えるような連続する部分列の、最小の長さを求めよ。 解法 まず部分和sを計算する(s[i+1] = s[i] + a[i], s[0] = 0)。 するとa[i],...,a[j]の総和はs[j+1]-s[i]となるので、始点iを決めると、終点はS+s…

問題 問題文読んで。 解法 色の変化をdfsする。隣接するマスの判定もdfsで。 コード int h,w,c; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int p[8][8]; bool ck[8][8]; bool valid(int x, int y){ return x>=0&&x<w&&y>=0&&y</w&&y>

問題 括弧のバランスがとれているか判定。 解法 左括弧ならstackに入れ、右括弧ならstackから取り出す。 左括弧と右括弧の対応が違っていたり、左括弧が余っていたり、右括弧が多すぎたりすればNG コード bool solve(string str){ map<char, int> t; t['['] = 1; t[']']</char,>…

問題 整数nに対し、n 解法 試し割りで素数判定 コード bool isPrime(int n){ for(int i = 2; i*i<=n; i++){ if(n%i == 0) return false; } return true; } int main(){ int n; while(cin>>n,n){ int ans = 0; FOR(i,n+1,2*n+1){ if(isPrime(i))ans++; } cout<

式をぼーっと眺めてると A_(n+1) = A_n + 2*B_n, B_(n+1) = A_n + B_nだと気づいたのでそのとおりに書いた。 a = 3 b = 2 count = 0 1000.times{ count += 1 if a.to_s.size > b.to_s.size a, b = a + 2*b, a + b } puts count

通らないと思ってたepochの予選が去年についで今年も無事通過しました。予想外なのでかなりうれしい。なぜ通らないと思ってたかはあとから書きます。 相方は@wand125(id:w125)で、チーム名はもふもふあるぱか。去年のチーム名はふわふわどーなつでした。由来…

#include <iostream> #include <sstream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define FOR(i,k,n) for(int i=(k); i<(int)n; ++i) #define REP(i,…</cmath></cstring></cstdlib></cstdio></map></set></queue></vector></algorithm></string></sstream></iostream>

#! /usr/bin/env ruby # coding: utf-8 text = gets.chomp asciis = text.split(',').map{|c| c.to_i} 'aaa'.upto('zzz'){|word| key = word.bytes.to_a str = asciis.zip(key.cycle).map{|c| (c[0]^c[1]).chr}.join if str.index("this") and str.index("th…

#! /usr/bin/env ruby # coding: utf-8 def count(n) return 0 if(n < 1) 1.upto(10){|x| y = x**n if y >= 10**(n-1) return 9 - x + 1 end } end n = 1 ans = 0 loop do break if count(n) == 0 ans += count(n) n += 1 end puts ans

#! /usr/bin/env ruby # coding: utf-8 require 'prime' require 'bsearch' primes = [] #4桁の素数リスト Prime.each{|prime| if prime > 10000 break elsif prime > 1000 primes.push(prime) end } primes.combination(2){|p1,p2| p3 = 2*p2 - p1 #p1,p2,p…

A time = hours * 60 + minutes に変換する。 int rev(int n){ return (n/10)+10*(n%10); } int main(){ int time,h,m; scanf("%d:%d",&h,&m); time = 60*h+m; while(true){ time = (time+1)%(24*60); h = time/60; m = time%60; if(rev(h)==m){ printf("%02…

問題文三行って短すぎじゃありませんか。ねえ。 144/250 入力のサイズは10^9だから一つずつチェックするのはさすがにだめか 4か7だけだから先に全通り作れそう stringとbit演算を使った rng_58さんのを見たらもっとうまい方法があった

この時期のSRMは問題分が短いのが多い気がする。読みやすいのはいいけど、内容を理解するのに時間がかかってしまう…。 こんかいは２問めが450だったので解けるかと思ったけど、無理だった。div1midはやる気が出ないので、これから250だけを解くことに決めた…

一昨日は、AOJ,euler,topcoderを一題ずつ解くと言いましたが、さっそく昨日はやりませんでした。

div1 easy 400も401も問題文短い 難しい 寝る 翌朝考えてみると案外簡単だった メモ化再帰した

div1 easy 問題 数字n(2素数 q:2以上の整数)となるようなp,qが存在するか判定し、存在すればp,qを返す。 解く q>=2だからpは10^9以下 2^60>10^18だからqは60以下 n^(1/i)を求めて、n^(1/i)が整数であり素数であればp=n^(1/i) q = iが答え 整数かどうかはn^(1…

0090 交点の位置を計算して、その点が含まれる円の数を数えればよい。答えの最小値が1であることに注意。この問題はながらく解けてなくて、この解法は検索して調べたものです。 0121 状態数が8!=40320なので、各状態のそれぞれの答えをgoalを初期状態とするb…

ついに春休みがやって来ました。今日は二日目。もうすぐ２回生になるんだと思うとなんだか寂しい気もする。 特に春休みにすることもないので、できるだけ毎日やるタスクを決めた。といってもAOJとeulerとtopcoderの問題を１題以上解くだけ。休みは60日近くあ…

寝起き30分後ながら参戦した。 275でまともな解法が思いつかず0点だった。最大パターンと最小パターンで比較すればいいらしい。それがわかったら簡単。たぶん。 ratingは1342->1275。なんとかdiv1残留した。

MacBook Air 11インチ欲しい！