Skip to content

Instantly share code, notes, and snippets.

@na2hiro
Last active December 30, 2015 16:49
Show Gist options
  • Save na2hiro/7857455 to your computer and use it in GitHub Desktop.
Save na2hiro/7857455 to your computer and use it in GitHub Desktop.
リクルートプログラミングコンテスト5完でアメリカを惜しくも逃しました. http://recruit-jinji.jp/procon/index.html 慣れなさの見える前ファイルコピペで補助関数が使いもしないのに増殖していっています.
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);
}
});
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;
}
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;
}
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;
}
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;
}
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