ARC 005 C 器物損壊！高橋君
続き。
むずくてワロタ。
問題概要
壁'#', 平地'.', スタート's', ゴール'g' で構成されたH*Wのマス内で、スタートからゴールまで、壁を2回まで壊していいから、平地を通って行けるか。
考えたこと(間違い)
- s から g までに到達する経路の中で、壁を壊した回数をマスに記録する
- g に到達するまでに、壊した壁の数の最小 2 以下 なら OK のはず
- '#' でも '.' でも行かなきゃいけないはず
こんな感じで考えてたんだけど、「あれ、実装できない...、同じところ通ってまう...、minで更新できない...」となって袋小路。諦め。
教えてgoogle先生。
解答
カッケー！！！ 3 次元配列でBFSするのが正解だったのか...
個人的にすごく貪欲っぽい解法だったことに驚きを隠せなかった。
あと今回はpythonでも通りました！！！！(嬉しい)
from collections import deque def main(): h, w = [int(i) for i in input().split()] f = [] for i in range(h): f.append(list(input())) sy, sx = 0, 0 for i in range(h): for j in range(w): if f[i][j] == 's': sy, sx = i, j elif f[i][j] == 'g': gy, gx = i, j d = [[[False for k in range(3)] for j in range(w)] for i in range(h)] q = deque() # tuple[y][x][t] := f[y][x]までに何回壁を壊したか q.appendleft((sy, sx, 0)) d[sy][sx][0] = True y, x = 0, 0 # g に到達するまでに、壊した壁の数の最小 < 2 なら OK のはず # '#' でも '.' でも行かなきゃいけないはず while q: y, x, t = q.pop() if f[y][x] == 'g': break for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # f[y+dy][x+dx] を k 回訪れた時で、場合分けする # f[y+dy][x+dx] に、t 回壁を壊した状態で訪れる場合を考える if 0 <= y+dy < h and 0 <= x+dx < w and not d[y+dy][x+dx][t]: if f[y+dy][x+dx] == '#': # 2 で来てるからダメ if t == 2: #ダメ continue else: d[y+dy][x+dx][t+1] = True q.appendleft((y+dy, x+dx, t+1)) else: d[y+dy][x+dx][t] = d[y][x][t] q.appendleft((y+dy, x+dx, t)) print('YES' if any([d[gy][gx][i] for i in range(3)]) else 'NO') if __name__ == '__main__': main()
結構感動してる。復習して、いつでも書けるようにしたいなぁ。めっちゃ楽しいし、いいな。
AGC 033 A - Darker and Darker
今日はやらない予定だったんですけど、昨日のが不完全燃焼だったの思い出して悶々としてしまったので。
続きです。
リンクです。
問題概要
H*Wのマスに白マス'.'と黒マス'#'がある。1ターンで、黒マスを中心とする十字に塗り潰すことができる。何ターンで全てのマスが黒マスになるか。
考えたこと(間違い)
最初に、黒マスを取得し、1 ターンごと塗りつぶすマスをキューにぶち込んで黒くする。キューが空になるまで繰り返す。
TLEで死んだ。
""" TLE """ from collections import deque def main(): h, w = [int(i) for i in input().split()] f = [] black = deque() for i in range(h): line = list(input()) for j, c in enumerate(line): if c == '#': black.appendleft((i, j)) f.append(line) ans = 0 d = [[False for i in range(w)] for j in range(h)] black.appendleft((-1, -1)) sw = False while black: y, x = black.pop() if (y, x) == (-1, -1) and sw: break else: sw = False if (y, x) == (-1, -1): sw = True ans += 1 black.appendleft((-1, -1)) for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]: if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] == '.' and \ d[y+dy][x+dx] == False: f[y+dy][x+dx] = '#' d[y+dy][x+dx] = True black.appendleft((y+dy, x+dx)) print(ans-1) if __name__ == '__main__': main()
別マップを用意して、訪れたか確認してたんだけど、どうしてもダメだった。ターンごとのマスを識別するために(-1, -1)の組みを入れたんだけど、全然だった。
けんちょんさんのC++コードを書き直してもTLE。 こんな感じ
from collections import deque def main(): h, w = [int(i) for i in input().split()] f = [] for i in range(h): f.append(list(input())) #カウンター用のフィールド d = [[-1 for j in range(w)] for i in range(h)] q = deque() for i in range(h): for j in range(w): if f[i][j] == '#': # スタート地点のメモ d[i][j] = 0 q.appendleft((i, j)) while q: y, x = q.pop() for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]: ny, nx = y+dy, x+dx # 行ったことない場合に限る if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == -1: d[ny][nx] = d[y][x] + 1 q.appendleft((ny, nx)) ans = 0 for i in range(h): for j in range(w): ans = max(ans, d[i][j]) print(ans) if __name__ == '__main__': main()
けんちょんさんのは、別マップにターン数を書いて保存したやつで、自分とは考えが違かったんだな、なるほどなと思った。ちなみに、TLEだったけど、けんちょんさんのは、TLEが 1 つ減ったりして、勉強になった。 TLEが取れなくて、こんな日もあるんでしょうという気持ちになった日でした。
あ、今日は vue と OS の記事書きません。
OSメモ(2)
今日はリンカスクリプトを読んだ。
KERNEL_VMAは仮想アドレスのベースとなるアドレスだと思う。
ADDRは、
Return the absolute address (the VMA) of the named section.
と書いてあったので、VMAを含んだ(含んだという言い方はおかしいか).textセクションのアドレスということがわかる。
ATキーワードについてだが、64bitモードの場合、仮想アドレスと、ロードアドレスというのがあるらしく、普通は、セクションで同じ値が与えられるらしい。ATキーワードはVMAとLMAを別々のものにするために使うキーワードらしい。 つまり、
AT(ADDR(.text) - KERNEL_VMA)
は、セクションのロードアドレスを、KERNEL_VMAだけ引いた値にするということらしい。
64bitモードのメモリがよくわかってないのは、まずいな。
64bitモードのメモリのわかりやすい説明や資料(Intelのやつ見ればわかるんだろうけど)お待ちしています。（他力本願）
冗談は置いといて、メモリ周りは、今後調べないといけない課題だ。
時間がない〜〜〜(朝3:46なう)。
優しく教えてくれるコメントお待ちしています泣。
vueでチャットアプリ作った
ABC 088 D Grid Repainting
続き。
ねむみ。
from collections import deque def main(): h, w = [int(i) for i in input().split()] f = [] c_of_sharp = 0 for i in range(h): line = list(input()) for c in line: if c == '#': c_of_sharp += 1 f.append(line) sy, sx = (0, 0) q = deque([[sy, sx]]) BIG = 100000 f2 = [[BIG for i in range(w)] for j in range(h)] f2[0][0] = 0 s = True while q: y, x = q.pop() if (y, x) == (h-1, w-1): break for dy, dx in [[-1, 0], [1, 0], [0, -1], [0, 1]]: if 0 <= y+dy < h and 0 <= x+dx < w and f2[y+dy][x+dx] == BIG and \ f[y+dy][x+dx] != '#': f2[y+dy][x+dx] = f2[y][x]+1 q.appendleft([y+dy, x+dx]) else: s = False print(-1) if s: print(h*w-f2[h-1][w-1]-c_of_sharp-1) if __name__ == '__main__': main()
OSメモ(1)
64bitOSが作りたいなぁと思っています。(30日OS自作本やったので) 手始めに、上記のサイトをやっていく。できれば毎日やりたい。 "まともに動く"を目標にやっていきたいかも。
x86_64-elf-gcc -ffreestanding -mcmodel=large -mno-red-zone -mno-mmx -mno-sse -mno-sse2 -c foo.c -o foo.o
フリースタンディング環境は、OSなしでプログラムを実行しなければいけない環境を指すCおよびC++の用語である
なるほど。
コードもデータも制限されません。コードもデータもアクセスは絶対アドレス指定を使用しなければなりません。
デフォだと、コードの大きさが 2GiB に制限されてしまうみたい。コードもデータもアクセスは絶対アクセスは絶対アドレス指定をしなければならなければならないらしい。smallだと命令ポインタ(IP)からの相対アドレスで指定しなければならないらしい。もうわからないが笑 とりあえず、放置しとく。
Do not use a so called red zone for x86-64 code
https://www.cleancss.com/explain-command/gcc/5723
red zoneってのがあるらしい。そこを使わせないようにするのが -mno-red-zone。-m はマシン依存オプションを表しているみたいだ。
sse, mmx あたりが書いてある。SIMD命令周りのレジスタ、命令を無効化するオプションらしい
-mcmodel=largeは非効率なので、非推奨だけど、とっかかりとしてはいいみたい。osdevに書いてある。
vueでTodo作った
長いから3行で
こちらになります。
参考にしたのはここ
