10数年の生活により出た結論として、｢ヤツらは最低限の食べ物があると無限に生存できる｣ということが分かりました。例えば缶ジュースなどを置いておくと、舐めているらしいです。僕はゴキブリだけはマジのガチで無理で、中学生の頃は研究者とゴキブリを絶滅させる仕事で迷った結果、ゴキブリを見たくないので研究者を選んだという過去があるほどです。話を戻しますが、絶対防衛ラインとしての｢ヤツらの生存に有利な食べ物を置かない｣と、僕自身の｢何もしたくない｣を天秤にかけた結果が、｢家庭内の飲料のほぼ全てをペットボトルに頼り、飲み終わったらしっかり蓋を閉めて部屋に投げ捨てる｣でした。だいたい3ヶ月に1回くらい限界が来て全部洗う羽目になります。

親からも姉からもめちゃくちゃに終わりだと思われていて、実際僕も人の部屋に行ってこれだったらマジで引きますが、僕は友達が家に来ることがないのでなんも困っていなくてむしろ困っています(改善圧が欲しい)

## 俺は掃除が嫌いなのか

自己弁護するぜ

｢こいつ掃除が苦手なの？｣ということも思われそうですが、実はそんなことはなく、放課後に教室の掃除をしているくらいには掃除が好きです。｢自分にしか影響がない領域で、基準を決めたらそれをこえない限り何をしても良い｣という価値観がこの部屋の惨状を生み出しているんだと思います。皆さんも基準をこえない全ての許容を体験してください。

## まとめ

飽きたので締めます。

総括としては

+ 我が部屋にはペットボトルが50本くらい転がっている

+ 虫が湧く要因にならないものは全て許容できる

+ 家族が泣くので皆さんはペットボトルはきちんと捨ててください

です。それでは良いペットボトルライフを！

2021-09-07

nitic ctf 2　公式解説(nanigasi_san)

お疲れさまでした。nanigasi_san作問の問題のフラグと解説です。

僕は「初めてCTFに出る人」および「競プロから来た人」向けに作問しました。

ほかの人の作った問題の解説はここにあります

お布施

↓僕のBASEとかお菓子になります。↓

Kyash

解説

Excel(☆1)[Misc]

zipを展開するとBook1.xlsxがあります。問題文に「どこかのセルにフラグが書いてあります」とあるので、それを探します。

想定解

Ctrl+Fで「nitic_ctf」で検索すると出ます。

xmlに対してgrepでも解けますが面倒です f:id:nanigasi_san:20210906204523p:plain

nitic_ctf{plz_find_me}

image_conv(☆2)[Misc]

after_image.pngをみるとうっすらnitic_ctf{, }と書いてあるのが見えます。肝心のフラグの中身が薄すぎて見えないので、根性でコントラストを上げることで見えるようになります。温情でギリ肉眼でも見えるくらいになってるので、コントラストの上げ方がわからなかったら頑張ってください。

モニターの設定がFPS用とかになってるとマジではっきり見えちゃってたのでコンテスト中にちょっと見づらくしました。

想定解

from PIL import Image
from PIL import ImageEnhance
img1 = Image.open("image_conv/after_flag.png")
i2 = ImageEnhance.Contrast(img1)
img2 = i2.enhance(1000)
img2.show()

f:id:nanigasi_san:20210906204715p:plain

nitic_ctf{high_contrast}

ord_xor(☆3)[Crypto]

xor(c, n)はx=[0, n-1]の数をループしてord(c)にxorしていく関数です。

flagのi文字目はxor(flag[i], i)されていますが、xorの性質として二回同じ数でxorするともとに戻るので逆操作をすればよいです。

想定解

with open("./flag") as f:
    flag = f.read()


def xor(c: str, n: int) -> str:
    temp = ord(c)
    if (n + 1) % 2 == 0:
        temp ^= n
    return chr(temp)


dec_flag = ""
for i in range(len(flag)):
    dec_flag += xor(flag[i], i)
print(dec_flag)

nitic_ctf{ord_xor}

問題名をフラグにするな

tanitu_kanji(☆3)[Crypto]

変換先テーブルが二つ用意されており、あるFORMATに従ってフラグが変換されていきます。復号処理自体は変換を逆にするだけなので、FORMATが分かれば復号できます。

