10/13-10/19

今週はvirtualはお休み(毎週お休みしそう)。
CFでレートを下げただけの週だった...。

出たコンテスト

KUPC2019 34位
CF#592(Div.2) 372位 2017->2008
CGR#5 2498位(????) 2008->1908
CF#593(Div.2) 335位 1908->1938
ABC143 23位

解いた問題

KUPC2019-D MaxMin Game

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d
i+1回目に勝ち負けが入れ替わったとする。このとき、i回目までに1以上2i以下のカードが全て手札から出ていることが必要。
よって、入れ替わるタイミングでは最初がどんな手札でも出ているカードの集合は同じなので、勝ち負けが変化しないようないくつかの区間に分割して考えられる。
そのような長さkの区間内で2人にカードを分配する通り数は、「最終的に|A|=|B|となり、常に|A|>=|B|を満たすように、前から集合A,Bに分配していく通り数」となる。これは実は、長さkの括弧列の数と同じである。これはカタラン数として知られており、C(2k,k)-C(2k,k-1)となる。
これを全ての区間について求め、掛け合わせれば答えが求まる。

KUPC2019-F カズマ王国の陥落

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f
各拠点から、ある1つの街だけに派遣するような最適解が存在することが示せる。
区間を右端でソートし、次のようなDPを考える:
dp(i,j):i番目の区間まで見て、今まで派遣した中で最も右にある街がjのときのダメージの最大値
右端が単調増加しているので、遷移元が狭まることがなく、このDPで最適解を求めることができる。
遷移にO(N)かかるように見えるが、累積maxを取っておくことでO(1)ででき、O(NM)でこの問題が解けた。

Mujin Programming Challenge 2017-B Row to Column

https://atcoder.jp/contests/mujin-pc-2017/tasks/mujin_pc_2017_b
明らかに、全てのマスが黒になるまでに初めてある1行が全て黒になる瞬間がある。これをi行目とし、iを決め打った時の全て黒になるまでの最小操作数を求める。
(i,j)が黒くなっていないとき、(k,i)が黒いようなkが存在するならば、(i,j)は1回で黒くできる。もしこれが存在しないなら、マス目上に1つでも黒いような(l,k)が存在すれば、最初に(l,k)->(k,i)と1回操作しておくことで、1回で(i,j)を黒くすることができる。これを全てのjについて考えれば最小操作数が求まる。
実は、これに「元から全て黒くなっていないような列の数」を足したものが答えとなる。明らかに、i行目を黒くする過程でそのような列数は増えることがない。また、実は減ることもないことが示せるので、これがiを決めた時の最適解となることがわかる。
これを全てのiについて計算するので、適当な前計算をすればO(N^2)で解ける。黒いマスが存在しないときは-1を出力すればよい。

天下一プログラマーコンテスト2016予選B-C 天下一プログラマーコンテスト1999

https://atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_c
本戦の順位によって人を並び替えておく。以下、ハシモトくんの記録上の勝ち負けを考える。
dp(i,j):i番目の人まで順位が一致していて、i番目の人がj回勝ったような確率 というDPを考える。
遷移は、dp(i,j)=sum{dp(i-1,k)}*f(i,j) のようになる。予選順位によってkの下限がjかj+1か決まる。f(i,j)は「i番目の人がj回勝つ確率」であり、これは各iについてO(N^2)で計算できる。dp(i,j)の遷移はO(N)でできるので、全体でO(N^3)で解けた。

ARC067-F Yakiniku Restaurants

