第二回コメントマラソン開催。

　　　　　　　　　　　　　　　　お知らせ。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

気まぐれに第二回コメントマラソンをしようかと思っている。

コメントマラソンとは、今日更新された全記事にコメントを付けて回る行為だ。

前回やった際には定期的に実施しようと思っていたのだが、すっかり忘れていた。

第一回コメントマラソン。

なんともう４ヵ月以上前だ。え、そんなに経ってるのか、光陰矢の如し。

正直１周全部回ると記事を書くより時間が掛かる。

だが、思い立ったのでやる、では、行きます！

ちなみに何のイベントでも無いが、参加したい方は是非ご一緒に。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

　　　　　　　　　　　　　　お知らせ終わり。

あれ、記事が短いな。

よし、

単品では不人気過ぎて書く気が起きない Atcoder の復習と抱き合わせよう。

昨日の D問題 だ。

問題：

長さ N の数列 A がある。

Aのうち、Aに含まれる他のどの数字でも割り切れないものは何個あるか。

例：

N:　　5

A:　　24　11　8　3　16

答え：

３個　　11、8、3が他のどの数字でも割り切れない。

普通に考えるなら、こうだ。

24　を　11、8、3、16　で割ってみる。　８でも３でも割り切れる。　ダメ。

11　を　24、8、3、16　で割ってみる。　どれでも割れない。　OK。

 8　を　24、11、3、16　で割ってみる。　どれでも割れない。　OK。

 3　を　24、11、8、16　で割ってみる。　どれでも割れない。　OK。

16　を　24、11、8、3　で割ってみる。　8で割り切れる。　ダメ。

 

答えは　３　個。
 

これなら簡単に書けるが、実はこいつは、めちゃ遅い。

そこで、こうなる。

小さい順に並べ替える。

3、8、11、16、24

 

１～24番まで ”Y” が入ったリストを用意する。

[Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y,Y]

 

初めに３。

リストの３番目が既に ”N” ならば、次の数へ。

３番目は ”N” でないので、

　　3×1、3×2、3×3、3×4・・・・番目の ”Y” を ”N” に換える。

　　[Y,Y,N,Y,Y,N,Y,Y,N,Y,Y,N,Y,Y,N,Y,Y,N,Y,Y,N,Y,Y,N]

　　ついでに３は答えなので記憶する。

 

次に８。

リストの８番目が既に ”N” ならば、次の数へ。

８番目は ”N” でないので、

　　8×1、8×2、8×3、・・・・番目の ”Y” を ”N” に換える。

　　[Y,Y,N,Y,Y,N,Y,N,N,Y,Y,N,Y,Y,N,N,Y,N,Y,Y,N,Y,Y,N]

　　ついでに８は答えなので記憶する。

 

次に11。

リストの11番目が既に ”N” ならば、次の数へ。

11番目は ”N” でないので、

　　11×1、11×2、・・・・番目の ”Y” を ”N” に換える。

　　[Y,Y,N,Y,Y,N,Y,N,N,Y,N,N,Y,Y,N,N,Y,N,Y,Y,N,N,Y,N]

 

次に16。

リストの16番目が既に ”N” ならば、次の数へ。

”N” なので次の数へ。

 

次に24。

リストの24番目が既に ”N” ならば、次の数へ。

”N” なので次の数へ。
 

これがねぇ、コンピュータに考えさせるなら早いらしいんよね。

最初の考え方が遅いだろうな、というところまでは予想が付くが。

じゃあこれを下の考え方にしよう、というところが、まだすぐ出来ない。

人間がやる手順と明らかに違う手順を踏ませるパターンがねぇ、苦手なんよね。

あと、もう一つ昨日の勉強。

左は通るけど、右は時間で引っ掛かる。

何度も読みに行く派目になるから遅いんね。

僕は右の書き方をしてしまいがちなんだけど、気を付けようと思った。

あ、しまった、抱き合わせ商法を無駄にいっぱい書いてしまった。

コメントマラソンに行かねば！！