Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2348-b14c3832
この記事にトラックバックする(FC2ブログユーザー)

UVa 12499 - I am Dumb 3 (この記事を編集する[管理者用])

Source

Another Bangladeshi Contest (2012-10-07)
UVa 12499

問題概要

正整数 n (50以下) と L (1000000以下) が与えられる.
また要素数nの単調非減少な整数列が与えられる.
2人でゲームをやる.打つ手がなくなったら負け.先手必勝か後手必勝かを判定する問題.
各ターンできることは,整数列の要素を1つ選び,1以上増加させる.
ただし,単調非減少は維持しなくてはいけなく,最後の要素はLより大きくなってはいけない.

解法

数列の最後にLを追加し,階差数列を考える.
それを1つ飛ばしで見てNIMと同様にXORを取って判定できる.
階差数列の偶数番目を減らすというのは,相手は同じ状態に戻せるので,意味のない動きになる.
なので,奇数番目だけ見れば普通のNIM.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2348-b14c3832
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。