debiruはてなメモ

はてなブログの HTML が Invalid なの、わたし、気になります

POJ-1082をショートコーディングしてみたよ!

はじめに

競技プログラミングが普及して、AtCoderAOJ とする日本語のジャッジシステムが登場して久しいものです。私が大学時代にICPCに参加していた頃(2006年頃)は日本語のジャッジシステムは存在せず、北京大学のオンラインジャッジシステム(POJ)をよく利用していました。

今回は、そんな POJ - 1082 の問題をショートコーディングする話です。この問題はICPCアジア地区予選、2001年韓国Taejon(テジョン)の A 問題です。アジア地区予選の1問目、納得できる難易度です。

POJ 1082 - Calendar Game

問題文

問題文(原文)を要約すると次の通り。

  • Adam と Eve が2人でゲームをする。
  • 1900/1/1 のように YYYY/MM/DD の日付が与えられ、「次の日」か「次の月の同じ日」を宣言できる。
  • 1900/1/31 は次の月の同じ日が存在しないため宣言できず、次の日 1900/2/1 しか宣言できない。
  • プレイヤーは相手の宣言の日付を受け取って、次の宣言を行う。
  • 2001/11/4 を宣言したプレイヤーが勝ちとなり、2001/11/4 より未来を宣言すると負けとなる。
  • 先手は Adam で、最初の日付はランダムに与えられ、宣言は交互に行う。
  • 最初に与えられる日付について、Eve が最適解を宣言し続けるとき、Adam が勝てるなら YES を、勝てないなら NO を出力せよ。
  • あなたは、閏年について考慮しなければならない。閏年の定義は年が、400の倍数なら閏年、100の倍数なら平年、4の倍数なら閏年である。閏年と平年の違いは2月29日(閏日)が存在するかどうかだけであり、閏年には閏日が存在する。

2001/11/3 が与えられたら、Adam は「次の日」を宣言することで 2001/11/4 を宣言できるので「勝ち」となる。

入力の仕様

  • 始めに正整数 T が与えられる。T はテストケースの数である。続く T 行に、3つの正整数 Y M D が与えられる。それぞれ最初に与えられる日付の年月日である。
  • 与えられる日付の範囲は、1900/1/1 から 2001/11/4 の間の日付である。

出力の仕様

  • テストケースごとに、改行区切りで "YES" か "NO" を(引用符無しで)出力しなければならない。

解答

アルゴリズム

この問題の想定解(問題のカテゴリ)は「DP(動的計画法)」でしょう。1900/1/1 から 2001/11/4 までの日数分の boolean 配列(この日付を渡されたら負けるフラグ)を用意して 2001/11/4 を True にしておき、2001/11/3 から逆順に「次の日」「次の月」の日付のフラグを見て、どちらかが True でなければ元の日付のフラグを True にするという方針で解くことができます。しかしそれより効率的な、数学的に解く方法が存在します。

この問題は、与えられた日付の「月と日」を見るだけで答えが分かります。「月と日の和が偶数ならYES」「9月30日または11月30日ならYES」「それ以外はNO」となります。このことを証明しましょう。

2001/11/1 が与えられたらどうでしょうか。「次の月」を宣言したら負けるので「次の日」しか宣言できません。するとその後、自分に 2001/11/3 が渡ってきます。つまり勝ちです。

2001/10/1 はどうでしょうか。2001/11/1 か 2001/11/3 を自分に渡せたら勝ちになりますが「次の月」を宣言するとそれが相手に渡ってしまいます。次の日を宣言しますが 2001/10/3 が自分に渡ってきてどうやら 2001/11/3 も自分に渡すことができません。2001/10/31 まで「次の日」を宣言し続けますが、2001/11/1 が相手に渡ってしまいます。つまり負けです。

この問題で渡ってくる日付の「不変量」を考えましょう。不変量を「月と日の和を2で割った余り(偶奇性)」にします。以下では自分に渡ってきた日付に注目します。

