読者です 読者をやめる 読者になる 読者になる

研究や趣味やらあれこれ

日々のあれこれをあれ

yukicoder No.5 数字のブロック

区切りにするつもりのNo.5

 

N個のそれぞれ高さ1横幅Wi(i:1->N)のブロックがあって、高さ1の長さLの箱に最大何個入れられるかという問題

 

No.4はこの問題で、ちょうどLになるときはあるか?という時だったのでちょっといじってできた

 

github.com

 

特に有りませぬ。★1だしね

yukicoder No.4 おもりと天秤

さてNo4

 

それぞれ重さのわかるおもりN個があり、それらすべてを天秤にのせたときうまく水平にできるおもりの置き方があるかどうか

 

github.com

 

はいWA

 

重い順に天秤が軽い方へ載せていったけど…これだと

 

Left{10, 3, 3, 3} Right{9, 5, 5}

 

みたいとき見つけられてなかった

 

あとからだと気づくんだけどね笑

 

 

こういう問題ってシミュレートして結果うまくいった、いかなかったっていう方法はだめなんだなと気づいた

 

素因数ゲームのときもそうだったけど、答えを置き換えなきゃ…

 

今回は、

両方のおもさがおなじになる割当があればおっけー

全体の半分の重さを作ることのできる割当があればおっけー!

 

 

github.com

 

TLE…だと?

 

テストケースコピってローカルで試してみたけどなぜかchallenge8だけ実行が終了しない…

 

そもそも無限ループになるような書き方してないのになぁ…

 

やっぱりなれない再帰を使うとうまくいかない

 

 

先輩に相談してみたところ、メモ化再帰ならうまくいくのでは、とのこと

 

…が、ダメ!!

 

そもそもの無限ループっぽい

 

悔しいけどカンニング

 

やっぱりDPなのかぁ。DP大人気!考えは良かったっぽい

 

わかってきたのは、ある答えを追い求めるよりも、考えうる答えをリスト化した後に答えがあるかを調べるのがいいのかな?

 

github.com

 

ようやくAC

 

 

 

研究も忙しくなってきたし、5までやってこっちは一段落しよう

 

 

yukicoder No.3 ビットすごろく

★2だ!やった簡単!

 

と思っていた時期がぼくにもありました。

 

と言うのはさておき、No.3

 

N個マスがあるすごろくで、Nマス目がゴールとなっている。1マス目がスタートで、自分の今いるマスの番号を2進数で見たときに1ビットの数だけ進むまたは戻る事ができる。ただし1未満のマス、N+1以上のマスには移動できない。このとき、何回の移動でゴールすることができるか、またはできないか

 

とりあえずWA(あたりまえのように)

 

github.com

 

よく考えたら、途中で戻る場合を考えてないことに気づいて修正

 

github.com

 

なんや、ちょろいやん

 

★2なら1WAでなんとかしたい…願わくば0…

 

 

 

うまくいって嬉しくなってデバッグコードまで一緒に提出してREなったのは秘密

 

 

これからの世界?

昨日読んだ雑誌で人工知能について取り上げられていたのでそれを読んで思ったことをつらつら

 

研究していないことについて述べてもつまらんので、一般のぼくらが使えるようになる技術について覚えていることを

 

  1. 30年後の人の職業の半分がAIで代替可能?
  2. これからはデジタルではなくアナログへ

 

まず、1.について。まあ就職していないぼくが語るのもあれですが、まじか。と

 

どうやら、現在の試算でこの結果が出ているそうな

 

もちろんだがどの職業もまんべんなく5割カットというわけではなくほとんど持っていかれるもの、ほとんど取って代わらないものがあるようだ

 

具体的には、経理事務員、公共交通機関運転士、各種清掃員などが99%以上は代替可能

 

医師・カウンセラー、ゲームクリエーター、各種デザイナーなどは代替率1%未満らしい

 

確かに、現在でさえ車や電車の自動運転があるのだから高い代替可能率のものはそうなっても仕方ないのかな、と思った

 

けど医師については現在カルテから病名を確定させる人工知能も出てきているのに代替できないのだろうかとは不思議に思った

 

リエーターが残るという試算が出ているのは少し嬉しかった笑

 

 

次に2.について

 

デジタルからアナログへ?なんで時代逆行してんの!と思うかもしれないが時代は進んでいる

 

これは、インターネットをパソコン同士の通信だけにつかうのではなく、身の回りの普段手にとって使うようなものにまで適用させよう!という考えらしい

 

この考えをIoT(Internet of Things)というんだと

 

たとえば、植木鉢

 

植木鉢にネットがつながれば、スマホから土の乾き具合、栄養状態が管理できるようになる、といった具合だ

 

つまり、万物の声が聞けるようになる…と

 

こんな厨二バンザイ技術だけど普通に整備してみたい

 

家のあらゆるものをIoT化してスマホで管理できるアプリを作ってみたい…

 

 

 

普段雑誌なんて読まないけどこういう技術紹介本は大好き

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を買った

 

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

 

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

 

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