研究や趣味やらあれこれ

日々のあれこれをあれ

yukicoder No.2 素因数ゲーム

yukicoderシリーズ2回目

 

この調子で続けたい…が早速WAで進めなくなった

 

ある数Nを2人で交互に素因数で割っていく。同じ数なら何度割っても良い。1を渡されたほうが負け。どちらが勝つか出力せよ、という問題

 

至極単純…が法則がつかめなかった…

 

github.com

 

 

少し紙に書いてみて、素因数の種類の数が奇数のとき先手必勝。偶数のときは素因数分解したときの素因数の総数が偶数なら後攻必勝かな?と思って書いたのが↑

 

見事にWA。でもACのケースが多かったので惜しいのかなとか思ってしまい見事にどん詰まり

 

sugarknri.hatenablog.com

 

testestest様の解説をちら見

 

このような山崩しケームは勝敗に法則があるらしい…

 

「全山の石の個数の排他的論理和が0なら後攻必勝」

 

…?わからん。ちら見じゃ無理だ、ガン見

 

どうやらこの手のゲームはNim問題と呼ばれるもので、この排他的論理和のことを

Nim和と言うみたいで、常にNim和が0で相手に手番を渡すことができれば勝つ事ができるようだ

 

ということで書き直し

 

github.com

 

ACでした

 

世の中知らないことだらけ〜

 

 

yukicoder No.1 道のショートカット

だーいぶ遅くなったけどとりあえず更新

 

最近yukicoderなるとこで競技プログラミングの練習を始めた

 

言語はJavaです。速さなんて知らない

 

多分星3とか4は飛ばすことあると思うけど、1から順にGitにアップしていこうと思う

 

yukicoder/src at master · gazinao/yukicoder · GitHub

 

とりあえずNo1。

 

N個の街と所持金Cがあって、ある街からある街へつなぐ道がV個ある。道にはそれぞれかかるお金と時間が与えられていてこの時、街1から街Nへ行くとき所持金内で行ける経路で最速のものを選んだ場合にかかる時間を求めよ、という問題

 

街番号が大きいものから小さいものへの経路は考えなくて良いとある

 

ので、速さだけ求めるならダイクストラとかいうDPっぽいもので、各街まで行くのに最速の経路を街番号が小さいものから順に更新していけば良い

 

プログラム的には、n番目の街に到達する最速の時間をt[n-1]とし、それぞれを更新していけば最終的にt[N-1]が答えになる

 

しかし今回はコストも考慮しなければならない

 

はじめに思い浮かんだ方法は、最小時間でダイクストラしていってコストオーバーした時点で道を戻り次にコストの低い道を選ぶ、というものだった

 

でもこれだと次にコストの低いものでゴールできても、すべての道で最速とは限らないのでボツ

 

てことで、思いついたのがダイクストラでできるようにコストの概念を消す方法

 

各街をC+1個にコピーして、所持残高で入れる街を制限してダイクストラ。最後にN番目の街すべての中から一番早いものが答えとなる

 

プログラム的には、t[N]をt[N][C+1]に拡張しダイクストラ。所持金が足りなくなる、つまり更新先の配列のインデックスがマイナスになる場合更新しない

 

でACいただけました

 

実行時間:211ms コード長:2162Byte(コメントって含まれるのかな?)

 

解説もこんな感じだったと思うし解けてよかった(小並感)

 

ここから

はじめまして、dazyと申す

 

まんま理系の学生。アニメ、漫画、etc

 

なかでもプログラミングとBUMP OF CHICKENに興味津津

 

BUMPのライブには結構参加してて、このまえのBFLYには最終日に参加済み!

 

めっちゃ良かった・・・語彙力の欠如笑

 

プログラムの方は趣味程度にjavaで好きなものを、大学ではソフトウエアの安全性について検証中

 

志としてはゲーム系の会社に就職すること

 

そう、僕もう院1年生で就活秒読み

 

けどゲーム系の会社を志望するような人にしては開発とか全然してなくて、おそすぎた・・・って感じ

 

だからって何もしないわけにはいかないし、自分としてもそんな気は毛頭ないためとりあえず、20万はたいてMacbook Proを買った

 

未来への先行投資と思えばなんともない

 

全てはここから、まだまだこれから

 

・・・厨二臭かったかな?笑