AtCoder Grand Contest 036と037のA問題を解く

【目次】

【本題】

AtCoder Grand Contest 036 A - Triangle

問題文 整数 S が与えられます。 以下の条件をすべて満たす 6 つの整数 X 1 , Y 1 , X 2 , Y 2 , X 3 , Y 3 を 1 組求めてください。

0 ≤ X 1 , Y 1 , X 2 , Y 2 , X 3 , Y 3 ≤ 10 9 二次元平面上の 3 つの点 ( X 1 , Y 1 ) , ( X 2 , Y 2 ) , ( X 3 , Y 3 ) を頂点とする三角形の面積が S / 2 である。 なお、この問題の制約の範囲で、条件を満たすような 6 つの整数が必ず存在することが証明できます。

制約 1 ≤ S ≤ 10 18 入力される値はすべて整数である。

x1とy1は0で固定にすると面積を求めやすくなります。

三角形の面積をシンプルに求めるには、高さと底辺が必要ですが、それぞれの座業は定まっていないとそれらの数値の取得が困難になります。

その為、x3とy2以外の座標は全て0で固定する事にしました。

そうすればs / 2 = x3 * y2 / 2という式が成り立ちます。

これを基に組んだコードがこちらです。

s = gets.to_i
puts [0, 0, 0, s, 1, 0].join(' ')

非常にシンプルですが、これだと全てのテストケースが通りません・・・

0≤X1,Y1,X2,Y2,X3,Y3≤10の9乗と1≤S≤10の18乗の制約を忘れていました・・・

このコードだと、sが10の9乗より大きい場合に制約に引っ掛かってしまいます。

なので、0で固定するのはx1とy1だけにしました。

s = gets.to_i
x1=Math.sqrt(s).ceil
puts"0 0 #{x1} 1 #{x1**2-S} #{x1}"
p x1
p x1**2-S

AtCoder Grand Contest 037 A - Dividing a String

問題文 整数 S が与えられます。 以下の条件をすべて満たす 6 つの整数 X 1 , Y 1 , X 2 , Y 2 , X 3 , Y 3 を 1 組求めてください。

0 ≤ X 1 , Y 1 , X 2 , Y 2 , X 3 , Y 3 ≤ 10 9 二次元平面上の 3 つの点 ( X 1 , Y 1 ) , ( X 2 , Y 2 ) , ( X 3 , Y 3 ) を頂点とする三角形の面積が S / 2 である。 なお、この問題の制約の範囲で、条件を満たすような 6 つの整数が必ず存在することが証明できます。

制約 1 ≤ S ≤ 10 18 入力される値はすべて整数である。

一文字づつ前後の文字を比較する方法を試しました。

不一致の場合は分割対象としてカウントします。

一致した場合はカウントせず、その文字を次の文字と結合させて比較を行います。

charsメソッドを使えば、一文字づつブロックを繰り返せます。

s = gets.chomp
before_char= ''
current_char = ''
count = 0
s.chars do |char|
  current_char += char
  if before_char != current_char
    count += 1
    before_char = current_char
    current_char = ''
  end
end
puts count