https://atcoder.jp/contests/arc067/tasks/arc067_d
訪れる中で番号が最小の焼肉店をL、最大の焼肉店をRとおくと、LからRへ順に移動していくことで、移動距離の最小値を達成できる。よって、L,Rを決めれば、区間［L,R］における焼肉の美味しさの総和を最大化すればよくなる。
各チケットは、区間内で自由に使う場所を決められるので、区間内でもっともBの大きい場所で使えばよい。
Segtreeを使えばO(MlogN)で区間を決めた時の美味しさの総和の最大値がわかるが、全体でO(N^2MlogN)となってしまい間に合わない。
f(L,R):区間［L,R］における焼肉の美味しさの総和の最大値 というテーブルfを計算したい。
焼肉(i,j)が食べられるような区間［L,R］の条件を考える。全ての(i,j)についてこれが求まれば、f(L,R)にB(i,j)を足していくことで全てのf(L,R)が求まる。［L,R］でのチケットjで食べられる焼肉の中でのBの最大値がB(i,j)となればよい。
この条件は、「S<=L<=i,i<=R<=Tを満たす任意の［L,R］」という形になる。S,Tは、setを持ちながらBの小さい方から見ていくことで、各チケットごとにO(NlogN)、全体でO(MNlogN)で求められる。Bが等しいもの同士も、適当に順序付けすることでうまく処理できる。
後は条件を満たす［L,R］について、B(i,j)を足しこめばよい。
二次元平面上で考えると、長方形領域に値を加算していく形になっている。これは二次元imos法でO(NM+N^2)でできる。
これでf(L,R)が求まったので、この問題が解けた。

ABC143-F Distinct Numbers

