2019-09-04

ABC 045 C - たくさんの数式

qiitaの蟻本互換記事の問題。

s = ""

def rec(i, word):
    if i == len(s):
        return eval("".join(word))
    ans = 0
    word.append('+')
    word.append(s[i])
    ans += rec(i+1, word)
    word.pop()
    word.pop()
    word.append(s[i])
    ans += rec(i+1, word)
    word.pop()
    return ans

def main():
    global s
    s = input()
    print(rec(1, [s[0]]))

if __name__ == '__main__':
    main()

eval使ったやつ。eval使わなかったらめんどくさそうだなと思った。

2019-08-16

AGC 013 A - Sorted Arrays

競プロ熱が高まってきたので、qiitaの記事のやつ進めることにした。数列の切り出しができなかったのよね

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 0
    i = 0
    while i < n:
        # 右隣が同じにならないようにする
        while i+1 < n and a[i] == a[i+1]:
            i+=1
        # i は n-1 で抜けてくるので、下には引っかからない
        # 右隣の数の方が大きかったら
        if i+1 < n and a[i] < a[i+1]:
            # 右隣の方が小さくなるまで、次に進める
            while i+1 < n and a[i] <= a[i+1]:
                i += 1
        # 右隣の数の方が小さかったら
        elif i+1 < n and a[i] > a[i+1]:
            # 右隣の数が大きくなるまで、次に進める
            while i+1 < n and a[i] >= a[i+1]:
                i += 1
        # a[i]まで切り取る
        ans += 1
        # i をインクリメントして、新しい配列の先頭とする
        i += 1
    print(ans)

if __name__ == '__main__':
    main()

2019-07-22

gnu as tips

OSのbootプロセスを見る日々です。オペコードオペランドはパスで。

1.マクロ1

/* マクロの定義 */
.macro macro_name
...
.macro

macro_name # マクロの展開

2.マクロ2

#define three(sym) sym ## sym ## sym

gccで使うようなマクロの定義。

#include "xxx.h"

を使うなら、gccでアセンブルする。##で結合できる。関数みたいに定義できたりする。gccを使うときは拡張子は.Sにしないとダメっぽい。

3.ラベルジャンプ

jmp 1f

1:
    push %eax

jmp 1b

ラベル名+f, ラベル名+b で前後どっちのラベルかを指定できる。forwardとbackwardっぽい。

サンプル

/* sample.h */
#define A 1

#if defined (A)
#define LOCAL(sym) _ ## sym

#define FUNCTION(x) .global LOCAL(x) ; LOCAL(x):
#endif

.code32
#include "sample.h"

FUNCTION(abc)
    push %eax

1:
    .macro sample
    push %eax
    push %ebx
    .endm

    sample

    jmp 1b

    jmp 1f

1:
    nop

逆アセンブル

sample.o:     file format elf32-i386


Disassembly of section .text:

00000000 <_abc>:
   0:   50                      push   %eax
   1:   50                      push   %eax
   2:   53                      push   %ebx
   3:   eb fc                   jmp    1 <_abc+0x1>
   5:   eb 00                   jmp    7 <_abc+0x7>
   7:   90                      nop

2019-06-15

IPLでセクタ読み込みエラー

自作デバイス

OS自作入門をgasで書きなおしてみたいなぁって思って進めてたんだけど、セクター読み込みでエラーが出てた。

なんで読み込めないのかなぁって思って、調べてたら、ディスク番号が違かったらしい。

起動時に、%dlに起動したドライブ番号が入ってるらしいので、それを退避させておけばいいっぽい。qemuでドライブ番号って変えられるんかな。

2019-05-28

ABC128 C Switches

競技プログラミング

出れなかったんだけど、AtCoderの解説動画が結構参考になったので、pythonで書く

数え上げ系すごく苦手なので、戒め兼補足。解説動画が少しわかりにくかったので。

問題概略。 ON/OFFスイッチが N 個と電球が M 個ある。それぞれのスイッチは複数の電球とランダムに接続されている。電球は、繋がっているスイッチのうちONになっているものの数が、偶奇どちらかの時(ランダム)、点灯する。それを決めるのは、P_i (1 ≦ i ≦ M)。全ての電球をつけるスイッチのパターンの数を求めよ。

解説では、bit全探索だった。N ≦ 10 なので、2 ^10 ≒ 10 ^3 なので十分。

まず、入力を表に接続表(隣接行列みたいなやつ)にする.

スイッチ番号\電球番号	0	1	2
0	1	1	0
1	1	0	1

こんな感じにしたい。bit全探索にすると、実装が楽になるので、2 進数にする。この時上の表と桁が反転することになる。

スイッチ番号\電球番号	2 1 0
0	011
1	101

ここで、スイッチ 0 を押すと、それぞれの電球の押されているスイッチの数は

電球番号	2	1	0
押されているスイッチの数	0	1	1

になる。さらに、スイッチ 1 を押すと

電球番号	2	1	0
押されているスイッチの数	1	1	2

こうなる。電球とスイッチが繋がっていない場合は、数は上がらず、スイッチを押すと、押したスイッチの接続表の行を足していく動作になる。

ここで、単純に押されているスイッチの数をそれぞれ 2 で割れば、あまりが出て、点灯しているかいないかがわかるが、単純に行を足すのではなく、排他的論理和をとれば、直接それぞれのあまりが出せて、実装が楽になる。

全探索の部分は、シフトを活かして、列挙する。1 が立っている桁と、スイッチのONが対応している具合に。

通った解答

def main():
    n, m = [int(i) for i in input().split()]
    # a[i] には i 番目のスイッチの 電球との接続情報が入っている
    a = [0 for i in range(n)]
    for j in range(m):
        k, *switch = [int(i) for i in input().split()]
        for s in switch:
            a[s-1] |= (1 << j)
    p = int(("".join(reversed([i for i in input().split()]))), base=2)

    ans = 0

    # bit全探索
    for i in range(1<<n):
        t = 0
        for j in range(n):
            if (i >> j & 1) == 1:
                t ^= a[j]
        if t == p:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

2019-05-23

gnu as のラベル参照に$付けるのと付けないのとの違い

雑記

gnu as(gas) には

label1:
    ...

という構文があって、label1はその部分のアドレスを表す。

例えば、

.code16

movw $label1, %ax

とすれば、axレジスタにlabel1のアドレスを入れることができる。

この時、

movw label1, %ax

と書いてもエラーにはならない。

この時の動作は label1 のアドレスから 2 バイト読み込みという動作になる

ちなみに

movw ($label1), %ax

とは書けないので、intel書きとは違うので注意する必要がある。

2019-05-14

ABC125 C GCD on BalckBoard

競技プログラミング

i 番目の要素だけを除いた全体のGCDを求めるという愚直な案を書いて当然TLEだったので供養。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    for i in range(n):
        tmp = -1
        for j in range(n):
            if j == i:
                continue
            if tmp == -1:
                tmp = a[j]
            tmp = gcd(tmp, a[j])
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

ユークリッドの互除法の計算量がO(log(min(A,B))なので、これだとO(n^2log(min(A,B))となってTLE。

解答を見ると、結合則を使って、左右のを求めて、最後に計算。といった具合だろうか。

def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

これでAC出た。結合則を用いて左右から計算していく発想は出なかったなぁ。

いろんなことで四苦Hack（仮）

b1u3の技術ブログ