プログラミングしたい日記

いつもプログラミングとか音楽聞いてたりする人の日記です

AOJ Volume 0022, 0023

いつものやっていきまーす
HHKB買いました。まだなれないので打ちにくいですが、タイプする感覚はGOODです!

AOJ Volume 0 Q22

Maximum Sum Sequence | Aizu Online Judge

問題の概要

連続する項の和が最大となる時、その和を出力せよ。

つまづいた所

総当りしか思いつかなくて、それでいいのか迷って他の方々の答えみたら総当りばっかだったのでもうそれでいいやってなりました(笑)
あと、intの最小値を出すのが不思議だった。

解説

総当りでなんとか見つけます。

ソース
import sys

def solve(numbers):
    max = -sys.maxsize
    for i in range(0, len(numbers)):
        sum = 0
        for j in range(i, len(numbers)):
            sum += numbers[j]
            if sum > max:
                max = sum
    return max


while True:
    n = int(input())
    if n == 0:
        break
    numbers = []
    for i in range(0, n):
        numbers.append(int(input()))

    print(solve(numbers))

AOJ Volume 0 Q23

円の交差 | Aizu Online Judge

問題の概要

2つの円があり、それぞれの円をA, Bとする。ただし、A≠Bとする。
BがAの中にある時2, AがBの中にある時-2, AとBが共有点を持つ時1, AとBが重ならない場合0を出力せよ。

解説

数学がわかってればつまづくところはないと思う。

つまづいたところ

内包表記を忘れて戸惑った。でもこれ便利ですね。

ソース
import sys

def solve(circleA, circleB):
    xa, ya, ra = circleA
    xb, yb, rb = circleB
    # まず、円の中に円が含まれる場合を判定
    if ra <= rb:
        if distancePow2(xa, ya, xb, yb) < pow(rb - ra, 2):
            return -2
    else:
        if distancePow2(xa, ya, xb, yb) < pow(rb - ra, 2):
            return 2

    # 共有点を持つ時を判定
    if pow(rb - ra, 2) <= distancePow2(xa, ya, xb, yb) <= pow(rb + ra, 2):
        return 1

    return 0

def distancePow2(xa, ya, xb, yb):
    return pow(xb - xa, 2) + pow(yb - ya, 2)

n = int(input())
for i in range(0, n):
    inStr = input()
    circleAInfo = [float(data) for data in inStr.split(" ")[0:3]]
    circleBInfo = [float(data) for data in inStr.split(" ")[3:6]]
    print(solve(circleAInfo, circleBInfo))

AOJ Volume 0 - 0012, 0017

はい。今まで寝てました。やっていこうと思います。

既にやってある所は飛ばしているのでごめんなさい!

AOJ Volume 0 Q12

A Point in a Triangle | Aizu Online Judge

問題の概要

三角形の頂点の座標と、ある点Pの座標が与えられた時、点Pが三角形の内部にあれば「YES」、なければ「NO」を出力する。ただし、三角形の辺、頂点に交差する場合を除く。

つまづいた所

いい方法が思いつかんのでネットで調べたら、外積使うとうまく解けるみたいです。
大学で最近習った外積をここで使うことになるとは思わなかった(._.)

解説

三角形の辺のベクトルを「v1To2, v2To3, v3To1」とし、三角形の頂点から点Pまでのベクトルを「vNToP」とする。
vNTo(N+1) × vNToPの符号がすべて一致する時、点Pは三角形の内部にあるという性質(?)を利用してます。

ソース
import fileinput


class Vector2D:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def dot(self, vec2d):
        return (self.x * vec2d.y) - (self.y * vec2d.x)


for line in fileinput.input():
    x1, y1, x2, y2, x3, y3, xp, yp = [float(r) for r in line.split()]
    v1To2 = Vector2D(x2 - x1, y2 - y1)
    v2To3 = Vector2D(x3 - x2, y3 - y2)
    v3To1 = Vector2D(x1 - x3, y1 - y3)
    v1ToP = Vector2D(xp - x1, yp - y1)
    v2ToP = Vector2D(xp - x2, yp - y2)
    v3ToP = Vector2D(xp - x3, yp - y3)

    if (v1To2.dot(v1ToP) < 0 and v2To3.dot(v2ToP) < 0 and v3To1.dot(v3ToP) < 0) or (v1To2.dot(v1ToP) > 0 and v2To3.dot(v2ToP) > 0 and v3To1.dot(v3ToP) > 0):
        print("YES")
    else:
        print("NO")

AOJ Volume 0 Q17

シーザー暗号 | Aizu Online Judge

問題の概要

aをb, bをc、zをaといったように、ある文字xがあった時、その文字コードをxcとし、その文字を(xc + n) mod 26の文字コードに対応する文字に置換するような暗号化を行うものとする。

この時、ある文字列Sが与えられて、それを暗号化した文字列をS'とする。
Sには「the, this, that」のいずれかが含まれるので、なんとかしてS'からSを決める。
という問題。
例えば、
S' = uijt jt b qfo

S = this is a pen
となる。

解説

負のindexが使えるpython最強な気がする

