-
-
Save na2hiro/7857455 to your computer and use it in GitHub Desktop.
リクルートプログラミングコンテスト5完でアメリカを惜しくも逃しました.
http://recruit-jinji.jp/procon/index.html 慣れなさの見える前ファイルコピペで補助関数が使いもしないのに増殖していっています.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
for(var i=0; i<t; i++){ | |
var line = texts[2*i+2]; | |
// console.log(line); | |
hash = {}; | |
line.split(" ").forEach(function(n){ | |
if(!hash[n[0]]){ | |
hash[n[0]]=parseInt(n, 10); | |
}else{ | |
hash[n[0]]+=parseInt(n, 10); | |
} | |
}); | |
// console.log(hash); | |
var max = 0; | |
for(var j in hash){ | |
max = Math.max(hash[j], max); | |
} | |
console.log(max); | |
} | |
}); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
var cnt=1; | |
for(var i=0; i<t; i++){ | |
var hannin=texts[cnt++]; | |
var hanninlen = text2length(hannin); | |
var num = texts[cnt++]; | |
var suslen=10000; | |
var sus = ":"; | |
for(var j=0; j<num; j++){ | |
var te = texts[cnt++].split(" "); | |
var kouho = te[0]; | |
var kouholen = text2length(te.slice(1, te.length).join(" ")); | |
if(sa(kouholen, hanninlen)<sa(suslen, hanninlen)){ | |
suslen = kouholen; | |
sus=kouho; | |
} | |
} | |
console.log(sus.substr(0, sus.length-1)); | |
} | |
}); | |
function sa(a, b){ | |
var k = a-b; | |
if(k<0) return -k; | |
return k | |
} | |
function text2length(text){ | |
var words=text.split(" "); | |
return words.map(function (word){return word.length}).reduce(function(a, b){return a+b;})/words.length; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
var cnt=1; | |
for(var i=0; i<t; i++){ | |
var n=parseInt(texts[cnt++]); | |
var te = texts[cnt++]; | |
var res = []; | |
for(var xx=0; xx<n; xx++) res.push(0); | |
var teban = 0; | |
var cs = te.split(""); | |
foo: for(var ii=0; ii<cs.length; ii++){ | |
switch(cs[ii]){ | |
case "X": | |
while(isNaN(parseInt(cs[++ii], 10))){ | |
if(ii>=cs.length) break foo; | |
} | |
res[teban]*=parseInt(cs[ii]); | |
break; | |
case "D": | |
while(isNaN(parseInt(cs[++ii], 10))){ | |
if(ii>=cs.length) break foo; | |
} | |
res[teban]=floor(res[teban]/parseInt(cs[ii])); | |
break; | |
case "S": | |
while(isNaN(parseInt(cs[++ii], 10))){ | |
if(ii>=cs.length) break foo; | |
} | |
res[teban]-=parseInt(cs[ii]); | |
break; | |
default: | |
// console.log(cs[ii]) | |
res[teban]+=parseInt(cs[ii], 10) | |
break; | |
} | |
teban++; | |
if(teban==n) teban=0; | |
} | |
console.log(max(res)); | |
} | |
}); | |
function floor(n){ | |
if(n<0) n=-n; | |
return Math.floor(n); | |
} | |
function max(arr){ | |
var m=arr[0]; | |
for(var i=1; i<arr.length; i++){ | |
if(m<arr[i]) m=arr[i]; | |
} | |
return m | |
} | |
function sa(a, b){ | |
var k = a-b; | |
if(k<0) return -k; | |
return k | |
} | |
function text2length(text){ | |
var words=text.split(" "); | |
return words.map(function (word){return word.length}).reduce(function(a, b){return a+b;})/words.length; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
var cnt=1; | |
top: for(var i=0; i<t; i++){ | |
var n=parseInt(texts[cnt++]); | |
// console.log(n) | |
var map = []; | |
for(var ii=0; ii<200; ii++){ | |
var tmp = []; | |
for(var jj=0; jj<200; jj++){ | |
tmp.push(0); | |
} | |
map.push(tmp); | |
} | |
var nss = []; | |
for(var j=0; j<n; j++){ | |
var ns = texts[cnt++].split(" ").map(function (n){return parseInt(n, 10)}); | |
// console.log(ns) | |
nss.push(ns); | |
for(var x=0; x<ns[2]; x++){ | |
for(var y=0; y<ns[3]; y++){ | |
map[ns[0]+x][ns[1]+y]++; | |
} | |
} | |
} | |
// console.log(map) | |
var found=false; | |
now: for(var j=0; j<nss.length; j++){ | |
var ns = nss[j]; | |
for(var x=0; x<ns[2]; x++){ | |
for(var y=0; y<ns[3]; y++){ | |
if(map[ns[0]+x][ns[1]+y]==1){ | |
continue now; | |
} | |
} | |
} | |
// console.log("found", ns) | |
found=true;break; | |
} | |
console.log(found?"TRUE":"FALSE") | |
} | |
}); | |
function floor(n){ | |
if(n<0) n=-n; | |
return Math.floor(n); | |
} | |
function max(arr){ | |
var m=arr[0]; | |
for(var i=1; i<arr.length; i++){ | |
if(m<arr[i]) m=arr[i]; | |
} | |
return m | |
} | |
function sa(a, b){ | |
var k = a-b; | |
if(k<0) return -k; | |
return k | |
} | |
function text2length(text){ | |
var words=text.split(" "); | |
return words.map(function (word){return word.length}).reduce(function(a, b){return a+b;})/words.length; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
win = 15/36; | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
var cnt=1; | |
top: for(var i=0; i<t; i++){ | |
var l=texts[cnt++].split(" "); | |
var A = parseInt(l[0], 10); | |
var N = parseInt(l[1], 10); | |
var teki = 0; | |
for(var j=0; j<N; j++){ | |
teki+=parseInt(texts[cnt++], 10); | |
} | |
// console.log("calc", A, teki) | |
var map = []; | |
for(var ii=0; ii<=teki; ii++){ | |
var tmp = []; | |
for(var jj=0; jj<=A; jj++){ | |
tmp.push(0); | |
} | |
map.push(tmp); | |
} | |
map[0][0]=1 | |
for(var dan=0; dan<=A+teki; dan++){ | |
for(var x=0; x<=dan; x++){ | |
if(x>=teki || dan-x>=A) continue; | |
map[x+1][dan-x]+=map[x][dan-x]*win | |
// console.log(x, ",", dan-x); | |
map[x][dan-x+1]+=map[x][dan-x]*(1-win); | |
} | |
} | |
// console.log(map); | |
var res = 0; | |
for(var j=0; j<A; j++){ | |
res+=map[teki][j]*(A-j); | |
} | |
console.log(res); | |
} | |
}); | |
function nCk(n, k){ | |
var ret = 1; | |
for(var i=n-k+1; i<=n; i++){ | |
ret*=i; | |
} | |
for(var i=1; i<=k; i++){ | |
ret/=i | |
} | |
return ret; | |
} | |
function floor(n){ | |
if(n<0) n=-n; | |
return Math.floor(n); | |
} | |
function max(arr){ | |
var m=arr[0]; | |
for(var i=1; i<arr.length; i++){ | |
if(m<arr[i]) m=arr[i]; | |
} | |
return m | |
} | |
function sa(a, b){ | |
var k = a-b; | |
if(k<0) return -k; | |
return k | |
} | |
function text2length(text){ | |
var words=text.split(" "); | |
return words.map(function (word){return word.length}).reduce(function(a, b){return a+b;})/words.length; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var rl = require("readline"); | |
var repl = rl.createInterface(process.stdin, process.stdout); | |
var input=""; | |
repl.on("line", function(text){ | |
input+=text; | |
}); | |
repl.on("close", function(){ | |
var texts = input.split("\n"); | |
var t = parseInt(texts[0], 10); | |
// console.log(t) | |
var cnt=1; | |
top: for(var i=0; i<t; i++){ | |
var N = parseInt(texts[cnt++], 10); | |
// console.log(N) | |
var words=[]; | |
for(var j=0; j<N; j++){ | |
words.push(texts[cnt++]); | |
} | |
// console.log("words", words); | |
var lines = []; | |
forwords: for(var j=0; j<words.length; j++){ | |
var word = words[j]; | |
// console.log("word", word) | |
var found=null; | |
for(var index=0; index<lines.length; index++){ | |
var line = lines[index]; | |
for(var pos=0; pos<word.length; pos++){ | |
var chr = word[pos]; | |
// console.log("lines", lines) | |
if(line.indexOf(chr)>=0){ | |
/* 注*ここでIMPOSSIBLE投げてたものを終了後に直しました */ | |
if(found!=null && found!=index){ | |
//impossible | |
lines[index] = append(lines[found], lines[index]); | |
lines[found]=""; | |
} | |
found=index; | |
// console.log("found",found) | |
} | |
} | |
} | |
if(found==null){ | |
// console.log("not found", word); | |
lines.push(word); | |
}else{ | |
// console.log("add to found elem", word); | |
lines[found] = append(lines[found], word); | |
} | |
} | |
var nums = lines.map(function(str){return str.length}); | |
console.log(lines, nums) | |
var res = knapsack(lines) | |
if(res==null){ | |
console.log("IMPOSSIBLE"); | |
continue; | |
} | |
console.log(addOthers(res).join(" ")) | |
} | |
}); | |
function addOthers(keys){ | |
// console.log(keys) | |
var used = keys.join(""); | |
var all = "abcdefghijklmnopqrstuvwxyz"; | |
var unused = sa(all, used).join(""); | |
var l0=keys[0].length | |
var l1=keys[1].length | |
var l2=keys[2].length | |
var must0 = 10-l0; | |
var must1 = 9-l1; | |
var must2 = 7-l2; | |
keys[0]+=unused.substr(0, must0); | |
keys[1]+=unused.substr(must0, must1); | |
keys[2]+=unused.substr(must0+must1); | |
// console.log(keys.join("").split("").sort().join("")) | |
// console.log(keys) | |
return keys | |
} | |
function sa(a1, a2){ | |
var ret = []; | |
for(var i=0; i<a1.length; i++){ | |
if(a2.indexOf(a1[i])==-1) ret.push(a1[i]); | |
} | |
return ret; | |
} | |
function knapsack(arr){ | |
return knapsack2(arr, ["", "", ""]); | |
} | |
function knapsack2(arr, results){ | |
if(results[0].length>10 || results[1].length>9 || results[2].length>7) return null; | |
// console.log("kna",arr, results) | |
if(arr.length==0){ | |
return results; | |
} | |
var word=arr[0]; | |
var remain = arr.slice(1); | |
for(var i=0; i<results.length; i++){ | |
var oldr = results[i]; | |
results[i]+=word; | |
var res = knapsack2(remain, results); | |
if(res) return res; | |
results[i]=oldr; | |
} | |
return null; | |
} | |
function append(str1, str2){ | |
var a=str1.split("").concat(str2.split("")).sort(); | |
var ret = [a[0]]; | |
for(var i=1; i<a.length; i++){ | |
if(a[i]!=a[i-1]) ret.push(a[i]); | |
} | |
return ret.join(""); | |
} | |
function nCk(n, k){ | |
var ret = 1; | |
for(var i=n-k+1; i<=n; i++){ | |
ret*=i; | |
} | |
for(var i=1; i<=k; i++){ | |
ret/=i | |
} | |
return ret; | |
} | |
function floor(n){ | |
if(n<0) n=-n; | |
return Math.floor(n); | |
} | |
function max(arr){ | |
var m=arr[0]; | |
for(var i=1; i<arr.length; i++){ | |
if(m<arr[i]) m=arr[i]; | |
} | |
return m | |
} | |
function text2length(text){ | |
var words=text.split(" "); | |
return words.map(function (word){return word.length}).reduce(function(a, b){return a+b;})/words.length; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment