ABC033 に参加しました - 名もなき未知

3.3完，90位．A問題で2WAとか，C問題で1WAとかもったいなくない？？

続きからどうぞ

今回，様々な言語で書いてみようみたいなコンセプトでA問題，C問題は解いてみたので，いろいろ書いてみようと思います．

A問題

問題文
abc033.contest.atcoder.jp

解答

Python

Submission #629064 - AtCoder Beginner Contest 033 | AtCoder

Ruby

Submission #630193 - AtCoder Beginner Contest 033 | AtCoder

Bash

Submission #630232 - AtCoder Beginner Contest 033 | AtCoder

Perl

Submission #630656 - AtCoder Beginner Contest 033 | AtCoder

Perlに関しては以下のサイトを参考にしました．（Atcoderのショートコードでよく見る人のブログですね… ブログ書かれていたんだ…）

AtCoder での Perl golf に関するメモ - 37.50.48 https://t.co/7AG55vPwAG
これを読みながらなるほどと言っていた
— yumechiさん (@yumechi0525) 2016, 2月 6

i-i.hatenablog.jp

というわけで，4言語で解答を作りました（？）．

解決方針としては，解答スライド通り，1111の剰余を求める（Bash, Ruby, Perlのコードがそれに当たります)のが定石だと思います．ただ，比較結果として，0以外ならtrueとする言語とそうでない言語があるので，注意が必要です．多分Rubyはちゃんと比較しないとまずいはずです．

ほらね↓（Rubyはちゃんと0と比較しないとダメです）
Submission #631975 - AtCoder Beginner Contest 033 | AtCoder

解答スライドでは，a[0]==a[1]&&a[1]==a[2]&&a[2]==a[3]で確認する方法もあると書いてありましたが，実は思いつきませんでした（！）

そしてこのPythonのコードですが，わざわざCounterを使って，CounterのKeyの数を求めています（なんでこれを最初に書いて出したんだろうw）．Keyが一つしかなければ，全て同じ数なのでSAMEを出力です．（多分こんなんで回答したの私だけじゃないかなあと思います…）

こういう解法もあるということで一つお願いします．

Python版

from collections import Counter
print("SAME" if len(Counter(list(input()))) == 1 else "DIFFERENT")

Ruby版

puts gets.to_i%1111==0?"SAME":"DIFFERENT"

Bash版

awk '$0=$1%1111?"DIFFERENT":"SAME"'

perl版

print<>%1111?DIFFERENT:SAME,$/

B問題

この問題はPython3オンリーでしか解いてませんでした．

問題
abc033.contest.atcoder.jp

解答

配列2つ使うパターン（一番最初に出したやつ）

Submission #629352 - AtCoder Beginner Contest 033 | AtCoder

Mapでかくパターン

Submission #631103 - AtCoder Beginner Contest 033 | AtCoder

2次元配列パターン

Submission #631201 - AtCoder Beginner Contest 033 | AtCoder

いや，どうやっても解けるんですよ？

2つ配列を使うパターン

数値配列の最大値と，人数の合計値の半分の比較で大丈夫です．ただし，過半数以上の人数，という表現に注意です．最大値を取る街はindexとmaxを駆使して，うまく呼んであげれば良いと思います．

配列2つパターンのコード．

n = int(input())
townnames = []
townpeople = []
for _ in range(n):
    s, p = input().split()
    townnames.append(s)
    townpeople.append(int(p))
print("atcoder" 
    if max(townpeople) <= sum(townpeople) // 2
    else townnames[townpeople.index(max(townpeople))])

Mapを使うパターン．

!!!!おおっと，Pythonの場合はdictでしたね!!!!

{ 町の名前:人数 } でも良かったのですが，あえて { 人数:町の名前 } にします．こうすることで，最大値を求めれば，最大値をそのまま突っ込むだけで町の名前を取り出すことが出来ます．
あとはdictを構築しつつ，街の人数の合計値を求めれば良さそうですね．

ただ，解決していない問題があって，なぜか sum(dict)した場合はWAが出てしまうので，ループの中で人数の合計値を出しています．心あたりがある方がいらっしゃいましたら，教えていただけると助かります．

