京都のITベンチャー企業を退職しました
はじめに
京大の学部2回生の時から約1年程お世話になったある京都のITベンチャー企業を退職しました。退職したのは今年の7月なので、ちょっと時間が経ちましたが、自分の備忘録としても、これからエンジニアを目指す人にとっても少しくらい役に立つかなと思って書いてみようと思います。最初の方は割と入社前とかの話になるので、面白くなかったら飛ばしてください。
入社前
1回生
京大に特色入試で合格したこともあって、周りより早く合格が決まっていましたが、特にこれといったこともせずだらだらと過ごしていたら入学していました。最初はフットサルのインカレのサークルとかに入っていたりしましたが、同期とそりが合わずに辞めました。
アルバイトはというと、最近流行っているウーバーイーツのサービスが開始されてすぐくらいの時期だったので、その配達員をやったり、家の近くの飲食店をやったり、ブライダルのバイトをやったりしていましたが、どれも自分に合わないと感じて半年くらいで辞めました。一番続いたのが塾講師のアルバイトで、一年くらい続けてました。
つまらない大学生活
高校の時の同期はサークルとかで楽しそうにしているのを横目で見ながら、ずっと羨ましいなと感じていました。正直サークル選びをミスった感じしかなくて、でもこれから新しいサークルに入るのは自分としてはハードルが高く、大学の電電の人とは最初から知らない間にできてたグループでつるんでて、それも今から絡みに行けるような感じでもなかったので、結局大学で新しい友達とかもあまりできずにっていう感じでした。今までは友達とか意識せずとも普通にできてたのに、まさか大学に入ってから人間関係で悩むことになるとは思ってなかったです。中高と結構勉強頑張ってきて、大学生になったら薔薇色のキャンパスライフが〜みたいに軽く妄想してたので、それと現実との違いに落胆しました。
ただ、現状を悲観してても仕方がないので、逆にこの時間が有り余ってる状況を上手く使って、俺は普通の大学生ができないくらいの経験を大学生のうちから蓄えて、社会に出た時に既に追いつけない程の差を付けてフライングでスタートしてやろう!みたいな思いを勝手にメラメラ燃やしてました。
プログラミングとの出会い
そんな時に出会ったのがプログラミングです。最初はなんかできたらかっこいいなといった程度で、言語はみんなが使ってそうだったという簡単な理由でPythonを始めました。最初はなんか好評ぽかったのでProgateから始めました。
ProgateのPythonのコースが終わってから、じゃあ次何やればいいんやってなりました。Twitterとかを見ているとみんな奇想天外な面白い発想でいろんなサービスとかを作っていて、Progateやったら自分も何か作れるようになると思ってましたが、全然甘かったです。確かにProgateやっただけで色んなサービス作れる天才もいると思いますが、残念ながら自分は凡人だったのでそんなことができる訳もなく、そもそもPythonでどんなことができるのかもよく分からなかったので、Pythonを学習し始めてから1ヶ月も経たないうちに辞めました。
競プロをやり始める
そんなこんなでまたバイト漬けのくだらない生活が始まりましたが、いつだったかAtcoderに出会いました。これなら別にプロダクトの発想とか必要ないし、純粋にプログラミングをやってる感じがあるので、これにのめり込みました。
最初の方は全然解けませんでしたが、途中からコツをつかんできて、C問題くらいまでは安定して解けるようになりました。その頃はAtcoderの問題の解説とかもやってましたね。(ブログを引っ越したので、昔解説してたのがこのはてブロにあがってます)
茶色に上がったくらいからアルゴリズムの壁が見え始めて悩んでました。ただ、Pythonには慣れてきて、愚直に問題を解くだけなら全然書けますし、初期の頃よりは上達したなとは思ってました。
この辺りから、実際にモノを作りたいなという気持ちが強くなってきました。競技プログラミングをこのまま続けてても何も作れるようにはならないなというのは分かっていながら、じゃあ何を勉強したら何が作れるのかもよく分からず、ずっと暗中模索してるような感じでした。
会社でアルバイトとして働いて実力をつけていくというのは当然考えていましたが、自分の実力程度で雇ってくれる会社があるのかということや、そもそも当時は塾講師のバイトをやってそれなりに稼いでいたので、もし雇ってもらえたとしてもここから離れて収入が減ってしまうのも良くないななどと散々理由をつけて、結局何も行動しないまま2回生になっていました。
2回生
2回生になってしばらくしてコロナが猛威を振るってきて、塾もリモートで行うようになっていました。その辺りから自分を冷静に客観視できる時間が増えてきました。塾講師のモチベーションも下がってきていて、このまま続けていたら結局自分は大学生活でサークル活動も何もしないまま終わるただの大学生で終わってしまうと感じて、自分の退路を無くすために半ば勢いで塾講師を辞めました。
その後京大の求人募集で見つけたのが、これまで働いていた会社でした。
入社
選考
入社前に選考がありました。履歴書選考を通過した後は3日間実際に働いて、社員の方に良いと思ってもらえれば採用されるといった形です。その時はOpenCVのモルフォロジー変換あたりを軽く触って、途切れ途切れの線を繋げるというものを3日間で実装するというようなことを確かやったと思います。
ただ、これも今となってはモルフォロジー変換というワードが思いつきますが、当時は途切れ途切れの線を繋いでというアバウトな指示だったので、そもそも何を使えばいいのかすら知りませんでした。当然OpenCVも知りません。ただ、社員の方になんやかんやアドバイスをもらったりする中でなんとか実装して、採用の連絡をいただきました。
アルバイトとして入社
なにはともあれ、運よく会社に拾ってもらって、アルバイトとして働き始めました。今思えばよく拾ってくれたなと思います。その会社がまだまだ小さい会社で、働き手を欲していたからこそ運よく拾ってくれましたが、普通に大きくなってくると実務経験、あるいは何らかの開発経験は必要になると思いますし、現に今アルバイトとして入社する人達はある程度のスキルがないと落とされます。(実際僕も社員になってか何人かアルバイトの採用業務を行いましたが、残念ながら書類選考で落としてしまう人も何人かいました。)
入社後最初に行ったのは3次元マッチングでした。PythonのOpen3dというライブラリを用いて、3次元デプスカメラを用いてある部品を3次元マッチングするというものです。正直もうあまり覚えてないですが、こんなのをやってたと思います。
実務経験0だったので、環境構築から当然詰まりましたが、その辺は色んな人に助けてもらいながらなんとかしていました。この辺で分からないことの調べ方とかが身についていったと思います。今思えばopencvをすっ飛ばしてopen3dやってたのは結構ハードだったなぁと思います。
ハードウェアエンジニアへ
うちの会社が結構特殊で、何でもかんでも3dプリンターで作るという所だったので、色んなものを3dプリンターで作っていました。それが結構面白そうだったので、CADの設計から始めて、色々なものを3dプリンターで作るハードウェア(寄りの)エンジニアになりました。この選択が最後まで続くことになります。(今はちょっと後悔してたりします笑)
当時は設計したものが実際に目に見える形で生成される3dプリンターがとても面白くて、ソフトウェアよりハードウェアの方が絶対面白いと思っていました。実際色々設計してプリントするのは楽しかったです。
CADの勉強の集大成として、パーツフィーダーというものを作るということになりました。パーツフィーダーって聞き慣れないと思うんですけど、こういうものですね。
ネジを同じ向きに揃えて供給するというような機械です。これ、結構高いんですよね。これを3dプリンターとかで内製化できたら安上がりで済むってことでこれ作り始めました。こんなん簡単そうちゃうかっていうことでポイっと仕事振られて、確かに自分も最初は簡単そうだと思ってたんですけど、やっぱり高いだけの理由があるなって感じで、かなり難しかったです。角度とか、振動のさせ方とか色々ちゃんと設計しないと難しい。なんやかんやで1ヶ月くらいかかって、ようやくプロトタイプが完成しました。
パーツフィーダーのデモ機がついに形になった、、、
— タムログ (@tamlog06) 2020年10月27日
まだまだ改善点はあるけど、とりあえず動いてくれてほんとに嬉しい pic.twitter.com/SxMgeWP5LL
スローじゃないとこんな感じ pic.twitter.com/Vrar0PAkUE
— タムログ (@tamlog06) 2020年10月28日
これは本当に嬉しかったですね。達成感半端なかったです。ちなみにこれくらいの時期に、時給が1200円から1300円くらいに上がった気がします。
ただ、結局このパーツフィーダーは使われることがありませんでした笑。パーツフィーダーを何十年開発してる会社と上司が話すことがあったようで、その辺でこの難しさに気付いたのも一つの理由かとは思いますが、単純にこの装置に人件費を使い過ぎてしまったようで、中止になりました。自分的にはあともう少しで完成しそうという所だったので、ショックでしたね。
正社員へ
他にもなんやかんや案件の開発をしたりして、1ヶ月ごとに時給が100円から150円くらい上がっていくとかがあって、最終的に1550円になりました。その後2020年12月勤務分から正社員として勤務し始めました。アルバイトと正社員の違いは
- 時給制から固定給へ
- 3ヶ月に1回のボーナス
- ストックオプションの権利
- 開発責任者となる
こんな感じです。僕はこの中でもストックオプションの権利に目をつけて社員になりました。上場した場合に数千万程度のお金が入ってくるということで、実際に当時は1〜2年で上場するという話だったので、これは美味しいと思いました。反面、固定給というのが厳しそうだなとは思っていました。時給制じゃなくなるので、どれだけ残業しても同じ額しか支払われないという契約です。ただ、当時はそこまで激務ではなく、残業(深夜労働)も納品直前とかに徹夜で働いたりする程度で、そこまで多くなかったので大丈夫だと思っていました。
その後5人程度のハードウェアユニットというのが結成され、そのユニット長として開発を進めることになります。
開発地獄
見出しの通りです。完全に社員は地獄への一歩でした。社員になってからはまず1つの小さめの案件が任されました。それは画像処理がメインの案件で、そこまで大きな案件ではなかったのですが、技術的な不可能性から炎上寸前でした。今思えば、開発前から厳しい案件であることは分かっていたのに、なぜ上から投げられたものをそのまま作ったのだろうと思います。もう少ししっかり検討して、方向性を変える提案をもっと早めにできていればここまで苦しまなかったのかなと思ってしまいますね。
本来これは12月中に終わらせるもので、実際なんとか形にはなったものの、ちゃんとした形にはならず納品は翌年に持ち越すことになりました。ただ、元々装置を2台納品するということで、この案件を振られたのが12月に入ってからなので、日程的には相当無理があるものでしたが、年度末ということで仕方なくやることになりました。最終的には僕が会社を辞める7月までもつれ込むことになります。本当にここまで長引くとは思ってなかった。。。
さて、年が明けてからどんどん激務になってきます。キャパを超えてどんどん増えていく案件の量。社員になる前は1〜2個の案件を任されると思っていたのですが、気付いたら7個の案件を持っていました。しかもその中の3つが1000万円相当の案件です。
当然全てを並列に処理する訳ではなく、優先順位をつけてこなしていく訳ですが、当時の僕のユニットは会社に入った直後でスキルがあまりないアルバイトの人が多く、案件を丸々任せることは不可能なので、こま分けした内容を振っていくということになるんですが、どれも結局自分がやった方が早いし確実だと思ってしまって、アルバイトの人に上手く仕事を振れず、自分が仕事に潰れました。単純に各案件の単価が高いことなども、余計プレッシャーに繋がって、深夜まで残業して働くのは当然みたいな感じでした。
今思えば当たり前なのですが、ほぼ初心者の方で構成されたユニットを任されて、さらにそのユニットの人数以上の数の案件をこなすため、それぞれの仕事をアルバイトの人がこなせる程度の仕事に分割し、それを割振りながら自分も開発するなど、到底不可能だと思います。そもそもタスクを割り振りした経験すらないのに。。。
毎日残業、家に帰ったらご飯を食べて酒を浴びるように飲んで、風呂に入って深夜に寝る。次の日は当然授業なんか間に合わないから昼過ぎに起きて準備をして出勤。本当に社畜のような生活を送っていました。
とは言え自分だけが残業しているのではなく、上司も他の社員も残業しているので、特に文句を言う訳でもないですし、そもそも自分の能力がないから残業になってしまうんだと思ってました。そうは言っても毎日他のどの会社の人間よりも遅くまで会社に残って開発してました。深夜1時に退勤とかよくある話です。
転機
さて、このような毎日を過ごす中で、幾分心の支えになったのがアルバイトとして入社してくれた友人など、会社の人達です。あと、彼女の存在も大きかったですね。家に帰ったらご飯を作ってくれてたりして、孤独感を感じなかったです。彼女がいなければ普通に精神崩壊してました。仕事のしんどさでやめようと思った事は何度もありますが、自分が辞めると彼らに直接負担がかかることが分かっていたので、どうしても踏みとどまっていました。
ただ、ある時ふと考えたのが、このままこの会社で働き続けることは自分にとってメリットがあるのだろうかという事でした。働く理由が他人に迷惑をかけたくないという負の考えのみになってしまっている現状は本当に良いのかという事を考えて、現状を冷静に考えることにしました。
実際僕の業務内容は、CADを描いて装置の設計を行い、PythonでArduinoと通信してロボットを動かしたり、Opencvとかで画像処理を行ったりするといった具合で、会社の内部での希少価値は高かったと思うんですけど、社会に出たときに僕のこのスキルって全然活かせないなと思ったんです。僕は当初から、サークルで遊びまくってる一般的な大学生より何倍も努力して、もう一生追いつけないような差を就職前から付けておく、要はフライングしておきたいなと思ってた訳です。それが気付いたら社会に役に立つかと言われると、そこまで必要とされていないスキルを身につけている訳です。これはどうなんだろうと。別に役に立たないスキルなんてないんですけどね。ただ、じゃあもし自分が将来的にアプリ開発エンジニアになるとして、この仕事がアプリ開発に直接活かせるかって言われると、全く関係ないわけで。正直将来的にCAD描いて開発するエンジニアになる未来は全く見えなかったですし、なんならもう描きたくなかったですし。
確かこの辺りだったと思うんですけど、twitterにカズレーザーさんの言葉が流れてきました。
人間なんて皆んな大したことない
— ぐっち🔰投資×転職 (@gucci_bonjin) 2021年2月23日
だから背負うものなんて何もない
こういう考え方できれば、人生楽になるし楽しめる気がします。 pic.twitter.com/ofhd0lMuPX
いや、ハッとしました。確かに自分が会社を辞めたら迷惑をかけてしまう人はいっぱいいます。けど、ジョブスでも替えがきくんだから、自分なんか辞めても大丈夫だろうと。こう考えてからは楽でしたね。結局自分に都合の良い考え方じゃんって訳なんですけど、良いじゃないですか。やっぱり交友関係は大事ですけど、だからと言って自分より他人を大事にして、自分の気持ちとかを疎かにするのは良くないなと思ったんです。
退職
それから色々時期を見て、確か5月くらいに上司に連絡をとって、7月に辞めることになりました。やめるにあたって、引き継ぎ書類を完璧に用意したり、今まで持ってた案件を完遂させたり、色々大変だった訳ですが、なんとか全て完成させ、7月中を持って会社を退職する運びになりました。
引き継ぎはかなり大変で、というのも今後僕にほとんど連絡が取れなくなる訳ですから、僕が開発してたものを引き継いでくれる人が詰まった時に聞ける人がいない訳です。その際に参考にする資料を作るので、あらゆるケースに対応した資料を作る必要があって、本当にこれでもかってくらい細かく書きました。
これからエンジニアを目指す人へ
こんな感じで未経験からベンチャー企業にアルバイトとして入社し、途中から正社員になって勤務してきた会社を退職した訳です。
最近はプログラミングスクールとかが流行ってきて、駆け出しエンジニアの方々も増えてきていると思うので、僕の経験を元にこれからエンジニアになろうと思う人に僕の考えを伝えたいと思います。
ベンチャーで働くということ
僕の考えは、ベンチャーはスキルをつけるのにはもってこいだが、のめり込むのはよくないという事です。
特に僕のように地方の学生になるにつれて、エンジニアの求人は少ないと思います。東京は溢れているように感じますが、京都は本当に少ないです。これがもっと地方だと、より限られてくるでしょう。そして、その中でも未経験可な求人はもっと少ないと思います。自分も採用をしていた身なのでわかりますが、未経験エンジニアは雇いたくありません。というのも、学習コストが高く、自分の時間をその人を成長させるのに使わなければならないからです。小さな会社ほど、各個人の担当範囲が広くなりがちなので、この傾向は大きくなるのではないでしょうか。
その中でも、未経験可、あるいは募集条件が緩めなところを見つけた場合は、迷わず応募してみるのがいいかと思います。正直プログラミングスクール程の高額な費用をかけなければプログラミングを勉強できないのなら、エンジニアに向いていないと思います。世の中には本やweb教材など、もっと安価で、あるいは無料で学習できるサービスがあるので、それを有効活用すべきですし、そもそもエンジニアバイトをすればお金をもらいながら勉強できるからです。
エンジニアバイトはブラックなのか
エンジニアバイトはブラックだという話をよく聞きますし、実際僕もそうでしたが、社員になるまでは働きやすい環境でした。どの会社もそうとは限りませんが、そこまで過酷な環境で働かせることは、自分がその会社にのめり込まない限りはそうないと思いますし、何より自分に合ってなければ辞めればいいだけの話です。
実際僕は未経験から1年程度で、それなりにエンジニアとしての力はついたと思いますし、エンジニアの力をつけるにはある程度の過酷な環境に身に置くのも必要な過程なのではと思います。
すごい人に出会える
あと、ベンチャーじゃなくてもそうだと思うんですけど、会社で働くと、世の中にはとんでもない人がいるんだなと思って、いかに自分が小さな存在かってのを再確認できるんじゃないかなと思います。特に僕の上司がそうだったんですけど、特色入試で京大に入った電電の先輩に当たる人なんですけど、とにかく最初はエンジニアで、プログラミング力が化け物みたいな人でした。色々すごいところはあるんですけど、一番は問題解決能力が半端ないんですよね。コーディングでもそうなんですけど、特にハードウェアに関しては、ロボットが上手く動かない時に色々原因が考えられるんですよね。電源供給が上手くいっていないとか、断線してるとか、電流が足りてないとか、配線が間違ってるとか、そもそもプログラムがおかしいとか。しかも純粋なプログラミングとは違って、エラーメッセージとか出てこないから、どうなっておかしくなってるのかすら分かりにくい。しかもそれらが複数原因となって動作不良を起こすことが多くて、結構未知の現象に遭遇することが頻繁に起きるんですけど、そういう時に僕なんかは考えはするものの割と手探り状態になってあちこち歩きながら進んでしまうんですけど、その人は着実に根本の原因に向かって一歩ずつ踏み込んで進んでいけるというか。
後はマネジメント力ですね。グループ長で10数個の案件をもらってきて、それを僕ら各ユニットに振るという感じになるんですけど、予定表は平日も休日も朝から晩までミーティングだのなんだので予定がパンパンで、なのにちゃんとタスクは振れる。立場上反感を受けやすい立場ではあるんですが、やっぱりすごいです。僕はどうやってもこの人にはなれないなと思いました。
ただ思うのは、僕が目指す像はそもそもこの人ではないなということです。僕は小さい頃から、身近の人で尊敬できる人を見つけて、その人に同化していくことで自分を成長させるということをよくしていました。従って、自分よりすごい人が多い環境に身を置くことで、どんどん自分を成長させることができる訳です。というわけで、僕はずっとこの上司を目標に頑張ってきたのですが、彼は僕の目指すエンジニア像ではないなと感じて、それも僕が会社を辞めようと思った一つの原因でした。
ともあれ、僕が言いたいのは、企業に入ると、こういう分かりやすくすごい人って大体いるんじゃないかなと。そういう人を目指して開発していくことで、どんどん成長していけるんじゃないかなと思います。だからある程度基本の文法とかを身につけた段階で、天才じゃない限りはすぐに企業でアルバイト探したら良いと思います。ものを作れる天才だったら、勝手に色んなサービス作っていけば良いと思いますけどね。僕もそんな天才になりたかったな。
これからについて
7月に退職後、学校の試験が待ち構えていました。途中で言ったように5月くらいからまともに授業を受けてないので、ほぼ0の状態から1ヶ月くらいで準備しないといけません。しかも行きたい研究室は割と人気があるという噂があったので、結構いい成績を取らないといけません。死ぬ気で勉強して、なんやかんや試験を乗り越えて夏休みはだらだらしてだいぶ気分転換できました。その間web系のエンジニアをやってみたくてrubyやrails、javascript辺りを軽くさらって、webサイトを作ったりしていました。そんなこんなで、同じく京都のweb系の会社に縁があって、これからまたアルバイトとして働かせてもらうつもりです。エンジニアとして社員になってちょっと痛い目見ましたが、懲りずにエンジニアとしてアルバイトをしていきます。これはやっぱり楽しいからですね。きつい時はきついですけど。やっぱり何かモノを作れる、創造的なことって楽しいんですよね。楽しみながらスキルもついて、お金もどっさりもらえる。こんなにいいバイトはないと思います。少なくとも自分が今までしてきたバイトの中では最も良いバイトだと思います。
おわりに
というわけで終わりです。結局言いたいことがまとまってなかったかもしれないですが、最後に強調すると、ベンチャーはスキルをつけるのにはもってこいだが、のめり込むのはよくないってことです。あと、機会があれば企業でアルバイトしてみたらいいんじゃないかってこともそうですね。エンジニアバイトは他のバイトと比べても全然時給もいいですし、勉強もできるしで本当にいいバイトだと思います。
とりあえずまだもうちょっと学生でいられるので、バリバリスキル身につけていければなと思います。ここまで読んでくださってありがとうございました。
スタックとキュー
ここでは,スタックとキューについて説明していきます。これは Python に限ったものではなく,どの言語でも共通のもので,簡単に言うならデータの構造です。
また,データを追加することを push,データを取り出すことを pop と言います。
スタック
- スタックでのpush は,データの一番上にデータを積むこと
- スタックでのpop は,データの一番上のデータを取り出すこと
実際にコードを書いてみます。Python で実装する場合は collections の deque モジュールをインポートします。
from collections import deque
s = deque([])
s.append(1) # s=[1] この操作が push
s.append(2) # s=[1,2] これもpush
p = s.pop() # s=[1] この操作がpop
print(p) # 2
キュー
- キューでの push は,データの一番上にデータを積むこと
- キューでの pop は,データの一番下のデータを取り出すこと
先ほどのスタックとの違いは,pop(データの取り出し) の方法です。スタックではデータの一番上のデータを取り出しましたが,キューではデータの一番下のデータを取り出します。
実際にコードを書いてみます。
from collections import deque
q = deque([])
q.append(1) # s=[1] この操作が push
q.append(2) # s=[1,2] これもpush
p = q.popleft() # s=[2] この操作がpop
print(p) # 1
以上,スタックとキューについて説明していきました。その違いは,データを上から取り出すか,下から取り出すかというものでした。もし分からないところがあればコメントをしていただければと思います。
Pythonにおける約数の高速列挙の解説
ここでは Qiita で @LorseKudos さんが紹介している
を自分の備忘録としても紹介,解説していきたいと思います。
競技プログラミングをやっているときに約数の列挙の作業が求められることがかなりの頻度であります。簡単に約数の列挙を行おうと思えば sympy をインポートして
import sympy
sympy.divisors(n)
これで出せます。ただし,競技プログラミングでは sympy が使えないのでこの方法が使えません。そこで今回は先ほどのサイトで @LorseKudos さんが紹介して下さっている次のコードを用いることで,競技プログラミングでも約数の列挙を高速に行うことができます。
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
# divisors.sort()
return divisors
ただ,なぜこれで約数が列挙できるのか分かりにくいかと思いますので(少なくとも私は理解するのにかなり時間がかかりました😅)説明していきます。
まず3行目。なぜ探索する範囲が
range(1, int(n**0.5)+1)
で良いのかについてです。i <= j として i,j を n の約数としたとき,
n = i × j
の関係が成り立ちますよね。そうすると,i は √n 以下でなければなりません。
どちらも √n 以上であれば,i × j >= √n × √n = n となってしまいます。
なので少なくとも1から √n の範囲で探索をしてあげれば良いわけです。もし i が n の約数であることが分かれば,j も n から i を割ってあげることで出せますよね。
よって,4,5行目はこの範囲の i において以下の作業を行っています。
if n % i == 0:
divisors.append(i)
これは,もし i が n で割り切れる(= n の約数)なら,約数の要素に i を追加するというものです。
さらに同時にこの約数 i が特定された後に次の分岐を行っています。
if i != n // i:
divisors.append(n//i)
これは先ほどの j を約数の要素に追加するものです。
if 分岐は,i が n の平方根であった時に約数のダブりを無くすための分岐です。つまり i=√n だったとき,
n = i × j = √n × √n
となり,i = j となるので,このまま j を約数の要素に加えてしまうと,√n が二回カウントされてしまいますよね。
j と i が同じ値でないことが確認されたのち,j = n ÷ i なのでその値を約数の要素に追加しているわけです。
j は int 型にしたいので n//i として追加しています。
最終的に divisors に格納された約数の要素を返すようにすれば,これで約数を列挙できたことになります。
1~√n までの探索なので,O(√n)で約数列挙をすることができます。👍
ただしこのままでは順番がバラバラなので,ソートしなければならないときは9行目のソートをすればいいわけです。
いかがでしょうか。
このような仕組みでこのコードが成り立っているわけです。
もし何かあればぜひコメントよろしくお願いします!
それでは!
AtCoder Beginner Contest 161 F を Python で
さて,いよいよ最後の F 問題の Python での解説に移ります。コンテスト中は E より F の方が解けてる人が多かったみたいだったので,E を飛ばしてこの問題を見てみたのですが,流石にまったく歯が立ちませんでした😅
でも Atcoder の解説を見て実装できたので,今回もかなり分かりやすいようにかみ砕いて解説していきたいと思います!
それではまずは問題から。
F – Division or Substraction
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
正整数 N が与えられます。
2 以上 N 以下の整数 K を決めて、N が K 未満になるまで次の操作を繰り返し行います。
- 操作:N が K で割り切れるとき、N を N/K に置き換える。そうでないとき、N を N−K に置き換える。
最終的に N が 1 になるような K の決め方は何通りありますか?
制約
- 2≤N≤10^12
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
最終的に N が 1 になるような K の決め方が何通りあるか出力せよ。
解説
N が K で割れるかどうかによらず,最終的に K 未満になるまで K を引き続けた結果が1になればいいのだから,N を K で割れるだけ割った後の値を N’ として,K を引ける回数を m とすると
N’ = K × m + 1
になればよく,2~N の全ての数 K に対して N’ を出し,N’ % K == 1 なるものの個数を出せばよいです。
しかし,これだと N の制約が最大 10^12 であるため,TLE を起こしてしまいます。もう少し試行する K の数を減らすことを考てみましょう。
まずは N が K で割り切れない時を考えてみます。この場合は N が K 未満になるまでただただ N から K を引いていくだけです。m 回 K を引けるとすると,最終的に N が1になるときは,
N = m × K + 1
このように N が記述できますね。この式を変形して
N – 1 = m × K
というようになります。N は2以上の整数なので,左辺は正の整数になります。従って右辺も正の整数 N-1 となり,m と K も正の整数であるから,結局 K は N-1 の約数ということになります。ただし,約数とは言ってももし K が1であったなら,N は 1(=K) 未満になるまで1を引くので,最終的に N は0になってしまい,題意に反してしまいます。
以上の考察から,N が K で割り切れない時は,K が N-1 の1より大きい約数であればよいということになります。
では次に N が K で割り切れる時を考えてみましょう。つまり,K が N の約数の時ですね。このときはまず N を K で割れるだけ割ってそのあと N が K 未満になるまで K を引き続けるという操作になります。
ということで,N を K で割れるだけ割った後の値を N’ とすると,その後 N’ が K 未満になるまで K を引き続けた結果1になればよいので,m 回 K を引き続けることができるとすると
N’ = K × m + 1
となり,結局 N’ を K で割った余りが1になればいいというわけです。
以上より,調べるべきは
- N-1 の1以外の約数の個数
- N の1以外の約数のうち,上記の N’ を K で割った余りが1になるものの個数
となり,2~N の範囲までの全ての整数で試行を行う必要はなく,かなり試行の数は減ります。
あとは実装するだけですが,まずは N-1 と N の約数の列挙が必要です。これについては
で解説していますので,これを参照してください。
約数を列挙した後は,それぞれの約数の要素から1を取り除きます。
N-1 の約数の個数はこれで出ますが,N の約数については N’ を出して N’を K で割るという試行が必要なので,これを for と while のループで実装してみました。
それでは,解答例を載せておきます。
解答例
n = int(input())
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
# divisors.sort()
return divisors
# N-1の約数の列挙
a = make_divisors(n-1)
# Nの約数の列挙
b = make_divisors(n)
# 約数から1を取り除く
a.remove(1)
b.remove(1)
count = len(a)
for k in b:
# まず1回nをkで割ったものをn_newという変数に入れる
n_new = n // k
# n_newをkで割れるだけ割る
while n_new % k == 0:
n_new = n_new // k
# 最終的にkで割った余りが1ならcountに1を追加
if n_new % k == 1:
count += 1
print(count)
どうでしょうか。
F問題とはいえ,そこまで複雑なことをしなくてもコーディングすることができました!
ただ,これをコンテスト中にできるかと言えば・・・😔
もっと頑張るしかないですね(笑)
それでは!
AtCoder Beginner Contest 161 E
AtCoder Beginner Contest 161 E を Python で解説していきます。初見のときは,いつもの問題よりも問題設定が簡単めかなぁと思いましたが,実際にコーディングしようとすると全然手が出ませんでした。(笑)
ただ,問題設定自体は理解しやすい問題だと思います!😀
AtCoder の解説を見てじっくり考えてから自力でコーディングして AC できましたので,これを基に解説していきたいと思います。
それでは早速いきましょう!まずは問題文から。
E – Yutori
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋君は明日からの N 日間のうち K 日を選んで働くことにしました。
整数 C と文字列 S が与えられるので、次の 2 つの条件を満たすようにして働く日を選びます。
- ある日働いたら、その直後の C 日間は働かない
- S の i 文字目が 'x' のとき、今日から i 日後には働かない
高橋君が必ず働く日をすべて求めてください。
制約
- 1≤N≤2×10^5
- 1≤K≤N
- 0≤C≤N
- S の長さは N
- S の各文字は 'o' か 'x'
- 問題文中の条件を満たすように働く日を選ぶことが可能
入力
入力は以下の形式で標準入力から与えられる。
N K C
S
出力
高橋君が必ず働く日を昇順に改行区切りですべて出力せよ。
解説
1つ目の設定は,j 日目に働くと次に働けるのは C 日間の休暇を挟んだ j + (C+1) 日目になるというもので,2つ目の設定は文字列 S が与えられて,その i 番目が i 日目に働けるかどうかを表しており,’o’ なら働け,’x’ なら働けないということです。
まずは入力例1を見てどういう思考過程を経ればいいか考えてみましょう。入力例1は以下です。
11 3 2
ooxxxoxxxoo
11日間のうち3日働き,それぞれ2日のインターバルが必要という設定ですね。実際に出力を考えるときは S を見ながら1日目から可能なものを考えて,
(1,6,10),(1,6,11),(2,6,10),(2,6,11)
この4パターンが考えられます。よって全てに共通している6を出力します。
この思考から,もし働く日数を最大にしたいのなら,1日目から貪欲に設定に当てはまるものを考えればいいことが分かります。上記の例の場合,これは(1,6,10)がこれに当てはまりますね。これを L = [1, 6, 10]としておきます。
働く日数が最大の場合とは結局どういうことなのでしょうか。これはつまるところ i 回目に働くのはL[i-1]日目以降ということになりますよね。どういうことかというと,L の場合が最大限に働く場合なのだから,例えば1回目に働くのは1日目以降,2回目に働くのは6日目以降でなければなりませんよね?
つまり,左から貪欲に働く日数を出していき,それを L という配列にすると,L は i 番目に働く日が L[i-1] 日目以降になるということが分かります。同様に今度は右から貪欲に働く日数を出していき,それを R という配列にすると, i 番目に働く日が R[i-1] 日目以前になるということが分かります。先ほどの例では (2,6,11) がこれにあたります。
ではこの L と R を求めたら何が分かるのか?についてです。
L[x] と R[x] はそれぞれ x 回目に働くのが L[x] 日目以降,R[x]日目以前ということなので,もし L[x] = R[x] = i となるような x があるなら,その x 回目に働くのは i 日目以降,i 日目以前,ということはつまり i 日目ということになって,x 回目に働くのは必ず i 日目であるということになります。
従って,実装すべきは貪欲に L と R を出して,その後条件分岐を設定して L[x] = R[x] = i となるような i を出力するというものです。ここまでくればコーディング自体はそこまで難しくはないと思います。
では,解答例を載せます。
解答例では S の最初に 'x’ を加えることで,S のインデックス番号と日にちを同じ値にしました。
また,R を出すときに後ろから貪欲でリストに追加していくと降順で追加されてしまうので,L と対応させるために R[::-1] で順序を逆にしました。
解答例
n,k,c = map(int,input().split())
s = "x" + input()
l = []
i = 1
# 前から貪欲
while len(l) < k:
if s[i] == "o":
l.append(i)
# i日目に働くと次に働けるのはc+1日目
i += c+1
else:
# その日働けないなら次の日に回す
i += 1
# 後ろから貪欲
r = []
i = n
while len(r) < k:
if s[i] == "o":
r.append(i)
i -= (c+1)
else:
i -= 1
# rを降順から昇順に
r = r[::-1]
for i in range(len(l)):
if l[i] == r[i]:
print(l[i])
やはり E 問題になると難しいですね。😅
ただ,発想自体はかなり面白いなと思いました!
それでは!
AtCoder Beginner Contest 160 E を Python で
AtCoder Beginner Contest 160 E を Python で解説していきたいと思います。
コンテスト中には解けなかったのですが,後で時間をかけて考えることでなんとか解くことができました。
考え方が大事で,思いつけば処理時間もあまり長くならず,実装も簡単という問題になります。
それでは,まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_e
E – Red and Green Apples
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
あなたは、X 個の赤色のリンゴと Y 個の緑色のリンゴを食べようとしています。
あなたは A 個の赤色のリンゴを持っており、美味しさはそれぞれ p1,p2,…,pA です。
あなたは B 個の緑色のリンゴを持っており、美味しさはそれぞれ q1,q2,…,qB です。
あなたは C 個の無色のリンゴを持っており、美味しさはそれぞれ r1,r2,…,rC です。
無色のリンゴは食べる前に着色することで、赤色のリンゴもしくは緑色のリンゴと見なすことができます。
以上のリンゴの中から、できるだけ美味しさの総和が大きくなるように食べるリンゴを選びます。
0 個以上の無色のリンゴに適切に着色したとき、食べる X+Y 個のリンゴの美味しさの総和が最大でいくつになるか求めてください。
制約
- 1≤X≤A≤10^5
- 1≤Y≤B≤10^5
- 1≤C≤10^5
- 1≤pi≤10^9
- 1≤qi≤10^9
- 1≤ri≤10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y A B C
p1 p2 … pA
q1 q2 … qB
r1 r2 ... rC
出力
リンゴの美味しさの総和の最大値を出力せよ。
解説
赤いリンゴが A 個,緑のリンゴが B 個,赤と緑どちらとも見なせる無色のリンゴが C 個あり,この中から赤いリンゴを X 個,緑のリンゴを Y 個選び,その美味しさの最大値を求めよという問題です。
まずは赤いリンゴ,緑のリンゴ,無色のリンゴをそれぞれ美味しさの降順にソートしておきます。
すると,赤いリンゴは X 個しか選ばないので,最大でも赤いリンゴは X 個しかいりません。なので赤いリンゴの美味しさが X 番目より小さいものは捨てます。緑のリンゴも同様に Y 番目より小さいものは捨てます。
Python ではこれを以下のように実装できます。
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
p = p[:x]
q = q[:y]
こうすることで,赤いリンゴが X 個,緑のリンゴが Y 個,無色のリンゴが C 個になりました。
あとはここから無色のリンゴを考慮して赤いリンゴを X 個,緑のリンゴを Y 個選べばよいのですが,例えば無色のリンゴの一番おいしいものの値が,赤いリンゴの一番おいしくないものの値よりも小さいとします。
このとき,赤いリンゴの一番おいしくないものを捨てて,無色のリンゴの一番おいしいものを赤いリンゴとみなせば,結局赤いリンゴを X 個選んだことになります。
これより,現在残っている赤いリンゴ X 個,緑のリンゴ Y 個,無色のリンゴ C 個 のなかから,最もおいしいものを上から X+Y 個選んで,その値の合計を出力してやればよいです。
従って,まず残りのリンゴをすべて合わせたリスト pqr を用意し,それを降順にソートして,上位 X+Y 個の値の合計値を出力します。
では,解答例を載せておきます。
解答例
x,y,a,b,c = map(int ,input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
p = p[:x]
q = q[:y]
pqr = p + q + r
pqr.sort(reverse=True)
yamm = sum(pqr[:x+y])
print(yamm)
いかがだったでしょうか。
コード自体は複雑な操作をしておらず,いたって簡単なものとなっていますが,解答するまでの考え方が難しいというような問題でしたね。
もし少しでも参考になったら,twitter でシェアをお願いします!
それでは!
AtCoder Beginner Contest 169 D を Python で
お久しぶりです。タムログです。少しモチベーションが下がってしまってコンテストをさぼっていたのですが,今回から再開して,また解説ブログも書いていきたいと思います。今回はまずAtCoder Beginner Contest 169 D を Python で解説していきます。続いてA~Cも書いていきますので,そちらもまた書いたらご覧ください。
それでは,まずは問題文から。
実行時間制限: 2 sec / メモリ制限: 1024 MB×
配点 : 400 点
問題文
正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
- ある素数 p と正の整数 e を用いて、 z=p^e と表せる
- N が z で割り切れる
- 以前の操作で選んだどの整数とも異なる
- N を、N/z に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- 1≤N≤10^12
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
24
出力例 1
3
例えば、次のように操作を行うことで、 3 回操作を行うことができます。
- z=2(=2^1) とする。( 操作後、N=12 となる。)
- z=3(=3^1) とする。( 操作後、 N=4 となる。 )
- z=4(=2^2) とする。( 操作後、 N=1 となる。 )
入力例 2
1
出力例 2
0
一度も操作を行うことができません。
入力例 3
64
出力例 3
3
例えば、次のように操作を行うことで、 33 回操作を行うことができます。
- z=2(=2^1) とする。( 操作後、 N=32 となる。)
- z=4(=2^2) とする。( 操作後、 N=8 となる。 )
- z=8(=2^3) とする。( 操作後、 N=1 となる。 )
入力例 4
1000000007
出力例 4
1
例えば、次のように操作を行うことで、 1 回操作を行うことができます。
- z=1000000007(=1000000007^1) とする。( 操作後、 N=1 となる。 )
入力例 5
997764507000
出力例 5
7
解説
問題文を一言で言うと,N を素数の異なるべき乗で何回割れるかというような問題です。これはまず N を素因数分解すると見通しがつきます。とりあえず入力例1の n=24 の場合で考えてみると,
24 = 2^3 + 3^1 と因数分解できます。
こうすることで,今回割れる素数は 2と3 であることが分かります。
では,このときある整数 e を用いて何回 p^e の形を作って N を割れるか,と言うものですが,これは e を1から順番に見ていけばいいです。24の場合は,例えばまず割りたい素数を2としたときには
- 24 ÷ 2^1 = 12
- 12 ÷ 2^2 = 3
となり,これ以上素数2のべき乗(次は2^3)で割れないから,これで終わりです。
今度は素数3でも同じことをして,1回しか割れないから,結局24の場合は2+1=3を出力すればいいことになります。
64の場合も同様です。素因数分解すると
64 = 2^6 ですから,これは2だけで割ればよくて,
- 64 ÷ 2^1 = 32
- 32 ÷ 2^2 = 8
- 8 ÷ 2^3 = 1
となり,以上で出力は3です。
実際考えるときは N を割っていきましたが,素因数分解しているのでわざわざ N を割って考える必要はありません。素因数分解するときに出てきた素数のべき乗について,それぞれ
-1, -2, -3 ・・・
と順々に引いていって,0以上になるという条件の下で最大何回引けるか確認します。
例えば 3456 = 2^7 * 3^3 であれば,まず素数2について見ると
- 7 – 1 = 6
- 6 – 2 = 4
- 4 – 3 = 1
- 1 – 4 = -3 ←これはアウト
ですから,3回操作を行えて,素数3の時は
- 3 -1 = 2
- 2 – 2 = 0
- 0 – 3 = -3 ←これはアウト
となり,2回操作を行えて,結局合計5回操作を行えることになります。実際のコーディングの際はこのように操作する回数を計算することになります。
では,コーディングに移ります。素因数分解は
の記事を参考にさせていただきました。このコードによって,例えば24なら,
factorization(24)
// [[2, 3], [3, 1]]
というように素因数分解してくれます。これを用いて,for文を利用し,[i][1]の値を-1,-2,・・・とした結果,0以上になるという条件の下で何回引けるかという値を count に格納していきます。自分のコードでは,a を素因数分解したときの値を入れるリストとし,b を先ほど述べた for 文の中で,-1, -2, ・・・と引いていく数に対応させます。
素因数分解したときに出てくる素数pによって,Nは少なくとも p^1で一回は割れるので,まずそれぞれの素数に対して,count に1を足して,次にp^2,p^3・・・で割れるかというような判断をしています。
注意したいのは N=1 の場合で,この場合に限り1度も割れないので,これだけ別枠で0を出力するようにしています。
それでは解答例に移ります。
解答例
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
n = int(input())
count = 0
a = factorization(n)
if n == 1:
print(0)
exit()
for i in range(len(a)):
a[i][1] -= 1
count += 1
b = 2
while a[i][1] > 0:
a[i][1] -= b
if a[i][1] >= 0:
count += 1
b += 1
print(count)
いかがだったでしょうか。久しぶりに解説ブログを上げたのでなかなか書くのが難しいなと思いましたが,もし分からないところや間違っていると思われるところがあれば,気軽にtwitterで教えてください。
それでは!