FORMATの長さは10だということがわかっているので、2¹⁰通りを全て全探索してフラグが出ます。この手法はbit全探索と呼ばれます。

想定解

alphabets = "abcdefghijklmnopqrstuvwxyz0123456789{}_"
after1 = "fl38ztrx6q027k9e5su}dwp{o_bynhm14aicjgv"
after2 = "rho5b3k17pi_eytm2f94ujxsdvgcwl{}a086znq"


def deconv(s: str, table: str) -> str:
    res = ""
    for c in s:
        i = table.index(c)
        res += alphabets[i]
    return res


for i in range(2**10):
    flag = "l0d0pipdave0dia244im6fsp8x"
    format = ""
    for j in range(10):
        format += str((i >> j) & 1)
        format = format[::-1]

    for f in format:
        if f == "1":
            flag = deconv(flag, after1)
        else:
            flag = deconv(flag, after2)
        if "nitic_ctf" in flag:
            print(flag)

nitic_ctf{bit_full_search}

解法をフラグにするな

web_meta(☆1)[Meta]

htmlをブラウザで開くとフラグが見当たりません。F12を押して開発者ツールを開くことでmetaタグ(表示に関係ない情報)が見れるようになり、そこにフラグが書かれています！

f:id:nanigasi_san:20210906205004p:plain

Atom結構いいですよ　フラグはnitic_ctf{You_can_see_dev_too1!}

caesar_cipher(☆1)[Crypto]

アルファベットを後ろに三文字ずらすシーザー暗号なので、前に三文字動かすことで復号できます。

これは紙でも解けますねフラグはnitic_ctf{caesar}

CTFの話

道路さんが「今年はやらないんすか？」っていうのでノリで第二回が開催されました。今回はSatoooon君が作問に入ってくれたので色んな層が楽しめるCTFになったんじゃないでしょうか。

普通にCTFしてる人が増えたおかげで教育的な普通の問題が生えました。

前回はカナブンとドラゴンみたいな感じだったけど今回はカナブンと犬とライオンとドラゴン#nitic_ctf_2
— nanigasi_san (@nanigasi_3) September 5, 2021

Twitterでもはなしていましたが前回は難易度分布が終わっていましたからね。

とはいえ反省もあって、RevとかPwnの低難度が少ないこと、告知が開催二日前だったことなどがありますが、まぁ全体的にはいい感じになったと思います。

第三回をやる予定はないんですがどうせやると思います。俺のTwitterをフォローするのはアレなので、偶然告知が流れてくることを祈っていてください。

では～。

2021-05-13

競プロリハビリ開始とバチャ反省

競技プログラミングを再開しますという話

AtCoderのコンテストに最後に出たのが2020/5/31なのですが、そろそろ一年経つので6月になると同時に(つまり、ぴったり一年経つと同時に)コンテストに復帰することにしました。5月中をかけてゆっくりリハビリしていきます。

バチャリンク

https://kenkoooo.com/atcoder/#/contest/show/a1ca2d09-73b4-4248-9f1b-879cd95bd2b3

解説

1. 仲良しうさぎ

概要

各ウサギが好きなのは一匹なので、あるウサギについて2ペア以上組んでいることはあり得ません。よってそのウサギが好きなウサギと両想いかを確認していけばよく、求まる数が「両想い属性を持つウサギの数」なので、最後に2で割るとペアの数になります。

実装

自分が好きなウサギの好きなウサギが自分であるかどうかを見ればよいです

N = int(input())
alist = list(map(int, input().split()))
ans = 0
for i in range(N):
    if alist[alist[i]-1] - 1 == i:
        ans += 1
