Ecasdqina's MEMO.

メモ帳.

競プロ百物語 035-057+α 17/10/9-10/23

競プロ百物語について

ecasd-qina.hatenablog.com

解いた問題

035 ABC-C 風力観測

C: 風力観測 - AtCoder Beginner Contest 001 | AtCoder

控えめに言ってクソ問。

Submission #1676762 - AtCoder Beginner Contest 001 | AtCoder

036 ABC-C Multiple Clocks

C: Multiple Clocks - AtCoder Beginner Contest 070 | AtCoder

入力ごとに最小公倍数を求める。

Submission #1688258 - AtCoder Beginner Contest 070 | AtCoder

037 ABC-C Colorful Leaderboard

C: Colorful Leaderboard - AtCoder Beginner Contest 064 | AtCoder

"色を自由に変えることができる"に注意。

Submission #1688301 - AtCoder Beginner Contest 064 | AtCoder

038 ABC-C Chocolate Bar

C: Chocolate Bar - AtCoder Beginner Contest 062 | AtCoder

場合分けして全探索。

Submission #1688497 - AtCoder Beginner Contest 062 | AtCoder

039 ABC-C Big Array

C: Big Array - AtCoder Beginner Contest 061 | AtCoder

pairでいい感じに情報を持つ。

Submission #1688533 - AtCoder Beginner Contest 061 | AtCoder

040 ABC-C Go Home

C: Go Home - AtCoder Beginner Contest 056 | AtCoder

1+2+\dots+(n-1)+n=\frac{n(n+1)}{2}が初めてXを超えるnを探す。

Submission #1688556 - AtCoder Beginner Contest 056 | AtCoder

041 ABC-C Back and Forth

C: Back and Forth - AtCoder Beginner Contest 051 | AtCoder

あるブロックの上下左右にあるブロックの数は4つ。

Submission #1690924 - AtCoder Beginner Contest 051 | AtCoder

042 ABC-C 柱柱柱柱柱

C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder

DP。

Submission #1690954 - AtCoder Beginner Contest 040 | AtCoder

043 ABC-C 単調増加

C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder

順に見ていく。

Submission #1691471 - AtCoder Beginner Contest 038 | AtCoder

044 ABC-C 総和

C: 総和 - AtCoder Beginner Contest 037 | AtCoder

累積和。

Submission #1691482 - AtCoder Beginner Contest 037 | AtCoder

045 ABC-C 座圧

C: 座圧 - AtCoder Beginner Contest 036 | AtCoder

座標圧縮。

Submission #1691511 - AtCoder Beginner Contest 036 | AtCoder

046 ABC-C オセロ

C: オセロ - AtCoder Beginner Contest 035 | AtCoder

いもす法。

Submission #1691530 - AtCoder Beginner Contest 035 | AtCoder

047 ABC-C 列

C: 列 - AtCoder Beginner Contest 032 | AtCoder

左と右でカーソルをもってぐにゃぐにゃ進む。

Submission #1691552 - AtCoder Beginner Contest 032 | AtCoder

048 ABC-C 数列ゲーム

C: 数列ゲーム - AtCoder Beginner Contest 031 | AtCoder

全探索。

Submission #1691607 - AtCoder Beginner Contest 031 | AtCoder

049 ABC-C Brute-force Attack

C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder

DFS。

Submission #1691734 - AtCoder Beginner Contest 029 | AtCoder

050 ARC-A 宝くじ

A: 宝くじ - AtCoder Regular Contest 006 | AtCoder

やるだけ。

Submission #1691756 - AtCoder Regular Contest 006 | AtCoder

051 ARC-B 2点間距離の最大と最小

B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder

最大は総和、最小は距離が一難長い2点を2円の中心にしたときに交わるかどうかで場合分け。

Submission #1691782 - AtCoder Regular Contest 004 | AtCoder

052 ABC-C 数を3つ選ぶマン

C: 数を3つ選ぶマン - AtCoder Beginner Contest 028 | AtCoder

DFS。

Submission #1692015 - AtCoder Beginner Contest 028 | AtCoder

053 ABC-C 倍々ゲーム

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder

解説の図を見ましょう。

Submission #1692070 - AtCoder Beginner Contest 027 | AtCoder

054 ABC-C 高橋君の給料

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder

実装ゲー。

Submission #1692168 - AtCoder Beginner Contest 026 | AtCoder

055 ABC-C 飛行機乗り

C: 飛行機乗り - AtCoder Beginner Contest 030 | AtCoder

貪欲法。

Submission #1692170 - AtCoder Beginner Contest 030 | AtCoder

056 JOI予選 12-3 最高のピザ(Best Pizza)

C: 最高のピザ (Best Pizza) - 第11回日本情報オリンピック 予選(オンライン) | AtCoder

貪欲法+全探索。

