2022-08-18

ABC171 D - Replacing

atcoder.jp 制約がQ <= 10⁵なので，各クエリをO(1)で処理する必要がある．
i回目の操作でO(1)で総和を求められるように，

あらかじめ，Aの総和ansを求めておく
A中の各数字の個数を保持しておく（下のコードではリストlに保持している）

BをCに置き換えるという各クエリは， B_count = l[B] l[B] = 0 I[C] = B_count で処理できる．

また，各クエリに対する答えは ans += (C-B)*B_count でも求められる．

N = int(input())
A = list(map(int,input().split()))
Q = int(input())

l = [0] * (10**5+1)
for i in range(N):
    l[A[i]] += 1

ans = sum(A)
for i in range(Q):
    B, C = list(map(int, input().split()))
    dif = C - B
    
    B_count = l[B]
    l[B] = 0
    l[C] += B_count
    
    ans += B_count * dif
    print(ans)

2022-08-18

picoGym Cookies

初めに

１日１問を目標にWeb問を解いていきたいと思っている．常設CTFのWriteupは良くないって『ホワイトハッカーの教科書』に書いてあった気がするけど，もともと競技CTFの問題だし良いでしょう～．

Cookies

BurpSuiteを使って解いてみた．
タイトルがCookiesなのでレスポンスヘッダーのCookieに着目すると，name=-1と設定されている．
Webページの検索窓のdefalt値のsnickerdoodleを入れてみると，検索結果のメッセージが「I love snickerdoodle cookies!」と変化する．また，Cookieを確認してみるとname=0となっている．

BurpSuiteで解く

BurpSuiteのintruder機能を使ってnameの値を1から100まで変化させてみる．

positionsの設定

proxy機能を使って，レスポンスヘッダーを眺めていた際に，/checkにリダイレクトされていることがわかっていたので，intruder->positionsタブでtargetをhttp://mercury.picoctf.net:54219/checkに設定する．また，name=-1にカーソルを合わせて，add §ボタンを押す．

payloadsの設定

intruder->payloadsタブでpayload Setsのpayload typeをNumbersに変更する．payload options[Numbers]のtypeをsequential，fromを1，toを100，stepを1とする．

Optionsの設定

intruder->optionsタブのGrep - Matchに「flag」という単語を追加する．

実行結果

上記設定をしたうえで，start attackボタンを押す．
name=18において，レスポンスにflagという文字列が出現したことがわかる． picoCTF{3v3ry1_l0v3s_c00k135_96cdadfd}

最後に

他の人のWriteupを見ていると，pythonやらでスクリプトを書いて解いてた．

2022-07-16

2022/07/16 ABC233 C - Product

ABC233 C - Product

atcoder.jp

組み合わせは深さ優先探索だって言ってんだろ．
あと関数内でグローバル変数にアクセスするときは，globalをつける必要があることを学んだ．（母語()がC言語なので，しばらくわけわからなくて悩んだ．）

ans = 0

def dfs(pos, product):
    global ans
    if pos == N:
        if product == X:
            ans += 1
        return 
    for i in range(1,La[pos][0]+1):
        dfs(pos+1, product*La[pos][i])
        
N, X = list(map(int, input().split()))
La = [list(map(int, input().split())) for i in range(N)]

dfs(0, 1)
print(ans)

2022-07-15

2022/07/15 データリンク層のフレーム化について簡単にまとめた

大学院入試で，このレベルの問題が出てくるらしい．
自分なら絶対解けない．

フレーム化の方式

データリンク層のフレーム化には3つの方式がある．

バイト数
フラグバイトとバイト詰め(byte stuffing)
ビット詰め(bit stuffing)

バイト数

バイト数方式は，ヘッダー中のフィールドにフレーム中のバイト数を示す方法

宛先のデータリンク層がバイト数を見れば，後ろに何バイトあるか，すなわちフレームの終わりがどこにあるかがわかる．

欠点として，伝送誤りによりバイト数が誤って伝えらえる可能性があるということがあり，バイト数方式は単独ではほとんど用いられていない．

フラグバイトとバイト詰め