https://atcoder.jp/contests/abc143/tasks/abc143_f
Ci:「Aj=iなるカードjの個数」とする。
X回操作すると仮定し、これが可能である条件を考える。問題は、次のように言い換えられる。
「X行K列のマス目に、数列Aの中から1つずつ数を書き込んでいく。同じ行に同じ数が入れてはいけない。マス目を全て埋められるか？」
明らかに、Ci>=Xなるiは、iで一列埋めてしまうのが最適。
後は、残っている列をCi=Xなるiの個数)*X+(Ci=X*K」が条件だとわかった。
単調性より、後はXを二分探索すれば答えが求まる。
累積和などで必要な値を適当に前計算しておけば二分探索内の判定はO(1)でできるので、全体でO(NlogN)で解けた。

感想

学校の後のCodeforcesは必ず仮眠を取る！

10/6-10/12

出たコンテスト

🤔

IOI2013 Day 2 Virtual

今までやった5時間セットで一番成績がよかった。
100+100+63=263点、Day1と合わせて430点、銀の真ん中らへんなので適正という感じ。
~0:30くらい 1問目を読むと、30分で76点、定数倍が軽ければ100点が取れる解法がわかってしまう。
76点でも取っておいたほうがいいと思ったので実装する。
0:47 1WAを出したが、1問目が通る。にぶたんの区間に気をつけよう。
~1:20くらい 2問目を読むと、よい性質に気づいて一気に90点、定数倍が軽ければ100点が取れる解法が15分くらいで分かる(定数倍ゲー多い...)。
1:50 書いたコードの定数倍が軽かったらしく、2511ms/3000msで通る。
~2:10くらい 明らかに「動的二次元セグ木を書きなさい」という問題だが、闇な気がしたのでやる気をなくす。とりあえずただの二次元セグ木で取れる63点を取ることにする。
2:22 3問目の63点が通る。動的二次元セグ木を導出しようと頑張る気が起きなかったので撤退。(時間が半分で終わってしまった...)

難易度はたぶん8-9-11みたいな感じ。
1問目 Cave
小課題3までは省略。
ドアを左から見ていき、順に対応するスイッチとその正しい状態を当てることを考える。
制約を見るとlogがつきそうなので、二分探索を考える。
「対応が未決定のスイッチの中の左からX個選んだ集合について、今見ているドアと対応するものがあるか？」という問題が解ければ、Xについて二分探索することで答えが求まる。
実はこれは、「左からX個選んだ集合」のスイッチを反転させ、元の状態での質問の答えと比較することで、1回の質問で知ることができる。
クエリ呼び出しはO(NlogN)回、時間計算量はO(N^2logN)となるので、適当な枝狩りをすれば間に合う。

2問目 Robots
実は、最適解において、「弱い」ロボットが運ぶおもちゃを考えると、「Xi>=Xjならば(iが運ぶ任意のおもちゃのW)>=(jが運ぶ任意のおもちゃのW)」が成立することが示せる。この性質を利用する。
解を二分探索することを考えると、「K分以下で片付けられるか？」という問題を解けばよくなる。
まず、「弱い」ロボットにおもちゃを割り当てる。このときロボットiは、「重さXi未満の残っているおもちゃの中で、大きさの大きい方からK個以下」を取るのが最適となる。ロボットをX、おもちゃをWでソートし、尺取り法とpriority_queueを用いることでO(TlogT)でどのおもちゃが取られるかが分かる。
その後は、「小さい」ロボットに、普通に大きさの小さい順に割り当て、最終的に全てを割り当てられたかを判定すればよい。これもO(TlogT)でできる。
時間の最大値がTであることから、O(T(logT)^2)で解けた。

3問目 Games
GCDはセグ木に乗るので、66点までは普通の二次元セグ木を実装すれば取れる。
80点は二次元動的セグ木、100点はそれのメモリ削減が必要らしい。
動的セグ木は、ポインタベースで「ノードが必要になったら作る」ということをすれば書ける。
これを応用すれば二次元にできる。(実装する気が起きない...)

解いた問題

AGC038-C LCMs

https://atcoder.jp/contests/agc038/tasks/agc038_c
Aiの最大値をVとする。今、S(k)=(gcd(i,j)==kなる(i,j)に対するijの和)とすると、lcm(i,j)=ij/gcd(i,j)より、1<=k<=VにおけるS(k)/kの和が答えとなることが分かる。
T(k)=(i,jがともにkの倍数となるような(i,j)に対するijの和)とする。T(k)=(iがkの倍数となるようなiの和)^2 となるので、調和級数より、O(NlogN)で求められる。
T(k)からS(k)を求めるには、余計に数えている分を引く必要がある。実は、kを上から見ていったとき、S(k)=T(k)-(kより大きいkの倍数lにおけるS(l)の和)となるので、これも調和級数からO(NlogN)で求められ、この問題が解けた。
数えなくていい部分も数えているのでAiの和を引いて1/2をすると答えになる。

ABC140-F Many Slimes

https://atcoder.jp/contests/abc140/tasks/abc140_f
Sを大きい順にソートしておく。明らかに、S1が最初のスライムとなる。
時系列順、同じ中では親の大きさ順にスライムを決めていく。
新たにできるスライムの大きさを考えると、「親のスライムより小さいSの中で最大の大きさ」とするのが最適。
もし最大でないものを取ったとして、その後で使われる最大のものとこれをswapしても損しないからである。
これを愚直に実装し、もし途中で構築できなくなったらNo。

CODE FESTIVAL 2016 qual B-E Lexicographical disorder

https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e
SiがSjより辞書順で大きいとき、
1.SjはSiのprefixである
2.最初から見て、2つが初めて相異なるような場所で、Sjの方がSiより辞書順で前にある
のどちらかである。
Trie上で考える。
1.の場合はTrieで前計算することができる。
2.の場合について考える。
「f(i,j,k):Siと他のある文字列Tとの辞書順が決まる場所において、Siの文字がj、Tの文字がkとなるようなTの個数」というテーブルfを前計算しておく。
これはTrie上で、26*O(sum(|S|))程度の計算回数で求めることができる。
各クエリにおいては「Skiより辞書順で小さい文字列の個数」を求めればよい。1.の場合は明らかで、2.の場合は、新しい辞書順でSiの方が後にくるようなfの値のみを足せばよい。
クエリ回答も26^2*O(Q)程度の計算回数で求まるので、制限時間6secに間に合う。

感想

台風のせいで土曜にまともに競プロできなかった、悲しい

9/29-10/5

この場所を有効活用したいと思ったのでばちゃの結果を書くことにした。代表になれないのにIOIばちゃをする人になった(大学生になったらどうせ解かないし...)。
できる日は5時間ばちゃをやってここに記録するようにしたい。

出たコンテスト

CF#589(Div.2) 3完 2095->2017
AGC039 2完 2027->2043

IOI2013 Day1 virtual

100+12+55=167点。謎問題で点数がだいぶ左右されるのつらそう。

~0:20くらい 1問目、2問目を読む。2問目が謎なので後に回すことにして、1問目はすぐに小課題3まで分かる。
~0:40くらい 1問目の小課題4が分かり、それに連動して満点解法も分かる。自分がこの時間で分かるということは簡単枠だろうと思ったので実装することにする。
1:07 1問目の小課題4だけ通る。なぜか一緒に取ろうとした小課題1が通らない。
1:51 謎だったので満点解法を実装すると、通らない理由がわかる。なぜか65点。
1:54 M=N-1で壊れていることに気づく。100点。
2:41 3問目を読むと、小課題3まで分かったので書くと通る。
2:54 すぐに小課題4もわかったので通す。それ以降はヤバい臭いがするので飛ばす。
3:57 2問目がよくつかめなかったので雰囲気で書いて出す。6点。
4:16 微妙な改善を投げるが12点。そのままコンテスト終了。

1問目 Dreaming

各連結成分について、「そこからの連結成分内への距離の最大値が最小となる頂点」のみ他の連結成分と繋げればよい。これに気づくと、次の3つの問題を解けばよくなる。
・木の中で最も遠い2頂点間の距離を求めよ。
・木の中で、「ある頂点を根にしたときの深さの最大値」の最小値を求めよ。
・頂点ごとにコストviが定まっているN頂点0辺のグラフがある。これにN-1辺を追加して、d(i,j)=vi+vj+(iとjの距離)*L の最大値を最小化せよ。
1つ目と2つ目は、全方位木DPをすることで求まる。
3つ目は、実はviが最大の頂点から他の全頂点へ辺を張るのが最適となる。
これは、viが最大な頂点をmとして、m-t1,t1-t2に辺が張られているとき、m-t1,m-t2 に辺を張り直しても損をしないことからわかる。
これでO(NlogN)で解けた。

2問目 Art Class

画像分類をしてくださいという問題。
無思考で「差の二乗和」とかを求めて特徴量を探そうとしていた。
なにもわからない...

3問目 Wombats

55点までは省略。ここから非自明パート(解説を見た)。
最短路テーブルをセグ木に載せることを考える。具体的には、列iから列jまでを被覆するノードでは、「C(p,q)=(i,p)から(j,q)への最短路の長さ」を任意のp,qについて求めたテーブルCを持つことにする。
「D(i,j)=i行目からj行目への、任意の列の2組の最短路テーブル」を求めたいとする。進行方向の性質から、これはi < k<=jなるkについて、D(i,k-1)とD(k,j)から求めることができる。愚直に計算するとO(C^3)。
k-1側の出る場所を固定すると、実は、k側で入る場所を右に動かすにつれ、「k-1からkへ移動する列」も右に動いていくことがわかる。この性質を使えばO(C^2)で求められる。
k=(i+j)/2とすることでセグ木のマージが同じようにできるので、辺更新1回についてO(C^2logR)でできる。
回答クエリについては、全体を被覆する区間を見るだけでよい。O(1)でできる。
これで解けた...と思ったが、実はサイズR*C^2のテーブルを用意しただけでMLEする。時間には余裕があるのでセグ木を工夫するとできるらしいが、面倒になって実装していない...。

解いた問題

JSC2019決勝-A Equal Weight

https://atcoder.jp/contests/jsc2019-final-open/tasks/jsc2019_final_a
15分くらい。300ではない。
まず、A,Bが相異なるので、条件を満たす組で同じシャリやネタが2回使われることはない。
握りの重さの種類数は高々2*10^6通りであることに注目する。
愚直全探索を考えると、シャリとネタの組を全部試し、重さに被りが出たところで終了、というようになり、これはO(NM)に見える。しかし、2*10^6通りより多い組を試した時点で1つ以上被りが生まれるはずである。そのため、2*10^6+1通りより多い通り数が試されることはなく、間に合う。

CF1228E Another Filling the Grid

https://codeforces.com/contest/1228/problem/E
コンテストが後5分長ければ通っていた...。
1の置き方を決めていくことを考えると、「行の中で最初に1が現れる列」が単調増加すると仮定して、
dp(i,j,k):i行目まで見て、i行目の中で最初に現れるのがj列目で、jがk回連続しているときの通り数
というDPをすると、累積和を使って面倒だがO(N^3)で解ける。コンテスト中はこの方法でやった。
上のDPは1の順序を固定してやったせいで面倒になっているが、冷静に考えると「1が既に入っている列の個数」さえ求まっていればよいことがわかる。
dp(i,j):i行目まで見て、1がj個の列に入っている時の通り数
というDPでO(N^3)で解ける。
また、実はこれは包除原理が使える。「i個の行、j個の列に1が含まれていないことがわかっている時の通り数」を計算し、偶奇に応じて足し引きすればよい。O(N^2)で解ける。「または」のみの式は「かつ」の通り数を足し引きすることで求められる、というのが包除原理。

JSC2019決勝-C Maximize Minimum

https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_c
座標xにあるイチゴについて、min(x,L-x)に置いてあるとして考える。
間に2つ以上イチゴのある2つの距離が答えになることはない。また、L/2に最も近い2つについて、(最も近いものを折り返した時の2つの距離)より距離が長くなることはない。よってこれと「間に1つイチゴがあるような2つの距離の最小値」とのminが答えの下界となる。
これは、「左から偶数番目にあるやつを折り返す」というように決めると達成できる。
L/2に近い2つの方の距離は毎回計算してよい。間に1つイチゴがあるような2つの距離は、この2つの集合が一度の操作で定数個しか変化しないことを用いると求められる。
「今の座標の集合」と「間に1つイチゴがあるような2つの距離の集合」をmultisetで管理すればO(NlogN)で解ける。
実装がとてもつらい。

AGC039-B Graph Partition

https://atcoder.jp/contests/agc039/tasks/agc039_b
V1に入れる頂点を1つ固定し、全頂点への最短距離を計算する。すると、最短距離がdの頂点をV(d+1)に入れるのが最適となる。なぜなら、Vi(i>d+1)に入れると壊れるのは明らかで、Vi(i<=d)に入れたとしても、それが条件を満たすならばV(d+1)に条件を満たしたまま移動できるからである。これは最短距離の性質を考えるとわかる。
このようにして構築したグラフのうち、条件を満たすものがなければ-1、あればd+1の最大値が答えとなる。

感想

相変わらず競技プログラミングをする時間がない。
PGBATTLEで入賞していてうれしかった。

9/22-9/28

ブログっぽいことをしようと思いました。

出たコンテスト

CF#558(Div.1) 2完 2018->2095
PG BATTLE 結果不明
ABC142 6完 1982->2027

解いた問題

手応えのあった問題だけ。

JOI2009春 1-2 Stamps

https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf
30分くらい。
新しい文字列T="IO"+S+"OI"としても、端の"IO""OI"を変化させることに意味はないので、Tのもとで考える。
Tは I..I とO..O が交互に繰り返される形になっている。これらのブロックをまるまる削除したり追加したりすると、2つまとめて消すことになり、必ず損をすることになる。
これでI..I、O..Oを独立に考えてよくなったので、操作回数が最小かつその中で文字列が最短になるものを考えると、
ブロックの長さLが奇数のとき floor(L/2)回変更する
Lが偶数のとき 1文字削ってfloor(L/2)回変更する
のが最適となる。
これを愚直に実装すればO(|S|)で解ける。

CF1229A Marcin and Training Camp

https://codeforces.com/contest/1229/problem/A
30分くらい。
「a_uで立っているbitがa_vで立ってない、またはa_u=a_v」の場合に(u,v)に有向辺を張ったグラフを考える。
明らかに、入次数=0な頂点は使えない。また、それを消すことによって入次数=0になる頂点は使えない。
これを再帰的に繰り返していき、残った頂点は全て入次数>0であり、これらを全て選ぶのが最適。
bit演算を使えば高速にグラフを構築でき、O(n^2)で解けた。

CF1229B Kamil and Making a Stream

https://codeforces.com/contest/1229/problem/B
コンテスト中はこの解法が間に合うとは全く思ってなかった。解説AC。
ある列Aについて、gcd(A_0),gcd(A_0,A_1),...,gcd(A_0,A_1,...,A_N)の中での種類数がO(logA_0)であるということを使う。これは、順に見ていった時にgcdが減る場面では必ず1/2以下になるということから分かる(gcdで掛けられている素因数が1つ以上減るので)
葉側の頂点vをDFSしながら走査していく。unordered_mapを使って「根からvまでのパスの中の、vを含むgcdの集合」を種類ごとに管理できるので、O(nlog(xmax))で解けた。

CF1229C Konrad and Company Evaluation

https://codeforces.com/contest/1229/problem/C
40分くらい。
稼ぐ額が大きい方から小さい方へ辺を張った有向グラフとして見ると、頂点が更新されたときに、入ってきている頂点を全て出ていくように変更し、差分を計算する、という処理をすればよいとわかる。
実は、これを愚直に実装するだけでACできる。
クエリを√M個のブロックに分割して考える。
・頂点がブロックで初めて更新されたとき　
これで更新される辺数の和が2M(次数の和)以下であることは明らか。
・頂点がブロックで2度目以降に更新されたとき　
各頂点について、1度更新されると入次数は0になり、1つのクエリについて高々1つしか入次数は増えないので、ブロック内のクエリ数から、変更する必要のある辺数は√M回以下。よって合計でM回以下。
これを合わせて、O(Q√M)になる。

ABC142-F Pure

https://atcoder.jp/contests/abc142/tasks/abc142_f
「全頂点が入次数1、出次数1のグラフ」はサイクルの集合となる。このうち1つ構築すればよいので、1つのサイクルになるような誘導部分グラフを求めればよい。
まず、元のグラフにサイクルがなければ明らかに-1である。そうでなければ必ず以下のように構築できる。
サイクルの始点を決め、順に見ていく。後ろから入ってくる辺があれば自分の前にある頂点、「入ってくる元の頂点」の後にある頂点は使わないようにする。後ろへ出ていく辺があればその間にある頂点はグラフに含めないようにする。この結果できるグラフは必ず2頂点以上のサイクルになるので、条件を満たす。

感想

コンテスト以外で1問しか解いていなくてまずい。こういうのを可視化していきたい。

JOI2018/2019本選 参加記

あったことを羅列します。

1日目

10時くらいに起きてTwitterを見つつ適当に出る。
北千住でTMJNと会ったので毒蛇の脱走の考察をするが、なにもわからなくなりやめる。TMJNが天才っぽいことをしていて天才。
会場に着くと同校が大量にいたので固まる。パズルに自分のIDが使われていて笑っていた。

プラクティスは最初ログインできなくて焦ったものの普通に全完。
マインスイーパをして(最後の1つで死んだ)、双子などのところに行くとTwitterで知ってる人々がいたので話す。E869120の予想がこわかった。

講義があったが、難しかったので割り算はにぶたんすればできるなーとかどうでもいいことを考えていた。
夕食は貪欲法を使った。自己紹介フェーズで嘘解法で通さないことを宣言する。

バスで宿に向かって部屋に入るとすぐみんぷろが始まったので出る。
Cまでは普通で、Dが一生解けなくて冷えたのでFに行ったら15分で解けて「は？？？？」って言ってた。
黄ぱふぉ1816->1869であたたまる。

絶起が不安で寝付けないとかいう状態になっていたが、気がついたら意識がなかった(起きたら周りに人が血だらけで倒れていたわけではない)。

2日目

6:45に目覚ましをかけたのに6:00に起きてしまう。二度寝しようとしたが不安になったので起床。
朝食は適当に食べてFAした気がする。
バスで会場に移動した後、色々な部屋を経由して会場に入る。

開始まで30分くらいあったので「1300問解いたし落ちるわけが無くないか？」とか思いながら虚空を見つめていた。

1問目は無限回見たやつなので8分くらいで解ける。

2問目は一瞬で分かったように見えて嘘で、頭を入れ替えて考えると降順に見ればいいことが分かるので解ける。この時点で20分。

3問目は問題名からしてセグ木かな？となる。
これは嘘で、制約を睨むとO(N^3)のDPが生えるので書く。部分点はよく分からなかった。
自信満々で出すと何故かTLEしていて(75点)、制限が500msなので定数倍がダメだと思って色々する。TLE。
焦ってコードとにらめっこしていると、DPの中でにぶたんをしていたのがボトルネックだと分かる。
前計算に変えてAC。この時点で80分くらい。

4問目は見た目的に苦手そうだなぁとなるが、とりあえず自明な8点を取って次へ。

5問目も4点は自明なので取れるが、それ以降が全くわからないので4に戻る。
xの小さい方から決めていけるなーと思うとDPが生えて、これで29点が取れる。
この時点で残り110分、341点だったので通ったかな？となる。

この後は1点も取れなかった。最後の30分は完全に諦めて虚空を見つめていたので落ちたかなーとか思っていた。
終わったので人のところに行くと、341点が大量らしく驚く。
2が虐殺問だったらしく背筋が冷える。下手したらハマって焦って死んでた気がしていたので。

E869120の乗っ取られたツイートにふぁぼりつつ昼食を食べる。
解説を聞くが、5が初っ端から理解できなくて頭の悪さを痛感した。
解散後はカラオケに行って帰宅。

結果

春通りました。

感想

コミュニケーションが下手すぎる 失礼なことをしていたらごめんなさい

JOI2018/2019予選 参加記

開始前

・SSSS.GRIDMANを見る
・眠かったので音ゲーをして目を覚ます

1問目

・見る
・数学ゲーっぽくて嫌だなあとなる
・ログイン日数を固定するといい感じになるので、書く
・WA(は？)
・コードを睨むとオーバーフローしているので、直す
・AC(05:09)

2問目

・雰囲気からしてシミュレーションするだけでは
・書く
・AC(09:44)
・1問目の方が難しかった

3問目

・見る
・前から決められるなあとなる
・適当なDPを書く
・WA(は？？)
・遷移をミスっていた
・AC(16:25)
・もっといい解法がありそう

4問目

・見る
・Employmentじゃーん
・下から見ていって、隣との関係を調べるだけでいい
・書く
・サンプルが合わない
・合う
・出す
・WA(は？？？)
・同じ高さのが隣り合ってるところがやばそう
・圧縮する
・AC(46:00)
・ボーダー400越えそうだなあとか思っていた

5問目

・区間がいっぱいあるらしいのでとりあえず終点ソートを書く
・dp[i]:i番目にイルミをつけるときのiまでの美しさの和のMAX
・遷移させちゃいけない範囲を求めたいなあとなる
・終点ソートしたおかげですぐに求まる
・セグ木を貼る
・AC(80:37)
・実家のような安心感

6問目

・とりあえず6点を取る
・20分くらい座っているだけをする
・「挿入DP」というワードが降ってくる
・ググる
・O: 文字列 - Typical DP Contest | AtCoder
・勝ちを確信する
・解説記事を見る
・何もわからない
・何もわからない
・残り10分くらいで諦める
・記事を書き始める
・終了

感想

6問目難しすぎる
ボーダーが高そうで怖いです

picoCTF 2018に出た

10110点で終了時730位くらい。
Warmup以外について雑に書きます。

Forensics

Desrouleaux(150)

画像を見れば答えが分かるので答えていくだけ。もう少し問題が難しくなるとスクリプトを書いたほうがよさそう。

Reading Between the Eyes(150)

Hintsにあるように、PNGのデコーダを使う。

admin panel(150)

Wiresharkで眺めているとadminのパスワードがFlagになっている。

hex editor(150)

vimで-bオプションをつけて開き、:%!xxd と入力するとhexdumpが表示される。
/picoCTF でファイル内を検索するとFlagが出てくる。

now you don't(200)

ペイントで塗りつぶしてみると、Flagが浮かび上がってくる。

Lying Out(250)

画像を見ると答えがわかるので答えるだけ。

What's My Name?(250)

大量のデータがあるので眺めてみると、ローカルIPアドレス同士で通信しているところが見つかる。そこにFlagがある。

LoadSomeBits(550)

バイナリを眺めると、最初の方にやけに1と0が並んでいる。ヒントと合わせて、Flagの形式になるように取っていくとできる。
スクリプト書いたら楽なんだろうけど手作業で求めてしまった。

General Skills

grep 1(75)

grepコマンドは使えますか？

net cat(75)

ncコマンドは使えますか？

strings(100)

stringsコマンドは使えますか？

pipe(110)

パイプって知ってますか？

grep 2(125)

grepコマンドは使えますか？(二回目)

Aca-Shell-A (150)

ls,whoami,cd,rm,cpコマンドは使えますか？

environ(150)

printenvコマンドは使えますか？

ssh-keyz(150)

Hintsにあるページを見たりググったりすると方法がすぐ見つかるのでその通りにやる。

what base is this?(200)

Pythonでどんな関数を使うと2進数や16進数を文字列に変換できるか調べ、その通りにやる。

you can't see me(200)

ls -a で隠しファイルを表示でき、-b で印字できない文字をエスケープしてくれるので、
あとはcat (エスケープされたファイル名)で中身を表示すればいい。

in out error(275)

言われたとおりに入力すると、怪しい文字列が大量に出力される。
よく見ると1文字おきにFlagっぽい文字が配置されているので、それを順に取っていくとFlagになる。

learn gdb(300)

GDBを使えと言われたのでGDBで開き、プログラムが終了する前にブレークポイントを置いてflag_bufの中身を確認する。

store(400)

コードを読むと買うflagの数をint型で受け取っているので、INT_MAXあたりの値を入れるとtotal_costが負数になり、balanceを増やせる。これでFlagを買うことができる。

Reversing

assembly-0(150)

結局戻り値(eax)=2つ目の引数(DWORD PTR [ebp+0xc])になるので。

assembly-1(200)

適宜命令を調べつつ処理を順に追っていくと分かる。

be-quick-or-be-dead-1(200)

どうやら処理を高速化すればいいらしい。calculate_keyという関数の逆アセンブルを読むと、0x6ff54b3dからインクリメントしていき、0xdfea967aと等しくなるまでループを続けている。これでは間に合わないので、加算する値を0x1bなどに変更して実行するとFlagが表示される。
radare2が無限に便利だった。

assembly-2(250)

これも処理を追っていくだけ。

Radix's Terminal(400)

radare2で解析すると、Base64エンコードされたように見える文字列が見つかるのでデコードするとFlagになる。

assembly-3(400)

引数のスタックへの積み方への理解が甘く、手で計算できなかったため、main関数を書いて実行できるようにした。

Cryptography

caesar cipher 1(150)

シーザー暗号なのでC++で全探索するコードを書いた。

caesar cipher 2(250)

1との違いはアルファベット以外もあるくらいで、これを考慮して全探索すれば解ける。

rsa-madlibs(250)

RSA暗号の勉強になる問題。
調べつつ、言われた通りに解いていくとFlagとRSA暗号の知識が得られる。うれしい。

Safe RSA(250)

eの値が3と小さいので、Low Public Exponent Attackができる。
暗号文の3乗根を求めるだけで復号できる。
誤差がつらかったのでPythonのDecimal型を使って計算した。

Super Safe RSA 2(425)

今度はeの値が大きいので、Wiener's Attackができる。
数学ができないのでまだよく理解できてない...

Web Exploitation

Inspect Me(125)

とりあえずF12を押してみるとFlagのような文字列がHTMLのコメントに見つかる。
3つに分かれてるので全部見つけてくっつける。

Client Side is Still Bad(150)

コードを眺めるとパスワードの認証がそのまま書いてある。

Logon(150)

覚えてない1(ごめんなさい

Irish Name Repo(200)

SQLインジェクションができないか試そうと「' OR 1=1 --」を入力したらいけてしまった。

No Login(200)

Cookieをいじれる拡張を入れてadmin=Trueにしたらいけた。

Secret Agent(200)

ChromeのNetwork conditionsからUseragentをGooglebotにしたらいけた。

Buttons(250)

HTMLをいじってButton2をButton1と同じ形式にする。

The Vault(250)

覚えてない2(ごめんなさい

Binary Exploitation

buffer overflow 0(150)

覚えてない3(ごめんなさい

buffer overflow 1(200)

win()のアドレスを調べ、vuln()の戻りアドレスがそれになるようにバッファオーバーフローさせる。

leak-me(200)

nameをオーバーフローさせるとpasswordが手に入るので、それを利用してログインする。

感想

こうして見ると自明以外全然解けてない...