つまづいたところ

文字列を変換して再代入を繰り返すと、「a」が「c」になった時、そのcがまた置換されてずれてしまうので対策するのがめんどくさかった。
最終的には、文字列を配列化して1文字1文字置換してく形になった。

ソース
import fileinput
import string

alphabetArray = list(string.ascii_lowercase)

for data in fileinput.input():
    for n in range(-26, 27):
        replacedStrAry = list(data.replace('\n', '').replace('\r', ''))
        for index in range(0, len(replacedStrAry)):
            if not replacedStrAry[index] in alphabetArray:
                continue
            if n >= 0:
                replacedStrAry[index] = alphabetArray[(alphabetArray.index(replacedStrAry[index]) + n) % 26]
            else:
                replacedStrAry[index] = replacedStrAry[index] = alphabetArray[alphabetArray.index(replacedStrAry[index]) + n]
        replacedStr = "".join(replacedStrAry)
        replacedStrSplitedBySpace = replacedStr.split(' ')
        if "the" in replacedStrSplitedBySpace or "this" in replacedStrSplitedBySpace or "that" in replacedStrSplitedBySpace:
            print(replacedStr)
            break

入門 Python3を2章まで読んだ

入門 Python3を大学の図書館で借りて、2章まで読みました。
Javaしかそこそこできない僕が、記憶の整理もかねて違いとかPython独自の機能とかをざっくり書いていこうと思います。

JavaPythonの違い

コンパイル型言語とスクリプト言語

Java Python
コンパイル型(ジャストインタイムコンパイル方式) スクリプト

Javaコンパイル言語(実行を高速化するために、機械に読まれることに特化した形に変換して実行する言語)であり、対してPythonは直接コンピューターにプログラムを読ませます。
この辺は曖昧のなのであってるかどうかよくわかんないです。

型付け

JavaPythonでは、型付けの方法が違います。

Java Python
静的 動的

静的型付けは、プログラマが自分で変数の型を指定して、その変数にはその型の値しか代入できなくなります。
それに対して動的型付けは、プログラマが自分で変数の型を指定しなくても、Pythonの実行プログラム(インタプリタ)が勝手に型を判定してくれます。
僕的には、静的型付けの方が今のところ好きです。何を代入すればいいのか明確になって判断がしやすいんで。

Pythonの文法

プリミティブ型変換

Javaでは「(Type) variable」や「Class.valueOf(variavble)」で型変換をしていましたが、Pythonでは関数を使って型変換をします。

文字列から整数へ

Java:

Integer.valueOf("123");


Python:

int("123")
浮動小数点数から文字列へ

Java:

String.valueOf(123.45);

Python:

str(123.45)

この型変換機能はスッキリしてて読みやすいですし便利ですね。

スライス

これがすごく便利そうな機能。リストの中身をいい感じに取り出せる機能。
文法的には次な感じ。

list[start:end:step]

startとかendとかの値は省略可能で、省略すると、

  • startには0
  • endにはlen(list)
  • stepには1

が入るようだ。
start, end, stepには負の数も指定することができ、その場合は「len(list) - n」のような数値になるらしい。
例えば、list[-3:]であれば、list[len(list)-3:list(len):1]のような感じになる。

文字列の掛け算

文字列に演算子「*」を適用すると、右項の値だけ左項の文字列が繰り返される。
例えば、「a*4」は「aaaa」になる。

感想?

