メンズワキガ対策専門ブランドD AGICA【ディーアジカ】

 

■競技プログラミング過去問題をやろうとしてみた…

やってみたんじゃなくて、やろうとしてみて、門前でめげたとゆ〜話 orz

 

C 言語を勉強しようと思い、なにか例題はないかなぁと探していたら、いいのがありました。

AtCoder:競技プログラミングコンテストを開催する国内最大のサイト

さっそく過去の問題に挑戦してみましょう。

 

7月14日の AtCoder Grand Contest 035 の A 問題「XOR Circle」です。

 

問題文
すぬけ君は N 枚の帽子を持っています。i 枚目の帽子には整数 ai が書かれています。

N 頭のラクダが円環状に並んでいます。 すぬけ君はそれぞれのラクダに 1 枚の帽子を被せようとしています。

どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば ' Yes ' を、そうでなければ ' No ' を出力してください。

・両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の被っている帽子に書かれた数と等しい

 

すぬけ君って (^_^;) 「競技プログラミング_用語 - projecthikky @ ウィキ - アットウィキ」によると「AtCoder社の社員のレッドコーダーsnukeさんのこと」だそうです。

 

しかし、えっと、あの〜、なんてゆ〜か、問題の意味すらわかりません orz

 

だいたい、すぬけ君はなぜラクダに帽子を被せようとしているわけ? その帽子に書かれた数の排他的論理和が云々ってなんの意味があるん (?_?) 

あ〜そうか、なんか小難しい数値の処理をラクダと帽子に例えたってことね。

登場人物の名前といい、たとえ話の奇想天外さといい、俺みたいな一般人が容易に足を踏み込めそうにないオタクなにおいがしてくる… (^_^;)

 

閑話休題

 

最も理解できなかったのは「自身の被っている帽子」ってところ。帽子はラクダに被せるんでしょ? すぬけ君の被っている帽子ってなによ (?_?) ―― 考えること小一時間、気が付いた。「自身」というのは両隣のラクダに挟まれたラクダのことね。「自身」というからてっきり人だと思った。

つまりこういうこと。

あるラクダの両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が、そのラクダ自身の被っている帽子に書かれた数と等しい」

 

例 1 より、帽子の数 N を 3 、それぞれの帽子に書かれている数字 a を 1 、2 、3 とします。

あるラクダ自身の帽子に書かれた数が 1 だとすると、右隣のラクダの帽子に書かれた数が 3 で、左隣のラクダの帽子に書かれた数は 2 です。右隣の 3 を二進数表示すると 0b11 、左隣の 2 は 0b10 です。それらのビットごとの排他的論理和は 0b01 になります。ラクダ自身は 0b01 で、求めた値と等しくなりますから、与えられた条件は「真」です。

帽子に書かれた数が 2 のラクダについても、両隣のラクダの帽子に書かれた数 1 と 3 のビットごとの排他的論理和は 0b10 になりますから「真」、3 のラクダについても同様に「真」です。

ということで、「どのラクダについても条件が成立」したので ' Yes ' を出力します。

 

では例 2 はどうでしょう。N = 4 、a = 1 2 4 8 とします。

ラクダ a=1 (0b0001) の右隣のラクダを a=8 (0b1000) 、左隣のラクダを a=2 (0b0010) とすると XOR は 10 (0b1010) ですから「偽」です。

両隣を 8 と 4 にしてみても、2 と 4 にしてみても「偽」となり、a=1 について条件を満たすような帽子の被せ方は存在しません。

「どのラクダについても条件が成立する」ことが条件ですから、これ以上他のラクダを検討してみる必要はないでしょう。この場合は ' No ' を出力します。

 

ということで、ようやく問題の意味が理解できました。

 

では問題に従って 3 ≦ N ≦ 10、0 ≦ ai ≦ 109 について考えてみましょう …

 

わ、わっかりませ〜ん orz

 

ラクダの頭数が 10 万頭で、帽子に書かれる数は 10 億までの範囲のラクダの頭数分の個数。帽子に書かれた数がすべて異なるといった条件はありませんから、同じ数が書かれた帽子もありうると… あ〜、力業で総当たりするにしても、どうすればよいものやらさっぱり (^_^;)

つまりこれは、C だのなんだの言う前に、いわゆる「アルゴリズム」ってものをしっかり考えろというとても基本的な命題なのだと、改めて気が付いた meyon さんでした。

 


コメント
コメントする








   
この記事のトラックバックURL
トラックバック

■calendar

S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
<< August 2019 >>

■search this site.

■recommend

毎日貯まるポイントサイト ECナビ

■recommend

* 楽天ROOM *

■Twitter

■recommend

■recommend

■selected entries

■categories

■archives

■recent comment

■recent trackback

■links

■profile

■others

■mobile

qrcode

■powered

無料ブログ作成サービス JUGEM