フラグバイト方式とは，フラグバイトと呼ばれる特殊な文字でフレームの両端を挟む方式

伝送誤りによって協会情報が失われても，その境界付近のフレームだけに影響するのみである．

ただし，バイナリデータが送られてきた場合，そのバイナリデータの中にフラグバイトが出現することがある．その場合，バイト詰めと呼ばれる手法が利用される．

バイト詰め

バイナリデータの中に現れるフラグバイトの前に，ESC（エスケープバイト）記号というフラグバイトとは異なる記号を挿入する方法．データ中にESC記号が現れた場合，さらにESC記号を挿入する．

ビット詰め

フラグバイト方式は1Byte=8bitであることを前提とした方式だった．

ビット詰め方式は，01111110 すなわち16 進の0x7Eでフレームの両端を挟む方式．1が5個以上連続しているデータは5個おきに0を挿入する．

最後に

間違ったこと書いてたらごめんなさい．

参考文献

edu.net.c.dendai.ac.jp - アンドリュー・S・タネンバウム，「コンピュータ・ネットワーク第五版」

2022-06-30

2022/06/29 ABC238 C（解けなかった）

ABC238 C - digitnum

atcoder.jp

他に用事があって，ACできなかった．後で時間があるときにもう一度解きなおす．以下のコードはWA出してるコード

def S (start, end, n):
    return int((start+end)*n/2)

N = input()
N_int = int(N)
N_len = len(N)

ans = 0
base = 1
next_base = 10
start = 1
for i in range(N_len-1):
    end = next_base-base
    ans += S(start,end,end)

    base = next_base
    next_base = base * 10
end = N_int-base+1
ans += S(start,end,end-start+1)
    
print(ans%998244353)

2022-06-29

2022/06/29 ABC240C

ABC240 C - Jumping Takahashi

atcoder.jp

DPの考え方が定着しない．最初DPもどきなコードを書いてしまった．

N, X = list(map(int,input().split()))
dp = [set() for i in range(N+1)]

dp[0].add(0)
for i in range(N):
    a, b = list(map(int, input().split()))
    l = list(dp[i])
    for j in range(len(l)):
        dp[i+1].add(l[j]+a)
        dp[i+1].add(l[j]+b)
if X in dp[N]:
    print("Yes")
else:
    print("No")

想定解とはちょっと違う解き方をしてしまったので，解説を読みながら解きなおした．配列の要素に何を入れればいいのかがイメージできないから，DPをいつまで経っても書けないんだろうな．

N, X = list(map(int,input().split()))
# dp[i][j]:i回ジャンプを行った時点で座標jの位置にいることが可能なら1,不可能なら0
dp = [[0]*(X+1) for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
    a, b = list(map(int,input().split()))
    for j in range(X):
        if dp[i][j] == 1:
            if j+a <= X:
                dp[i+1][j+a] = 1
            if j+b <= X:
                dp[i+1][j+b] = 1

if dp[N][X] == 1:
    print("Yes")
else:
    print("No")

2022-06-26

2022/06/26 ABC253C

ABC253 C - Max - Min Query

atcoder.jp

2*10⁵個のクエリにおいて，最大値・最小値をheapqで高速に求める．

import heapq
from collections import defaultdict

Q = int(input())

Max_S = []
Min_S = []

S = defaultdict(int)

for i in range(Q):
    query = list(map(int, input().split()))
    op = query[0]
    if op == 1:
        op, x = query
        S[x] += 1
        heapq.heappush(Max_S, -x)
        heapq.heappush(Min_S, x)

    elif op == 2:
        op, x, c = query
        if S[x] > c:
            S[x] -= c
        else:
            S[x] = 0
    else:
        while S[-Max_S[0]] == 0:
            heapq.heappop(Max_S)
        while S[Min_S[0]] == 0:
            heapq.heappop(Min_S)
        print(-Max_S[0] - Min_S[0])

メモ

Maxheap，Minheapを別々で求めても，制限時間内に求まる
C++だと，Multisetなるもので，瞬殺できるらしい．
- ~~ずるくない?~~
dequeとheapqがごちゃごちゃになっていた
- あとで自分用のまとめ記事作る