syuntoku14の進捗

進捗を書きなぐります

AOJ

AOJでPythonに慣れる(20問目)

AOJ

問題 The Shortest Path on A Rhombic Path 所感 ・簡単な動的計画法 ・pythonの文法に躓くこと多し 躓きポイント:スライスは[2:20000]みたいに範囲外でも受け付けてくれるけど、[-1:20000]みたいに負の数は末尾からのカウントになる コード INF=1e8 path=[…

AOJでPythonに慣れる(19問目)

AOJ

問題 Surrounding Area 所感 ・簡単なDFS ・pythonだと再帰深さの限界が速いので一部のテストケースに対してREになっちゃう ・まぢむり コード def fill(MAP,xy,stick,c): global w,h if stick=='B': sflag=0 else: sflag=1 x,y=(xy[0],xy[1]) if MAP[y][x][…

AOJでPythonに慣れる(18問目)

AOJ

問題 Princess's Gamble 所感 ・夜も遅いので灰色でお茶を濁す ・灰色解くだけだとあれなのでテストケースと出力を照らし合わせるプログラムを適当に書いた ・適当に書いたけど結構便利なのでやっぱデバッグが楽になるのは良い コード import math while Tru…

AOJでPythonに慣れる(17問目)

AOJ

問題 Chain Disappearance Puzzle 所感 ・いろんなところでえらーがでてたいへんでした ・もっとはやくとけるようになりたいです コード def calc(puzzle,H,score): flag=False for i in range(H-1,-1,-1): stones=[] for j in range(5): now=[j,puzzle[j][i…

AOJでPythonに慣れる(16問目)

AOJ

問題 Grey Area 所感 ・VScodeを導入したので練習がてら ・簡単 ・なんでREになるのかわけがわからないよ コード from heapq import * def calcInk(wdt,val): maxval=val[-1] histnum=maxval//wdt hist=[] for i in range(histnum+1): hist.append([]) vl=le…

AOJでPythonに慣れる(15問目)

AOJ

問題 Highway Express Bus所感 ・良い問題やこれは… ・DPをうまく使うと解ける(私は解けない) ・いつもみたいにsample inputに対してはいい感じの答え出すけどWA(test case全部表示してほちい…)コード from heapq import * import copy def dijkstra(s,c…

AOJでPythonに慣れる(14問目)

AOJ

問題 Shortest Path - Single Source Shortest Path 所感 ・初めてのダイクストラ法 ・ぶっちゃけよくわかってないマン コード from heapq import * #edge {to cost} #P {mindirection, modeNum} #G a list which contain informations of nodes # building …

AOJでPythonに慣れる(13問目)

AOJ

問題 Summer of Pyonkichi 所感 ・幅探2回目 ・sample input と同じ答え返すけどなぜかruntime errorでるからだれか助けて(ギブアップ) コード from collections import deque import copy def makeList(splist,n): for i in range(n): springs=[] springs…

AOJでPythonに慣れる(12問目)

AOJ

問題 A Thief所感 ・リハビリがてらにナップサック問題 ・簡単かと思ったけどなぜかTest Case 2でWAに ・何が間違ってるのか全然わからんのでギブアップコード count=1 while True: vw=[[0,0]] W=int(input()) if W==0: break n=int(input()) for i in range…

AOJでPythonに慣れる(11問目)

AOJ

問題 Seven Puzzle所感 ・眠い ・pythonのミュータブルオブジェクトで悩み時間を無駄にし虚無 ・多分普通の幅優先探索だと思う ・もっといい解法があると思うの(このコードだとTLEになっちゃう)コード (これだとACできない...) import copy import queue…

AOJでPythonに慣れる(10問目)

AOJ

問題 The Number of Island所感 ・初めてDFSを理解した ・How Many Islands?とほとんど同じ問題 ・終了条件が特殊 ・上下左右の分岐の奇麗な書き方を知ったコード while True: c=0 islands=[] islandsID=[] ID=0 def dfs(row,col): global ID if 0<=row<12 a…

AOJでPythonに慣れる(8,9問目)

AOJ

問題 Partition 所感 ・クイックソートにつながるやつ ・joinを知った ・pythonでのswapを知った コード def partition(A,p,r): x=A[r] i=p-1 for j in range(p,r): if A[j]<=x: i+=1 A[i],A[j]=A[j],A[i] A[i+1],A[r]=A[r],A[i+1] return i+1 n=int(input()…

AOJでPythonに慣れる(7問目)

AOJ

問題 Merge Sort 所感 ・普通のマージソート ・pythonにおける参照渡しで微妙に混乱したコード def mergeArray(a,b,bLength,c,cLength): global count apos,bpos,cpos=(0,0,0) while bpos

AOJでPythonに慣れる(6問目)

AOJ

問題 Fastest Route 所感 ・pythonじゃ無理? ・正直わかんなかったのでリンク先をパクり参考にしましたコード 答えは出るけどRE(c++でやろう) while True: N=int(input()) if N==0: break stage=[] for i in range(N): stage.append(list(map(int,input().s…

AOJでPythonに慣れる(5問目)

AOJ

問題 Space Coconut Crab 所感 ・眠い ・mathを初めて使った気がする解法 ・x+y2+z3=e より、yとzが決まるとxが決まる。よってyとzについてforループを回せば行けるはず(c++はこれで良い) ・c++のときと同じようにやったらRuntime Errorをくらったので少…

AOJでPythonに慣れる(4問目)

AOJ

問題 Coin Changing Problem所感 ・動的計画法入門 ・ポロック予想も同じ解法でできる(先にコイン問題やっとけばよかった)コード def main(): n,m=map(int,input().split()) c=list(map(int,input().split())) dp=list(range(n+1)) k=0 while k

AOJでPythonに慣れる(3問目)

問題 Pollock's Conjecture所感 ・はじめての動的計画法 ・任意の整数を扱う問題が出たら基本的にDP使うんか? ・わしには難しかったょ(そもそもRuntimeError) ・DP使っても1分45秒かかってるのでゴミ解法 ・正四面体数を使って106のリストを更新していく …

AOJでPythonに慣れる(2問目)

問題 Heaps - Maximum Heap所感 ・Outputの形式をちゃんと読んでなくてはまった解法 ・6.006のLecture4を見たら理解が進む ・問題文の通りに実装するだけコード def maxHeapify(A,i,H): l=2*i r=2*i+1 if l<=H and A[l-1]>A[i-1]: largest=l else: largest=i…

AOJでPythonに慣れる(1問目)

問題 The Balance of the World所感・pythonの文字列操作に慣れた ・replaceのおかげで楽に書けた気がする ・pythonよく分からん解法 ・文字列から括弧だけ抜き出して新しい括弧のみの文字列を作る ・左括弧と右括弧の個数が等しいか調べる ・一番内側の括弧…

AOJでPythonに慣れる

・春休みを利用してAOJをやっていくお話 ・難易度100でも何でもいいから一日2問くらい解いていきたい(願望) ・そもそもアルゴリズムの基本ができてないので難しい問題が解けないマン ・ブログを書いたことが無いのでブログにも慣れていくお話