print(ans//2)

atcoder.jp

2. Good Sequence

概要

元の数列のうち、いい数列の要素になりえる数の条件は「自分自身より個数が多い」数です。3が5個あれば2個減らすことで3-3になりますが、3が2個しかなければいい数列の要素として残せません。ある数KがV個ある時、K<=VならばV-K個削り、K>VならばV個全て削る、という操作をすべての要素に行うことで最小手数でいい数列が求まります。

実装

個数を数えるにはCounterが便利です

from collections import Counter
N = int(input())
alist = list(map(int, input().split()))
ac = Counter(alist)
ans = 0
for k, v in ac.items():
    if v < k:
        ans += v
    else:
        ans += (v-k)
print(ans)

atcoder.jp

3. ∵∴∵

概要

OとEを交互に足していきます。終わりです

実装

listに変換するとpopが使えてうれしいです

O = list(input())
E = list(input())
ans = ""
while O:
    ans += O.pop(0)
    if E:
        ans += E.pop(0)
print(ans)

atcoder.jp

4. 100 to 105

概要

商品は最低100円なので、どのように買っても X // 100個は買えます。そうすると端数がX % 100円発生するので、その端数を作り出せるかが問題となります。1桁目を見ると1~5円があるので、一番大きい5円を最大限使った場合が表せる最大の数になります。よって(X // 100)*5が(X%100)を上回っていれば、可能です。

実装

上の話を実装するだけです

from math import ceil
X = int(input())
can_buy_num = X // 100
mod = X % 100
if mod <= 5 * can_buy_num:
    print(1)
else:
    print(0)

atcoder.jp

5. Choose Integers

概要

何を足してもいいと言っていますがAの倍数縛りがあるので、結局和もAの倍数です。よって「A*N % B == CとなるNがあるか？」を探索すればよいです。

実装

よくわからなかったのでN=1000まで回しました

A, B, C = map(int, input().split())
for i in range(1, 1000):
    if (A*i) % B == C:
        print("YES")
        break
else:
    print("NO")

atcoder.jp

6. To 3

概要

3の倍数の性質として、「各桁の和が3の倍数になっている」というのがあります。よって、和が3の倍数になるかだけをみたいので、すべての数をmod 3で考えてよいです。

与えられた数列 mod 3をSとして、Sの総和のmod 3をとったものをXとします。Xが0なら最初の時点でOKです。Xが1の場合はSの1を一つ、あるいは2を二つ消すことでXが0になります。Xが2の場合も同様で、Sの2を一つか、1を二つ消すことで実現できます。逆に、これ以外の場合は実現できません。

実装

from collections import Counter
N = input()
def int_and_mod3(c):
    return int(c) % 3
Nlist = list(map(int_and_mod3, list(N)))
ln = len(N)
sn = sum(Nlist)
nc = Counter(Nlist)
if sn % 3 == 0:
    print(0)
elif sn % 3 == 1:
    if nc[1] >= 1 and ln > 1:
        print(1)
    elif nc[2] >= 2 and ln > 2:
        print(2)
    else:
        print(-1)
else:
    if nc[2] >= 1 and ln > 1:
        print(1)
    elif nc[1] >= 2 and ln > 2:
        print(2)
    else:
        print(-1)

atcoder.jp

7. Minimization

概要

全部同じ値になっているとき、それは最初の数列の最小値になっていることが明らかにわかる。なぜなら、最小値以外をすべて同じにして[2, 2, 2, 2, 2, 1, 2, 2, 2]という風にしても、結局すべて同じになるためには1を含んだ範囲を操作しなければならないからである。

長さKの範囲を操作するとき、最小値を含むことを考えると「新たにK-1の範囲を更新する」と言い換えられる。素直に考えると、最小値を左端に含んで右に動かしていく、右端に含んで左に動かしていく、の二つをすることで全てが1になることがわかる。ここで、端で少しあまることがあるのでそれを反対側に移譲することで最小手数で達成できる。

実装

from math import ceil
N, K = map(int, input().split())
Alist = list(map(int, input().split()))
min_num_index = Alist.index(min(Alist))
left = min_num_index
right = N - 1 - min_num_index
extra = (K-1) - (left % (K-1)) if (left % (K-1)) else 0
# print(left, right, extra)
right -= extra
print(ceil(left/(K-1)) + ceil(right/(K-1)))

atcoder.jp

8. Ice Tea Store

概要

まず、求められるNが整数なのでQとHはそれぞれ4倍、2倍して1Lの値段に換算して良い。そうすると1Lが三種類出てくるので、その中の最安値を1Lの値段として設定できる。

その最安値の2倍がDより安い場合、すべてそれで買えばよい。Dの方が安い場合、可能な限りDで買い、余った分をできるだけ安く買いたいが、問題より「ちょうどN[L]」という制約があるので、余った場合は先に述べた1Lの最安値で買うほかない。

実装

Q, H, S, D = map(int, input().split())
N = int(input())

Q *= 4
H *= 2
best_price_of_QHS = min(Q, H, S)
if 2*best_price_of_QHS <= D:
    print(best_price_of_QHS*N)
else:
    print((D * (N//2)) + (best_price_of_QHS * (N%2)))

atcoder.jp

9. ModSum

概要

左に一個ずつずらすと、1~(N-1)に2~Nが割り振られ、「(N-1)%N=N-1」より、そこまでの余りの総和は1~(N-1)の総和になる。最後だけが「N%1=0」になるため、結局1~(N-1)の和を求めればよい。

実装

N = int(input())
a = N - 1
print((a*(a+1))//2)

atcoder.jp

10. A+...+B Problem

概要

あり得ない場合の場合分けが面倒ですが、あり得る場合は「AとBは最低一回ずつ使う」という条件を用いて、A+BにA*(N-2), B(N-2)を足した範囲が答えの範囲になります。

実装

あり得ない場合の判定が面倒でした

N, A, B = map(int, input().split())
if A > B or (A != B and N == 1):
    print(0)
    exit()
if A == B:
    print(1)
    exit()
N_ = N-2
deka = A + B + B * (N-2)
tubi = A + B + A * (N-2)
print(deka-tubi+1)

atcoder.jp

感想

案外解けましたが、時間が足りず緑まで行きませんでした。まぁ週2, 3くらいのペースでバチャしてリハビリしていけたらと思います。

2020-05-31

2020/5/31バチャ反省(2)

久し振りにABCに出るのでウオーーーーーーーーーーーーーーーーーーーーーーミングアップにバチャをしました。

バチャ概要

リンクです。

難易度は

0~400(灰)*10
800~1200(緑)*2
1200~1400(水色)*1

55分+2ペナで全完。水色の考察をするために組みましたが、グラフだったので瞬殺でした。

解説

緑以上の3問だけ解説と提出を書きます。

Transit Tree Path

考察と方針

クエリでは $x _ jとy _ j$ が与えられ、 $x _ jからKを経由してy _ j$ まで移動する最短距離を求める必要があります。無向グラフなので、 $x _ jからKまでの最短経路$ と $Kからx _ jまでの最短経路$ は同じです。

また、木においてある二点をつなぐ経路は一つしか存在しないため、実は「 $x _ jからy _ jへの経路にKが含まれているか$ 」は気にしなくてよいことが分かります。

つまり、事前にKを始点にした全点への最短経路を求めておき、各クエリにおいて

$Kからx _ jまでの最短経路$
$Kからy _ jまでの最短経路$

を足したものを出力すればよいです。

実装

解説を読むと「経路は一通りなのでKを根にしてDFSすればよいです」とあります(これはつまり、上で言っている「最短経路」が「経路」と言い換えられるということでもあります)が、それに気づかなかったのでKを始点にダイクストラをしました。あとは各クエリにおいて上で書いた値を出力するだけです。

提出

atcoder.jp

計算量

ダイクストラ部分がネックになって、 $O(NlogN)$ です。想定解では $O(N+Q)$ なのでかなり違いますが、通ればいいんです。

STring

考察と方針

とりあえず変化しなくなるまで

X = X.replace("ST", "")

を繰り返せばいいのはわかります。提出します。 $O(N ^ 2)$ なので当然TLEです。

制約的に $O(N)$ が限界なので、大体一回のループで処理を完了しなければなりません。どうしよう....

問題文の通り、、STが1ペアとなって消滅します。これはスタックの説明でよく見る括弧列の対応と同じです。すなわち、要素をスタックに一つずつ追加していって、右端でSTのペアができていたら消す、できていなかったらなにもしない...という流れを繰り返すことで、問題文にあるSTのペアを消していくシミュレーションと同じ結果が得られます。

これはざっくりいうと、「スタックに変更があるたびに右端だけチェックすれば、右端以外はチェック済みなのでSTが含まれていることは無い」ということです。