Submission #1695967 - 第11回日本情報オリンピック 予選(オンライン) | AtCoder

057 CODE FESTIVAL 2017 qual C-C Inserting 'x'

C: Inserting 'x' - CODE FESTIVAL 2017 qual C | AtCoder

右と左でカーソルを分けてえいっ。

Submission #1703109 - CODE FESTIVAL 2017 qual C | AtCoder

057-2 CODE FESTIVAL 2017 qual C-B Similar Arrays

B: Similar Arrays - CODE FESTIVAL 2017 qual C | AtCoder

数学解の考察に大失敗して再帰を書いたらバグったので先にCを解いてたらDP解が降ってきた。

Submission #1703581 - CODE FESTIVAL 2017 qual C | AtCoder

17'高専セキュリティコンテストに参加した[write-up]

はじめに

チーム名 "BiPhpne" で

bi0o = 0b100 (@sei0o) | Twitter, Akashi_SN (@Akashi_SN) | Twitterさん, Snow (@Snow_Poijio) | Twitterさんと出ました。
ぼくはセキュリティコンテスト未経験だったのであまり難しい問題はできなかったけど、とても楽しかったです。
2位をとれてよかった。
以下にぼくが解いた問題のwrite upを書きます。

write up

サンプル

問題文にFlagが書かれてるのでそれを送るテスト問題。

フラグを答えろ

Problem Fileが置かれていたのでstringsをするとFlagが出てくるのでそれを整形すると答え。

ボスを倒せ

ncでアクセスするとボスとプレイヤーとの戦いが始まるがボスのHPが異常に高く全く倒せない。
プレイヤーの名前を入力する段階があったので適当にAAAAAAAAAAAAAAAAAAAAAAAAAAとか入力するとバッファオーバーフローしたので、メモリ上にプレイヤー名|プレイヤーHP|ボスHPと並んでるのかと考え境界をうまく探るとプレイヤーのHPを大きくし、ボスのHPを小さくできるようになり、ボスを倒せるようになる。

素数を数えろ

7桁で最大の素数が答えなので素数辞書でさがしてAC。

RSA2

同じ法で異なる2つの鍵を使い暗号化された2つの暗号文が渡されるので復号化する。
復号の手順を以下に示す。
定数: N:法, M:平文, e_1:鍵1, e_2:鍵2, c_1:暗号文1, c_2:暗号文2
まず次の2つの合同式が成り立つことが分かる。
c_1=M^{e_1}\ \left(mod\ N\right)
c_2=M^{e_2}\ \left(mod\ N\right)
また、これらより次の式も成り立つ。
c_1\times c_2=M^{e_1}\times M^{e_2}=M^{e_1+e_2}\ \left(mod\ N\right)
c_1^{a}\times c_2^{b}=M^{ae_1}\times M^{be_2}=M^{ae_1+be_2}\ \left(mod\ N\right)
ここでae_1+be_2=1となるようなa,bがあると嬉しい。
このような方程式を1次不定方程式といい、e_1e_2が互いに素なとき、解が必ず存在する(証明は読者に任せる)。
今回はe_1e_2は差が2の奇数なのでe_1e_2は互いに素(証明は演習問題とする)。
またaかbが負になることは明らか、今回はbが負と仮定する。
e_2が小さかったのでO(e_2)アルゴリズムで解を探した。

for i in range(e2):
    if (e1*i)%e2==1:
        a=i
        b=-(e1*i)//e2
        break

aとbがわかったのであとは計算すればよい、bが負なのでc_2の(mod\ Nでの)逆元を計算する(iとおく)。
M=c_1^{a}\times i^{|b|}\ \left(mod\ N\right)
平文MがわかったのでASCIIに変換するとFlagが出る。

途中まで与えられた数値がおかしかったようで、8時間くらい溶かした......

Homomorphic Encryption

準同型暗号、暗号化したまま計算できる。
準同型とは群/環準同型写像で次の性質がある。
\phi(a\times b)=\phi(a)\times \phi(b)
問題文に論文(英語)が添付されていた。
結局論文を読むだけで終わりました。

おわりに

CTFの楽しさを知ってしまった、ずぶずぶ(沼へ沈む音)......

競プロ百物語 026-034 17/9/26-10/8

競プロ百物語について

ecasd-qina.hatenablog.com

解いた問題

026 Tenka1 Programmer Beginner Contest-C 4/N

C: 4/N - Tenka1 Programmer Beginner Contest | AtCoder

姑息な全探索をした。

Submission #1638235 - Tenka1 Programmer Beginner Contest | AtCoder

027 ABC-C Digits in Multiplication

C: Digits in Multiplication - AtCoder Beginner Contest 057 | AtCoder

やるだけ。

Submission #1648781 - AtCoder Beginner Contest 057 | AtCoder

