Ecasdqina's MEMO.

メモ帳.

17'日本情報オリンピック予選に参加した話

結局

4完+部分点で416点でした。

JOI前

12時過ぎに起きました、目覚ましN個くらいかけてたのに全部消してしまった......
予選5分前くらいまでツイッターをしてました。

各問題について

A 鉛筆(Pencills)

cout << min((n/a+!!(n%a))*b, (n/c+!!(n%c))*d) << endl;  

00:01:18(100)

B 双六(Sugoroku)

1が連続する部分列の長さの最大+1

00:05:05(100)

C 幹線道路(Trunk Road)

全探索BFSですよね、バグります。

00:30:00(100)

D 水ようかん(Mizuyokan)

え〜全然わからなかったので(DPだったらしい)、全探索を書いて部分点10点を得ました。

02:53:54(10)

E 森林伐採(Deforestation)

拡張ダイクストラですよね、バグります。

01:30:23(100)

F L番目のK番目の数(LthKthNumber)

問題名からバグってませんか? 全然わからないので全探索を書いて部分点6点を得ました。

01:49:10(6)

JOI後

ツイッターを見たらボーダー上がるってみんな言っててこわいノエ......

あとがき

タプリスちゃん予想すごい

競プロ百物語 058-080 17/10/24-11/18

競プロ百物語について

ecasd-qina.hatenablog.com

解いた問題

058 ABC-C 九九足し算

C: 九九足し算 - AtCoder Beginner Contest 012 | AtCoder

全探索。

Submission #1711916 - AtCoder Beginner Contest 012 | AtCoder

059 ABC-C 123引き算

C: 123引き算 - AtCoder Beginner Contest 011 | AtCoder

貪欲法。

Submission #1711920 - AtCoder Beginner Contest 011 | AtCoder

060 ABC-C Atcoderプログラミング講座

C: AtCoderプログラミング講座 - AtCoder Beginner Contest 003 | AtCoder

貪欲法。

Submission #1712139 - AtCoder Beginner Contest 003 | AtCoder

061 ABC-C Dubious Document 2

C: Dubious Document 2 - AtCoder Beginner Contest 076 | AtCoder

全探索。

Submission #1732051 - AtCoder Beginner Contest 076 | AtCoder

062 ARC-C Reconciled?

C: Reconciled? - AtCoder Regular Contest 076 | AtCoder

場合分けして組み合わせ。

Submission #1732548 - AtCoder Regular Contest 076 | AtCoder

063 ARC-C たくさんの数式 / Many Formulas

C: たくさんの数式 / Many Formulas - AtCoder Regular Contest 061 | AtCoder

Bitで全探索。

Submission #1732687 - AtCoder Regular Contest 061 | AtCoder

064 ABC-C Blue Bird

C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

ダイクストラ

Submission #1732721 - AtCoder Beginner Contest 022 | AtCoder

065 JOI予選 10-5 チーズ(Cheese)

E: チーズ (Cheese) - 第10回日本情報オリンピック 予選(オンライン) | AtCoder

BFS。

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

066 JOI本戦 11-1 JJOOII(JJOOII)

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

全探索。

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

067 JOI本戦 11-2 たのしいカードゲーム(Card Game is Fun)

B: たのしいカードゲーム (Card Game is Fun) - 第11回日本情報オリンピック 本選(オンライン) | AtCoder

全探索。

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

068 JOI予選 07-5 おせんべい

E: おせんべい - 第7回日本情報オリンピック 予選(オンライン) | AtCoder

全探索。

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

069 ARC-C pushpush

C: pushpush - AtCoder Regular Contest 077 | AtCoder

deque

Submission #1748282 - AtCoder Regular Contest 077 | AtCoder

070 ARC-A 2兆円

A: 2兆円 - AtCoder Regular Contest 057 | AtCoder

場合分け+シミュレーション。

Submission #1748465 - AtCoder Regular Contest 057 | AtCoder

071 JOI予選 16-4 ぬいぐるみの整理(Plush Toys)

D: ぬいぐるみの整理 (Plush Toys) - 第16回日本情報オリンピック 予選(オンライン) | AtCoder

BitDP

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

072 JOI予選 16-5 尾根(Ridge)

E: 尾根 (Ridge) - 第16回日本情報オリンピック 予選(オンライン) | AtCoder

下から見ていく。

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

073 ARC-C こだわり者いろはちゃん / Iroha's Obsession

C: こだわり者いろはちゃん / Iroha's Obsession - AtCoder Regular Contest 058 | AtCoder

全探索。

Submission #1752550 - AtCoder Regular Contest 058 | AtCoder

074 ARC-C 怪文書 / Dubious Document

C: 怪文書 / Dubious Document - AtCoder Regular Contest 071 | AtCoder

最大公約数的。

Submission #1754485 - AtCoder Regular Contest 071 | AtCoder

075 AGC-A A+...+B Problem

A: A+...+B Problem - AtCoder Grand Contest 015 | AtCoder

考える。

Submission #1769732 - AtCoder Grand Contest 015 | AtCoder

076 JOI予選 15-4 JOI国のお散歩事情(Walking in JOI Kingdom)

D: JOI国のお散歩事情 (Walking in JOI Kingdom) - 第15回日本情報オリンピック 予選(オンライン) | AtCoder

DP

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

077 ARC-A 数え上げ

A: 数え上げ - AtCoder Regular Contest 055 | AtCoder

やるだけ。

Submission #1777392 - AtCoder Regular Contest 055 | AtCoder

078 ABC-C Bridge

C: Bridge - AtCoder Beginner Contest 075 | AtCoder

DFS

Submission #1780663 - AtCoder Beginner Contest 075 | AtCoder

079 ARC-C 高橋君とカード / Tak and Cards

C: 高橋君とカード / Tak and Cards - AtCoder Regular Contest 060 | AtCoder

DP

Submission #1780698 - AtCoder Regular Contest 060 | AtCoder

080 ABC-D Axis-Parallel Rectangle

D: Axis-Parallel Rectangle - AtCoder Beginner Contest 075 | AtCoder

全探索。

Submission #1780748 - AtCoder Beginner Contest 075 | AtCoder

競プロ百物語 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