paiza POH ec-campagne (C # / Java / Python / Ruby) # paizahack_01

problème https://paiza.jp/poh/ec-campaign
Liste de temps/C++ http://qiita.com/cielavenir/items/a61cfe8390eb16866ae5
Python/Ruby(1) http://qiita.com/cielavenir/items/b10ff4d201150f525062
C#/Java/Python/Ruby http://qiita.com/cielavenir/items/d89e85f069cf570e6786
Perl/PHP http://qiita.com/cielavenir/items/1a650a4c41d7bdd31392
JavaScript http://qiita.com/cielavenir/items/a85b985888fdc15c52b7
Go/CoffeeScript/Scala/R/Bash http://qiita.com/cielavenir/items/79016a0afd30470f440d
VB/F#/D http://qiita.com/cielavenir/items/cb6094bab56253de992c

Implémentation de l'entrée de lecture à la fois avec Python / Ruby. De plus, j'ai trouvé que C # et Java avaient une bibliothèque de recherche de 2 minutes en standard, donc je l'ai porté.

Fonctionne avec Python * 3.3

paizapoh1_read.py


#!/usr/bin/python
import sys,io,bisect
def init():
	reader = io.open(sys.stdin.fileno(),'rb',0)
	if sys.version_info[0]<3:
		s=reader.readall()
	if sys.version_info[0]>=3:
		s=str(reader.readall(),encoding='utf8')
		raw_input=input
		xrange=range
	reader.close()
	x=s.rstrip().split("\n")
	return (int(x[0].split()[0],10),[int(e,10) for e in x[1:]])

n,S=init()
v=sorted(S[0:n])
for m in S[n:]:
	r=j=0
	#k=n-1
	k=bisect.bisect_right(v,m-v[0])-1
	while j<k and v[j]+v[j+1]<=m:
		while v[j]+v[k]>m: k-=1
		if r<v[j]+v[k]:
			r=v[j]+v[k]
			if r==m: break
		j+=1
	print(r)

Ruby paiza a été mis à jour pour éliminer le besoin de définir bsearch. C'était légèrement plus rapide. Après tout, le code natif est important.

paizapoh1_read.rb


#!/usr/bin/ruby
#https://github.com/marcandre/backports/blob/master/lib/backports/2.0.0/range/bsearch.rb
unless Range.method_defined? :bsearch
  class Range
    def bsearch
      from = self.begin
      to   = self.end

      to -= 1 if exclude_end?
      satisfied = nil
      while from <= to do
        midpoint = (from + to).div(2)
        result = yield(midpoint)
        if result
          satisfied = midpoint
          to = midpoint - 1
        else
          from = midpoint + 1
        end
      end
      satisfied
    end
  end
end

S=$<.read.split("\n").map(&:to_i)
n=S[0]
v=S[1,n].sort
S[n+1..-1].each{|m|
        r=j=0
        k=((0...v.size).bsearch{|i|m-v[0]<v[i]}||v.size)-1 # upper_bound-1
        while j<k&&v[j]+v[j+1]<=m
                k-=1 while v[j]+v[k]>m
                if r<v[j]+v[k]
                        r=v[j]+v[k]
                        break if r==m
                end
                j+=1
        end
        p r
}

Java J'ai aussi mis un tri seau

paizapoh1.java


import java.util.*;
class Main{
        static final int SIZE=9999999;
        static byte[] z=new byte[SIZE];
        static int[] _v=new int[1000001],v;
        static int count=0;

        static int get(){
                int r=0;
                for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
                count++;
                return r;
        }
        public static void main(String[]Z){try{
                System.in.read(z,0,SIZE);
                int n,d,m,i,j,k,r;
                n=get();d=get();
                v=new int[n];
                for(i=0;i<n;i++)_v[get()]++;
                for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
                for(i=0;i<d;i++){
                        m=get();
                        int idx=Arrays.binarySearch(v,m-v[0]+1);
                        if(idx<0)idx=~idx;
                        for(r=j=0,k=idx-1;j<k&&v[j]+v[j+1]<=m;j++){
                                for(;v[j]+v[k]>m;)k--;
                                if(r<v[j]+v[k]){
                                        r=v[j]+v[k];
                                        if(r==m)break;
                                }
                        }
                        System.out.println(r);
                }
        }catch(Exception e){}}
}

C#

paizapoh1.cs


using System;
class PaizaPOH1{
	const int SIZE=9999999;
	//static string z;
	static byte[] z=new byte[SIZE];
	static int[] _v=new int[1000001],v;
	static int count=0;

	static int get(){
		int r=0;
		for(;'0'<=z[count]&&z[count]<='9';)r=r*10+z[count++]-'0';
		count++;
		return r;
	}
	public static void Main(){
		//z=Console.In.ReadToEnd();
		Console.OpenStandardInput().Read(z,0,SIZE);
		int n,d,m,i,j,k,r;
		n=get();d=get();
		v=new int[n];
		for(i=0;i<n;i++)_v[get()]++;
		for(i=j=0;j<1000001;j++)for(k=0;k<_v[j];k++)v[i++]=j;
		for(i=0;i<d;i++){
			m=get();
			int idx=Array.BinarySearch(v,m-v[0]+1);
			if(idx<0)idx=~idx;
			for(r=j=0,k=idx-1;j<k&&v[j]+v[j+1]<=m;j++){
				for(;v[j]+v[k]>m;)k--;
				if(r<v[j]+v[k]){
					r=v[j]+v[k];
					if(r==m)break;
				}
			}
			Console.WriteLine(r);
		}
	}
}

Recommended Posts

paiza POH ec-campagne (C # / Java / Python / Ruby) # paizahack_01
paiza POH ec-campaign (Python / Ruby) (pas bien réglé)
paiza POH paizen # paizahack_02 (Perl / PHP / Python)
Comparaison de vitesse de Python, Java, C ++
Comparaison grammaticale de base en cinq langues (C #, Java, Python, Ruby, Kotlin)
[Swift / Ruby / Python / Java] Programmation orientée objet
Sélection en plusieurs étapes (Go / C # / Ruby / Python)
Appeler popcount depuis Ruby / Python / C #
Ruby Python Java Tri insensible à la casse
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 065 C-th power
Comparaison des performances de désérialisation de msgpack (C ++ / Python / Ruby)
Résolution avec Ruby, Perl, Java et Python AtCoder ARC 098 C Somme cumulative
Résolution avec Ruby, Perl, Java et Python AtCoder CADDi 2018 C factorisation premier
Résolution avec Ruby, Perl, Java et Python AtCoder ABC 047 C Expression régulière
Résolution avec Ruby, Perl, Java et Python AtCoder ARC 066 C Hash carré itératif
À propos de l'index de liste Python (Paiza POH Lite 4: Mission 3)
Résolution avec Ruby, Perl, Java et Python AtCoder Diverta 2019 Concours de programmation Manipulation de chaînes C
notes de python C ++
python, openFrameworks (c ++)
Tendances 2014 du cadre d'application Web (PHP / Java / Ruby / Python / Perl)
Qu'est-ce que l'algorithme [Ruby / Python / Java / Swift / JS]?
Benchmarks langage C, Java, Python avec factorisation prime
AtCoder Beginner Contest 176 Explication de l '«étape» du problème C (Python3, C ++, Java)
Écrivons respectivement Python, Ruby, PHP, Java, JavaScript
Vous marchez en spirale dans un monde où les murs de la croix s'élèvent (régularité, Python / Ruby / C / C # / Java)