まだまだPythonの魅力にあまり触れられていない自分ですがどんどん触れていきたいと思います。
実は、既にPythonで監視カメラを作った経験がありPython自体にはある程度触れています。でも調べながらだったので文法とかその場その場で覚えていく感じで中途半端なんですよね。
なので、本を使ってがっつりやろうと思った次第です。
水曜日にテストあるのに何やってんだって感じですが、どっちもそこそこやっていきます(*´﹃`*)。

夏休みの目標

結局、AOJの問題解くやつ毎週更新してないですね。ごめんなさい。(それどころか今まで全然やってねーじゃんっていう)

今日は夏休みの目標について書きたいと思います。

今度こそ(ほぼ)毎週AOJを解く!

いい加減解いてなかったので今度こそ毎週AOJの問題を解いていきたいと思います。
夏休みなので倍の4題に増やします。Pythonを学ぶのでほとんどPythonで頑張ってやってみたいと思います。
ただ、できない週もある(8/12, 19, 9/23)のでその週は飛ばしていきます。

Python3を覚えて何かサービス(Webアプリ?)を作る!

まだまだ詳細は決まっていないので、順次決めていきたいと思います。スケジュールとしては次の感じ。
f:id:wintermaples:20170729010354p:plain

機械学習をCourseraで覚える

せっかくのPythonなので、Courseraで機械学習を覚えたいと思います。
もう既に途中までは進んでて、2章の半分ぐらいまでは進んでます。(でも結構忘れているけど><)




バイトやら委員会やら旅行やらで全部できる気がしないですが頑張るぞい!

これから毎週日曜日AOJ2題づつやっていこうと思います

どうも。大学入学したwintermaplesです。大学エンジョイしてます。

最近数学的なプログラミングあんまやってない気がするのでAOJやるの習慣づけようかなーって思ってます。
ちなみに、既に少しだけやっちゃってます。
ルールは以下の通り

  • 毎週日曜日にAOJの問題を2題解く
  • 解説とソースコードを書く
  • やらなかったら来週に持ち越し。最大6題
  • Volume0から順番に解いていく
  • 使える言語の中からできるだけランダムに使う
  • 自前のライブラリみたいなのは使用OK。それ以外はデフォルトで入っているもののみ
  • ただし初回は土曜日(この記事を書いた日)

こんな感じでやっていきます。

じゃあ早速

AOJ Volume 0 Q4

Simultaneous Equation | Aizu Online Judge

問題の概要

2元1次連立方程式を解く。ただし、小数点第4位で四捨五入。解なしは考慮しない。

つまづいた所
double x = (double) (c * e - b * f) / (a * e - b * d);

ここint/intになってて、結果もintにするように最初してたからWrong Answer勃発してた。
それ以外は特になし。ちなみに、最初まともに計算して解の公式作ってた。調べたら一般性のある解の公式あるじゃんっていう。

ソース
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by wintermaples on 2017/04/29.
 */
public class Main {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String read;
    while (scanner.hasNext()) {
      read = scanner.nextLine();
      //1行を読み込んでint配列に
      int[] variables = Arrays.stream(read.split(" "))
          .mapToInt(s -> Integer.parseInt(s))
          .toArray();

      //わかりやすいようにそれぞれ変数に格納
      int a = variables[0];
      int b = variables[1];
      int c = variables[2];
      int d = variables[3];
      int e = variables[4];
      int f = variables[5];

      //解はクラメルの公式で一発
      double x = (double) (c * e - b * f) / (a * e - b * d);
      double y = (double) (a * f - c * d) / (a * e - b * d);
      BigDecimal xBD = new BigDecimal(x);
      BigDecimal yBD = new BigDecimal(y);
      xBD = xBD.setScale(3, BigDecimal.ROUND_HALF_UP);
      yBD = yBD.setScale(3, BigDecimal.ROUND_HALF_UP);

      //3桁にまとめて出力
      System.out.println(
          String.format("%.3f", xBD) + " " + String.format("%.3f", yBD)
      );

    }
  }

}

AOJ Volume 0 Q10

Circumscribed Circle of a Triangle | Aizu Online Judge

問題の概要

3点の座標が与えられ、それらが作る三角形の外接円の座標と半径を求める。

つまづいた所

そもそもpythonに慣れてない。標準入力から調べんとよーわからんかった。
あと、中心の座標の一般解求めるのめんどくさかった。
python3だと四捨五入がおかしいとか出てきたけど提出したら通ったから問題ない(多分)

解説

中心の座標は2元1次連立方程式に帰着したので、さっきの解の公式にぶちこんで、フォーマット&出力して終わり。
ちなみに、中心の座標の解px, pyは次で表される。

{ \displaystyle
a_1 := 2(x_2 - x_1)\\
b_1 := 2(y_2 - y_1)\\
c_1 := x_2^2 + y_2^2 - x_1^2 - y_1^2\\
a_2 := 2(x_3 - x_1)\\
b_2 := 2(y_3 - y_1)\\
c_2 := x_3^2 + y_3^2 - x_1^2 - y_1^2\\
a_1px + b_1py = c_1\\
a_2px + b_2py = c_2\\
Solution:\\
px=\frac{(y_3-y_1)(x_2^2 + y_2^2 - x_1^2 - y_1^2)-(y_2-y_1)(x_3^2 + y_3^2 - x_1^2 - y_1^2)}{2(x_2-x_1)(y_3-y_1)-2(x_3-x_1)(y_3-y_1)}\\
py=\frac{(x_2-x_1)(x_3^2 + y_3^2 - x_1^2 - y_1^2)-(x_3-y_1)(x_2^2 + y_2^2 - x_1^2 - y_1^2)}{2(x_2-x_1)(y_3-y_1)-2(x_3-x_1)(y_3-y_1)}\\
}

カオスだなこりゃ

ソース
import math

n = int(input())

for i in range(n):
	x1, y1, x2, y2, x3, y3 = map(float, input().split()) # Get variables
	a = 2 * (x2 - x1)
	b = 2 * (y2 - y1)
	c = math.pow(x2, 2) + math.pow(y2, 2) - math.pow(x1, 2) - math.pow(y1, 2)
	d = 2 * (x3 - x1)
	e = 2 * (y3 - y1)
	f = math.pow(x3, 2) + math.pow(y3, 2) - math.pow(x1, 2) - math.pow(y1, 2)
	px = (c * e - b * f) / (a * e - b * d)
	py = (a * f - c * d) / (a * e - b * d)
	r = math.sqrt(math.pow(x1 - px, 2) + math.pow(y1 - py, 2))
	print('{:.3f}'.format(px) + ' ' + '{:.3f}'.format(py) + ' ' + '{:.3f}'.format(r))
CSS Design created by satotaka99. Thankyou.