No. 892 タピオカ (yukicoder)

オリジナル: https://yukicoder.me/problems/no/892

入力フォーマット:

A_1 B_1 A_2 B_2 A_3 B_3

問題の概要: A_1 ^ B_1 + A_2 ^ B_2 + A_3 ^ B_3 が2で割り切れるなら :-) 、そうでないなら :-( を出力する

制約: A_1 B_1 A_2 B_2 A_3 B_3 は全て1以上10^9未満の自然数

解説

• 愚直にA_1 ^ B_1 + A_2 ^ B_2 + A_3 ^ B_3をやると(10^9)^(10^9)を踏んで死ぬので、考察をする。
• A_1 ^ B_1 に注目する
  • 偶数を何乗しても偶数 (注釈: 偶数 × 偶数 = 別の偶数、帰納的に成り立つ)
  • 奇数を何乗しても奇数 (注釈: 奇数 × 奇数 = 別の奇数、帰納的に成り立つ)
• A_2 ^ B_2 と A_3 ^ B_3 も同様
• つまり (偶数|奇数) + (偶数|奇数) + (偶数|奇数) の8パターンに帰着できる
• 3つの整数の和が偶数になるのは全て偶数か、2つ奇数で1つ偶数のときのみ
  • 全て偶数の場合
    • 2a + 2b + 2c = 2(a+b+c)
  • 1つ奇数の場合
    • 2a+1 + 2b + 2c = 2(a+b+c)+1
  • 2つ奇数の場合
    • 2a+1 + 2b+1 + 2c = 2(a+b+c)+2 = 2(a+b+c+1)
  • 3つ奇数の場合
    • 2a+1 + 2b+1 + 2c+1 = 2(a+b+c)+3 = 2(a+b+c+1)+1

実装例

Ruby:

a,b,c,d,e,f = gets.split.map(&:to_i)
puts ((a % 2) + (c % 2) + (e % 2)) % 2 == 0 ? ":-)" : ":-("

—https://yukicoder.me/submissions/577356