dict(map）パターンのコード

town, sm = {}, 0
for s,p in [input().split() for _ in range(int(input()))]:
    p = int(p)
    town[p] = s
    sm += p
mx = max(town.keys())
print("atcoder" if mx <= sm//2 else town[mx])

2次元配列パターン

Pythonのリスト（Pythonでは配列はリストでしたね！！！！）は柔軟なので，リスト内の要素が必ずしも同じ型でなくても入ります．この性質を利用するとうまく解けるでしょう．

最終的に私が帰着したのは，2次元配列で持っておいて，数値要素で昇順ソート，そしてソート後のリストの最後の要素が最大値になるので，それと配列内の人数の合計値を比較する，みたいな形で回答できます．

なんというかね，すごいPythonでしか出来ないようなコードが書けたのが気持ちよかったですね．インデックスに-1を指定すると，配列の最後の要素を取ってこれたり，ラムダ式を使いまわしたりと大変気持ちよかったです．楽しい．

2次元配列パターンのコード．

l=[input().split() for _ in range(int(input()))]
f=lambda x:int(x[1])
l.sort(key=f)
print("atcoder" if int(l[-1][1])<=sum(map(f,l))/2 else l[-1][0])

C問題

問題
abc033.contest.atcoder.jp

解答(すみませんやっぱりここから書き方変えます）

evalするパターン

Python

Submission #629675 - AtCoder Beginner Contest 033 | AtCoder

Ruby

Submission #630593 - AtCoder Beginner Contest 033 | AtCoder

はいC問題eval使った部集合〜〜〜
— yumechiさん (@yumechi0525) 2016, 2月 6

誰も集合しませんでした．

"+"でsplitしたあと，evalで計算結果を求め，0でないならカウントしていきます．それだけです．

ちなみにPythonでこの方法のコードを書くと，再帰回数の制限に引っかかるので，再帰回数を引き上げてから書いて下さい（ちなみにこの解放で解いたの，Python3では本当に私だけだったみたいです）

Pythonのコード．再帰回数を増やすsys.setrecursionlimit(100000)がキモ．

import sys
sys.setrecursionlimit(100000)
print(sum([1 for s in input().split("+") if eval(s) > 0]))

Rubyのコード．Rubyなら再帰回数の心配いらなかったのです．

p gets.split("+").select{|i|eval(i)>0}.size

(追記：evalの補足）
evalって何？ッて言われそうなので補足しておきますと，評価してその値を返す関数です．（私はLispで初めてこの概念を知った）

この辺りのサイトが参考になるかと思われます．

Python Tips：文字列を評価したい - Life with Python

qiita.com

countするパターン

Ruby

Submission #630612 - AtCoder Beginner Contest 033 | AtCoder

Java

Submission #630766 - AtCoder Beginner Contest 033 | AtCoder

Python

Submission #631703 - AtCoder Beginner Contest 033 | AtCoder

多分これが想定解．

"+"でsplitしたあと，countで文字列中の"0"の数を求め，0でないならカウントしていきます．それだけです．

殆ど変わらないっすね…．

ちなみに，Javaのstring.split()メソッドは，デフォルトで正規表現を渡すことになるので，ちゃんと\\+で渡さないとダメです（エスケープ処理っていうんでしたっけ？）

Ruby版．eval使った時とほぼ変わらず．

p gets.split("+").select{|s|s.count("0")==0}.size

Java版．やっぱり久々に書いてみたけどJavaはいろいろ冗長になりがち．うーん．

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.next();
 
		int res = 0;
		for(String elem : line.split("\\+"))
			res += elem.indexOf("0") < 0 ? 1 : 0;
 
		System.out.println(res);
	}
}

Pyhton版．inを使うとかっこ良く書けますね．

print(sum([1 for s in input().split("+") if "0" not in s]))

splitがない言語で頑張るパターン

C言語

Submission #631039 - AtCoder Beginner Contest 033 | AtCoder

splitないと不便ですよね？ですが，大丈夫です．

"+"が来るまで読み込んで，"+"がきたら，前にチェックしたところから現在の"+"の位置までに0が入ってないかを調べます．それでなんとかなります．最後も別途チェックする必要があるので要注意です．

#include <stdio.h>
 
int res = 0, i = 0;
int flag = 0;
char s[100002];
int lastidx = 0;
 
int main(void) {
	scanf("%s", s);
 
	for(i = 0; s[i] != '\0'; i++) {
		if(s[i] == '+') {
			int flag = 0;
			for( ; lastidx <= i ; lastidx++) {
				if(s[lastidx] == '0') flag = 1;
			}
			if(flag == 0) res++;
		}
	}
 
	for( ; lastidx < i ; lastidx++) {
		if(s[lastidx] == '0') break;
	}
	if(lastidx == i) res++;
 
	printf("%d\n", res);
 
	return 0;
}

D問題

問題
abc033.contest.atcoder.jp

解答（Python，30点分のみ）
Submission #630040 - AtCoder Beginner Contest 033 | AtCoder

えっと，部分点は三点の組み合わせを選んで，どんな三角形かを判断するよう総当りします．総当りの方法は，ベクトルで確認，角度で確認，長さで確認とありますが，私はわからなん！！だったので（なん！！とは），長さを取りまくる方法に帰着しました．

参考にしたサイト（yahoo知恵袋）
detail.chiebukuro.yahoo.co.jp

というわけで，長さを見てやれば，鋭角三角形(a^2+b^2>c^2)，直角三角形(a^2+b^2=c^2)，鈍角三角形(a^2+b^2<2)か判断できるわけですね．

itertoolsでcombinationを使うと，Pythonの場合，楽に組み合わせが作れるゾイ！

import itertools
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
ei, choku, don = 0, 0, 0
calclengths = lambda x1, y1, x2, y2: \
    abs((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
for elems in list(itertools.combinations(points, 3)):
    i = calclengths(elems[0][0], elems[0][1], elems[1][0], elems[1][1])
    j = calclengths(elems[1][0], elems[1][1], elems[2][0], elems[2][1])
    k = calclengths(elems[2][0], elems[2][1], elems[0][0], elems[0][1])
    temp = sorted([i, j, k])
    if temp[2] == temp[1] + temp[0]:
        choku += 1
    elif temp[2] > temp[1] + temp[0]:
        don += 1
    else:
        ei += 1
print(ei, choku, don)

長くなりましたが以上でした．

鋭角三角形，直角三角形，鈍角三角形を英語でなんというかわからなかったので，変数名を
ei, choku, don
にしたんだけど，chokuって競プロだと別の意味に聞こえますよね（？）
— yumechiさん (@yumechi0525) 2016, 2月 6