2001/11/3 が渡ってきたら勝ちでした。つまり不変量が偶数の日付が渡ってきたら勝ちになります。自分が勝つには、相手に不変量が奇数の日付を渡さなければなりません。

  • (P-1)「次の月」を宣言すると、不変量は M + 1 + D で反転する。自分が偶数なら勝つ
  • (P-2) 末日以外に「次の日」を宣言すると、不変量は M + D + 1 で反転する。自分が偶数なら勝つ
  • (P-3) 自分が偶数月の末日のとき(2/28, 2/29, 4/30, 6/30, 8/31, 10/31, 12/31)、
    • (P-3-1)「次の日」を宣言すると、相手が「奇数月 + 1日目」で偶数になる。この宣言をすると負ける。
    • (P-3-2) 自分が偶数のとき「次の月」を必ず宣言でき、相手が「奇数月 + 偶数日」で奇数になる。この宣言をすると勝つ
    • (P-3-3) 自分の奇数のとき「次の月」を宣言すると、相手が「奇数月 + 奇数日」で偶数になる。この宣言をすると負ける。
  • (P-4) 自分が奇数月の末日のとき(1/31, 3/31, 5/31, 7/31, 9/30, 11/30)、
    • (P-4-1)「次の日」を宣言すると、相手が「偶数月 + 1日目」で奇数になる。この宣言をすると勝つ

(P-1), (P-2) は、基本的に「次の日」か「次の月」を宣言すると不変量が反転することを言っています。つまり自分が「偶数」なら相手が「奇数」となるので勝てるということです。(P-3) は、自分が奇数で偶数月末日のときは勝つ手段がないことを確認しています。(P-4) は、自分が奇数でも奇数月末日(つまり 9/3011/30)であれば勝てると言っています。

閏年閏日は上記の議論に影響しません。閏日があろうがなかろうが、偶数月の末日が何日だろうが「与えられた日付の不変量が偶数」なら勝ちということです。そして奇数月の末日が偶数日の場合は、その日だけ例外的に勝ちになるということです。

ちなみに、この「不変量」を考えるという概念は数学の証明でも強力な武器になる手法です。数学の証明問題で不変量を用いた証明は「【史上最悪】伝説の1998年東大後期グラフ理論を徹底解説【理系大問3】」をご覧ください。

ソースコード

a,b;main(i){for(;~scanf("%d",&b);)--i%3?a=b:i&&puts(a+b&1&&a<9|b<30?"NO":"YES");}

i の初期値は 1 になります。1個ずつ値を b で受け取り a にコピーしておく。4個目の値を受け取ったら、a と b を使って答えを出力する。以降7個目、10個目、3k+1個目の値を受け取ったら出力する。puts の条件部分は、奇数かつ「9/30でも11/30でもない」ならば NO, そうでなければ YES としています。

このコードで POJ 1082 - GCC のコードの短さで1位を取ることができました。

Ozyさんリスペクト

この記事は Ozy さんに感化されて書いたものです。Ozy さんのショートコーディング記事は 😍楽しいプログラミング😍隣接するビットを数えよう - カメヲラボ をご覧ください。

Ozy さんはショートコーディング界の偉大な方で『ショートコーディング 達人達の技法』を執筆されています。この本の凄さについては私の Amazon レビューでもお読みください。昔からコードを短く書く遊びは「コードゴルフ」と呼ばれていますが、Ozyさんは敢えて「ショートコーディング」という別名を付けています。

そんな Ozy さんが翻訳された書籍『きれいなPythonプログラミング』が近日発売されるので、Python初心者の方からベテランの方まで興味があればぜひ読んでみてください。私は献本されたわけでもステマでも何でもないのでまだ読めていませんし内容も知りませんが、いつか読んでみたいです。

Next debiru's HINT 「WebはWEBじゃない