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

Problem https://paiza.jp/poh/ec-campaign
Zeitliste/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

Leseeingabe sofort mit Python / Ruby implementiert. Außerdem habe ich festgestellt, dass C # und Java standardmäßig eine 2-Minuten-Suchbibliothek haben, also habe ich sie portiert.

Funktioniert mit 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 wurde aktualisiert, um die Definition von bsearch zu vermeiden. Es war etwas schneller. Immerhin ist nativer Code wichtig.

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 Ich habe auch eine Eimersorte aufgestellt

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-Kampagne (C # / Java / Python / Ruby) # paizahack_01
paiza POH ec-Kampagne (Python / Ruby) (nicht gut abgestimmt)
paiza POH paizen # paizahack_02 (Perl / PHP / Python)
Geschwindigkeitsvergleich von Python, Java, C ++
Grundlegender Grammatikvergleich in fünf Sprachen (C #, Java, Python, Ruby, Kotlin)
[Swift / Ruby / Python / Java] Objektorientierte Programmierung
Mehrstufige Auswahl (Go / C # / Ruby / Python)
Rufen Sie popcount von Ruby / Python / C # auf
Ruby Python Java Sortierung ohne Berücksichtigung der Groß- und Kleinschreibung
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 065 C-te Potenz
Vergleich der Deserialisierungsleistung von msgpack (C ++ / Python / Ruby)
Lösen mit Ruby, Perl, Java und Python AtCoder ARC 098 C Kumulative Summe
Lösen mit Ruby, Perl, Java und Python AtCoder CADDi 2018 C Primfaktorisierung
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 047 C Regulärer Ausdruck
Lösen mit Ruby, Perl, Java und Python AtCoder ARC 066 C Iterativer Square Hash
Informationen zum Python-Listenindex (Paiza POH Lite 4: Mission 3)
Lösen mit Ruby, Perl, Java und Python AtCoder diverta 2019 Programmierwettbewerb C String Manipulation
Python C ++ Notizen
Python, openFrameworks (c ++)
Trends für das Webanwendungs-Framework 2014 (PHP / Java / Ruby / Python / Perl)
Was ist der [Ruby / Python / Java / Swift / JS] -Algorithmus?
C-Sprache, Java, Python-Benchmarks mit Primfaktorisierung
AtCoder Anfängerwettbewerb 176 C Problem "Schritt" Erklärung (Python3, C ++, Java)
Schreiben wir jeweils Python, Ruby, PHP, Java und JavaScript
Sie wandeln in einer Spirale in einer Welt, in der sich die Wände des Kreuzes erheben (Regelmäßigkeit, Python / Ruby / C / C # / Java)