pythonでアルゴリズムとデータ構造を書く キュー

アルゴリズムとデータ構造のプログラムをPythonで書く

4.3 キュー

class Queue:
    def __init__(self,size =100005):
        self.size = size
        head = tail = 0
    
    def next(self,n):
        return(n +1) % self.size
    
    def enqueue(self,x,y):
        P.append*1
        Queue.tail = (Queue.tail + 1) % self.size
    
    def dequeue(self):
        #print(Queue.head)
        x = P[Queue.head]
        Queue.head = (Queue.head + 1) % self.size
        return x
#プロセスの個数nと処理時間qを格納
n,q = map(intinput().split())
#Pにプロセスの列を格納
P = []
for x in range(1,n+1):
    name,t =input().split()
    P.append((name, int(t)))
#シュミュレーション
p = Queue()
Queue.head = 0
Queue.tail = n
elaps = 0
while  Queue.head != Queue.tail:
    #dequeueでプロセスの値を取得してuに格納
    u = p.dequeue()
    #print(u[1])
    #処理時間qとプロセスの時間を比較して小さい方を取得
    c = min(u[1],q)
    t2 = u[1] - c
    #print(t2)
    #処理時間elapsを加算
    elaps = elaps + c
    #t2(プロセスの時間 - 処理時間q)が0以上ならキューの末尾に追加、そうでないなら出力
    if t2 > 0:
        p.enqueue(u[0],t2)
    else:
        print(u[0] ,end=" "),
        print(elaps)

 

Cも別に詳しいわけではないので、

Cにてどのような実装なのか理解する⇒Pythonでの実装を考える

ってとこが大変

 

 

 

*1:x, y

pythonでアルゴリズムとデータ構造を書く スタック

アルゴリズムとデータ構造のプログラムをPythonで書く

4.2スタック

逆ポーランド記法で与えられた数式の計算結果を出力

str_list = list(input().split())
stack = []

for s in str_list:
    if s == "+":
        a = stack.pop()
        b = stack.pop()
        stack.append(int(b)+int(a))
    elif s =="-":
        a = stack.pop()
        b = stack.pop()
        stack.append(int(b)-int(a))
    elif s =="*":
        a = stack.pop()
        b = stack.pop()
        stack.append(int(b)*int(a))
    else:
        stack.append(s)
print(stack)

Pushとpopは面倒なのでappendとpopを使用

最初に入力をリストにしてるけど、

そうしなくても入力から繰り返しにできそうだけど思いついたら追記しよう

 

 

AtCoder Beginner Contest 148 一人反省会

 

A~Dはとけた、Dはもっとスマートに解けそうなきもするけど

E - Double Factorial
「末尾に何個の0が続くか」かポイント
階乗の末尾0の数ってのをカウントするのは数学であるらしい。

https://www.clearnotebooks.com/ja/questions/573304

とか

http://fukiyo.g1.xrea.com/math-qa/kaijou.htm

みたけど

10で何回割り切れるのか?
10=2×5
なので
素因数分解して2と5がセットでいくつ出てくるか?
入力例1 12×10×8×6×4×2=46080

だと

2で割れるのは、12、10、8、6、4、2の6個
5で割れるのは 10の1個

なので2と5のセットは1個なので答えが1となる

と言う考えを応用するれば解ける。

いや~こんなん気づけないな~。
でも、末尾0で検索したらヒントにはたどりつけたかも。

 

F - Playing Tag on Tree
頂点距離とDFSやBFSによる計算

DFSの参考
https://qiita.com/gogotealove/items/74cb3221228865aebc32

入力のグラフはなんとなくわかったきもするけど
青木君と高橋君の移動するのをどうやって実装するのだろう?

競技プログラミングでの計算量についてのリンク

C,D問題解くと時間オーバーとなるので

計算量について学ぶ

 

良さげな記事はこんな感じ

 

https://nowokay.hatenablog.com/entry/20090106/1231233947

 

 

 

https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c

 


https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0


本にもあったけど普通にやると多重ループになるのはそれを分解しろって解釈でいいのかな

 


先人の教えに感謝しつつ、

まだ理解がついて来ない

Atcoder以外の競技プログラミング

AtcoderのC,Dがとけない。
数をこなすにしても解説読んでもわからないときがあるし
(もっと初心者向けな解説がほしい)
ほかの競技プログラムのサイトは解説がわかりやすかったりするのでは?

と調べてみた。


hackerrank 英語のサイト
https://www.hackerrank.com/

問題の一覧はここから見れる
https://www.hackerrank.com/dashboard

問題にはそれぞれスレッドがあり、回答者が色々と議論をかわしているので
難しいものにはそこからヒントを探るがよいかも。

英語のサイトなので言語のハードルは高い
PCならグーグルのページ翻訳でなんとかなりそうだけど、
スマホアルゴリズムを勉強したいってのに向いてない


ポチポチ問題を解いてくとレートがあがるのは楽しそうだけど、
ちょっと今回の趣旨とははずれるので今は保留にしておく。


exercism
https://exercism.io/ こちらも海外サイト
52言語にわたる3,103のエクササイズと、
熱心なメンターの専任チームとの洞察に富んだディスカッションで、
プログラミングスキルをレベルアップします。運動は 永久に100%無料です。

課題があってそれを提出する方式らしいけど、
AtcoderのC,Dを解けるようになるための課題があるか調べるのが面倒だったので保留


TopCoderも似た感じ


AOJ(Aizu Online Judge:onlinejudge.u-aizu.ac.jp/home)
atcoderと似た感じ
問題に対する解説ページが見つからない・・・。


あれ?そうするとhackerrankで見てみるしかない?

でじたる とらんすふぉーめーしょん

DX

https://www.meti.go.jp/committee/kenkyukai/digital_transformation/pdf/001_haifu.pdf

 


実現に向けて人材が必要って言ってる

 


https://www.mizuho-ir.co.jp/publication/column/2018/itss0420.html

 


IPAの議事録面白い

 


https://www.ipa.go.jp/jinzai/itss/dx_Jinzai_sg.html

 


やってる事例が既存システムの再構築にしか聞こえないのと、対象がカスタマーサポートばかりなのはなぜなんだ?

そしてこれが、DXの課題とあんまり結びつかない。

 


https://www.dhbr.net/articles/-/6187

 


ホスト開発や昔の感覚だと

手作業を無くIT化しましょうって作業効率化してた側から

こんどはDX化することにより効率化される側に回ってるという皮肉

 


ホスト業務のDX化はサーバー化をすっ飛ばしてクラウド化しちゃうぜ

ってのが究極のDXになるのだろうか?

でも、システム刷新ってどちらかと言えば守りの部類だよな。

そうではなく、より新たなビジネスモデルを作るためか、新しいビジネスモデルを実現させるための新しい技術の導入がDXなのかな?

 


今まで運用保守に回してた予算プラスDX用の予算が組まれると予測出来る。

 


人材面で見ると

アジャイル、AI、セキュリティとあるけど

興味があるのはAIだけどAIって

言語にするとPython、Rとかになるのか?

それともいわゆる数学的な知識になるのか?

 


そして、人材の確保って言ってるけど

人材の育成というか、仕事をシフトさせるって

方向性はないんだな。

会社や社会から見たらそっちの方が手間だし

それは個人で頑張れよってことか。

厳しいよね

 


結局のところ、時代の流れに乗って新しいことしますか?

これをしてれば安泰なんてあるわけはなく、

現状維持だと取り残される。

 


昔はIT化で今はDX

 


そこで自分はどこにポジションを置くキャリアプランを描くかってことか

どうせなら変化を楽しめるポジションがいいよな