028 JOI本戦 07-3 最古の遺跡

C: 最古の遺跡 - 第6回日本情報オリンピック 本選(オンライン) | AtCoder

2つ選んでアの全探索。

Submission #1652465 - 第6回日本情報オリンピック 本選(オンライン) | AtCoder

029 DDCC-C 収納

C: 収納 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder

sortして 前と後ろで 貪欲法

Submission #1658276 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder

030 JOI予選 08-3 連鎖

C: 連鎖 - 第8回日本情報オリンピック 予選(オンライン) | AtCoder

実装ゲー、iとjを間違えてn時間溶かした。

Submission #1662063 - 第8回日本情報オリンピック 予選(オンライン) | AtCoder

031 JOI予選 10-4 1年生(A First Grader)

D: 1年生 (A First Grader) - 第10回日本情報オリンピック 予選(オンライン) | AtCoder

DPやるだけ。

Submission #1662399 - 第10回日本情報オリンピック 予選(オンライン) | AtCoder

032 JOI本戦 07-2 共通部分文字列

B: 共通部分文字列 - 第7回日本情報オリンピック 本選(オンライン) | AtCoder

DPやるだけってことに気づかなくてア。

Submission #1661417 - 第7回日本情報オリンピック 本選(オンライン) | AtCoder

033 JOI本戦 08-1 IOIOI

A: IOIOI - 第8回日本情報オリンピック 本選(オンライン) | AtCoder

やるだけ。

Submission #1662126 - 第8回日本情報オリンピック 本選(オンライン) | AtCoder

034 JOI本戦 09-1 旅人

A: 旅人 - 第9回日本情報オリンピック 本選(オンライン) | AtCoder

やるだけ。

Submission #1662199 - 第9回日本情報オリンピック 本選(オンライン) | AtCoder

競プロ百物語 020-025 17/9/23-25

競プロ百物語について

ecasd-qina.hatenablog.com

解いた問題

020 AGC-A Ice Tea Store AC

A: Ice Tea Store - AtCoder Grand Contest 019 | AtCoder

貪欲法でいけた。

Submission #1623921 - AtCoder Grand Contest 019 | AtCoder

021 ARC-E TrBBnsformBBtion AC[1WA]

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder

項書換えだった、なんかできた。

Submission #1623989 - AtCoder Regular Contest 071 | AtCoder

022 ABC-C 背の順 AC

C: 背の順 - AtCoder Beginner Contest 041 | AtCoder

はじめてpair使った。

Submission #1626748 - AtCoder Beginner Contest 041 | AtCoder

023 atcoder Typical DP Contest-E 数 AC

E: 数 - Typical DP Contest | AtCoder

解説見ながら桁DPした。

Submission #1613598 - Typical DP Contest | AtCoder

024 atcoder Typical DP Contest ナップザック AC

H: ナップザック - Typical DP Contest | AtCoder

むずい〜。

Submission #1613485 - Typical DP Contest | AtCoder

025 JOI本戦 07-2 最長の階段

B: 最長の階段 - 第6回日本情報オリンピック 本選(オンライン) | AtCoder

いい感じに前処理したらできた。

Submission #1613031 - 第6回日本情報オリンピック 本選(オンライン) | AtCoder

競プロ百物語 015-019 17/9/22

競プロ百物語について

ecasd-qina.hatenablog.com

解いた問題

015 JOI予選 07-5 品質検査 AC

E: 品質検査 - 第6回日本情報オリンピック 予選(オンライン) | AtCoder

適当にやったら解けた。

Submission #1610477 - 第6回日本情報オリンピック 予選(オンライン) | AtCoder

016 JOI予選 08-4 星座探し AC[1WA]

D: 星座探し - 第7回日本情報オリンピック 予選(オンライン) | AtCoder

座標を適当に決めて全探索。

Sign in - 第7回日本情報オリンピック 予選(オンライン) | AtCoder

017 JOI予選 08-6 船旅 AC[1WA]

F: 船旅 - 第7回日本情報オリンピック 予選(オンライン) | AtCoder

ダイクストラでやるっぽかったけどダイクストラ知らないので適当に組んだら動いた。

Submission #1612011 - 第7回日本情報オリンピック 予選(オンライン) | AtCoder

018 JOI予選 09-4 薄氷渡り AC

D: 薄氷渡り - 第8回日本情報オリンピック 予選(オンライン) | AtCoder

DFSで全探索した。

Submission #1612308 - 第8回日本情報オリンピック 予選(オンライン) | AtCoder

019 JOI予選 10-4 カード並べ AC

D: カード並べ - 第9回日本情報オリンピック 予選(オンライン) | AtCoder

これもDFSで通った。

Submission #1612510 - 第9回日本情報オリンピック 予選(オンライン) | AtCoder