shpxで参加してました。 結果はpwnを2問解いて76位。 Writeup Da Lat city (Pwnable 100) ELF 32-bit、動的リンク、canaryとNX有効。 % file cheatme cheatme: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter …
ogteckで参加していました。 後輩と参加してましたが結局解いたのは自分だけでした。 Misc1問、Pwn2問解いて752点、86位。 PwnのRecho、RCalc、RNoteは個人的に面白かったです（RNoteは解けてないが）。 解いたチーム数によって点数が変わるシステムもよかっ…
angstromCTF チームで参加しました。 Crypto1問、Binary4問解いて470点。チーム全体で780点取り15位でした。 他のメンバーのWriteup Writeup Running in Circles (Binary 50) このCTFのBinaryはすべてソースコードも渡された。 ソースコードを見てみるとシェ…
https://asis-ctf.ir/challenges/ 今回は一人で参加しました。 7問解き、763点で65位でした。 初めてpwnをコンテスト中に解いたので満足。 Writeup Welcome! (Trivia 1), CTF Survey (Trivia 9) サービス問題 Start (Warm-up, Pwning 89) こちらの資料がとて…
shpxというチームを組ませていただいてから初めてのCTF。 700点を取り、117位という結果で終わりました。 個人では150+50+200(共同)点。全体的に全然わからなかったので精進が必要です。 Write up VC A.pngとB.pngを重ねたら文字が見えたのでそれを読むだけ…
CTF for ビギナーズに参加してきました。 解けない問題も多かったのですが運よく優勝しました。CTF for ビギナーズ 優勝しました pic.twitter.com/qjBqFGauV8— h_noson (@h_noson) January 29, 2017 Tシャツと本をいただきました。感謝 Writeup Misc 100 Wel…
巷で流行りのAmazon Dash Buttonで何かしようということで，競プロのAC数を数えてみたいと思います． 環境 Amazon Dash Button Python 2.7.13(scapy,requests_oauthlib) ボタンが押されたことを検知 ボタンが押されたことを検知できないと何も始まらないので…
問題 No.429 CupShuffle - yukicoder N個のコップについて交換の仕方・最終配置が与えられる．ただし，X回目の交換の仕方の情報が抜けている．どのコップを交換したかを求める問題． 解法 解説を見るとX-1回目までswapを行い，一方K回目からX+1回目まで逆順…
問題 E: Lexicographical disorder - CODE FESTIVAL 2016 qual B | AtCoder N個の文字列Siが与えられる．以下のクエリにQ回答える問題 整数kと{'a',...,'z'}を並び替えたp1,...,p26が与えられる．文字の順序がp1<p2<...<p26の時SkはN個の文字列の中で何…
問題 No.416 旅行会社 - yukicoder N個の点とM本の辺が与えられ，CiとDiの間の辺を壊すというクエリがQ個与えられる．それぞれの点は何回目のクエリで点1から到達できなくなるか答える問題． 解法 辺を繋いで（この問題では壊して）ある点から到達できるかを…
問題 Problem - D - Codeforces 3つのクエリに答える． 1. xをmultiset Aに加える 2. xをmultiset Aから取り除く 3. を出力する 解法1 c++のmultisetを使って二分探索をする． xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい．xを反転…
問題 Problem - C - Codeforces N角形のバスがやってくる．幅Wの道路をバスにぶつからずに渡るとき，最短の渡る時間を求める問題 解法 バスを固定すると人が右上に向かって移動することと等しくなる．もしぶつからずにそのまま行けるのであればそのまま行く…
問題 D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder N頂点，M辺からなるグラフがあり，Q組の兄弟がスタンプラリーを行う．i番目の兄弟はそれぞれXi，Yiにいて合わせてZiのスタンプを集めたいと思っている．通ることになる辺の最大の番号を最小にす…
トポロジカルソートを初めて書いた気がするので記事に残そうと思う 問題 C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder 文字列Ai,BiがN個ずつ与えられる．Ai 解法 トポロジカルソートを使う．AiとBiを左の文字から比較して初めて異な…
問題 Problem - E - Codeforces N個のデータと容量Kのキャッシュがある．キャッシュのアルゴリズムにLRUが使われていて，無限のクエリが飛んできたとき，最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか． 解法 簡単に言うと，キャッシュ…
問題 No.23 技の選択 - yukicoder 体力がの敵を 攻撃力の通常攻撃（必ず当たる） 攻撃力の必殺技（2/3の確率で当たる） の二つの攻撃を使って倒したい．最小の攻撃回数の期待値はいくつか． 解法 解説を見たら全部DPで解いていたが，通常攻撃の使う回数でル…
問題 https://www.codechef.com/problems/CHSQARR の行列が与えられる．個のクエリに対して以下の操作を行う． が与えられての範囲の数がすべて等しくなるように行列の要素の数字を増やすとき，増やす数の最小値を出力する 解法 範囲の和と範囲の最大値を使…
問題を見て，まず考えるべきことを問題の種類別にまとめていく． これから追加していくつもり．また，当たり前になってきたものは消していくかも． クエリ クエリを先読みしてソートしたりする 勝ち負けゲーム 対称性を作れないか 探索系 一度全探索の解法を…
問題 No.103 素因数ゲーム リターンズ - yukicoder 個の整数が与えられる． 一度の操作で任意の整数をその素因数で割ることができる．同じ素因数ならば２回まで同時に割れる． AliceとBobが交互に操作を行うとき，すべての整数をにできるのはどちらか．解法 …
問題 Problem - D - Codeforces の部屋があり，それぞれ宝箱が置いてある．タイプの宝箱にはタイプの宝箱を開ける鍵が入っている．タイプの宝箱を開けるまでに移動する最小距離はいくつか．解法 単純にタイプごとにダイクストラを行っていたら間に合わない．…
問題 No.318 学学学学学 - yukicoder 数列が与えられる．からについて順番に，同じ数で挟まれた数をで置き換える．書き換えられた後の数列を出力する問題．解法 双方向リストを使う．大きい数から順番に以下の操作を行う． 一番左のが，一番右のがとすると，…
テンプレートの読み込みはcppの場合、 autocmd BufNewFile *.cpp 0read $VIM/template/template.cpp とするのが普通だと思う。 しかしこの方法では、touchや>で作ったファイルやwindowsの新規作成で作ったファイルなどを編集する時に読み込みがされない。そ…
問題 Problem - C - Codeforces 行の銀行が円周上に並んでいる．隣の銀行に送金することが可能になっている．Aさんがそれぞれの銀行に口座を持っていて，お金を預けている（または借りている）．預けているお金を隣の銀行に送金することを繰り返し，すべての…
問題 Problem - B - Codeforces 文字列が与えられる．どの部分列をとっても同じ文字列が現れないように与えられた文字列を書き換えるとき，書き換える最小の文字数は幾つか．解法 部分列は1文字だけ考えればよい．つまり，すべて違う文字になるように書き換…
問題 Problem - A - Codeforces 123456789101112...といったように数字を1から並べた列がある．番目にくる数字は幾つか．解法 1から順に数字をstringに積んでいき，番目にきた数字を出力する．ソースコード #include <iostream> #include <vector> #include <algorithm> using namespace s</algorithm></vector></iostream>…
問題 No.174 カードゲーム（Hard） - yukicoder A君とB君がカードでゲームを行う．１から１０００までの数字が書かれたカードがあり，その中から枚ずつ配られる．試合は回あり，試合ごとにプレイヤーがカードを出していき，大きい数字を出したほうがその数字…
問題 Problem - F - Codeforces AさんはBさんにある数字にその数字の長さを右に付け足して送った．しかし，送られる途中で文字の順番がバラバラになってしまった．Aさんはその数字の部分列を覚えている．送った可能性のある数字の内，その部分列を含むような…
問題 Problem - E - Codeforces 対応する括弧が存在する括弧の列が与えられる．カーソルの初期位置と R : カーソルを右にずらす L : カーソルを左にずらす D : 今見ている括弧と対応する括弧の間の括弧を消して右に移動する という操作の列が与えられた時，…
問題 Problem - D1 - Codeforces クッキーを作ろうとしている．１つ作るのに種類の材料がずつ必要である．初めにずつ持っているとする．また，のマジックパウダーも持っており，そのパウダーはどの材料にも変えることができる．作れるクッキーの最大値はいく…
問題 Problem - C - Codeforces 人の人がいる．それぞれ使える言語は１つだけである．個の映画があり，音声と字幕は違う言語が使われている．１つの映画を全員で見るとき最も多くの人が満足できる映画はどれか． 音声に満足している人が等しいならば字幕で比…
問題 Problem - B - Codeforces ロボットが体いる．それぞれのロボットに番号が付けられている． 左のロボットから順番に，「ロボットの番号を一番左のロボットの番号から自分の番号まで言う」ことを行うとき，回目に言われるロボットの番号は幾つか．制約 …
問題 Problem - A - Codeforces 火星では１年が日続く．また，地球と同じように１週間は平日が５日，休日が２日ある． １年の休日の数の最大値と最小値はいくつか．解法 ７で割り，最大値を求めるときは余りに対してできるだけ休日から割り当て，最小値を求…
問題 No.241 出席番号(1) - yukicoder 人の生徒がいて，それぞれ出席番号を割り振る． １人１つ割り当てられたくない数字があるのでそれを避けるような割り振り方を１つ出力する問題．解法 ２部マッチングで解く． 生徒から割り振ることのできる番号へ結び，…
問題 No.132 点と平面との距離 - yukicoder ３次元上の点と個の点が与えられる． をから点を通る平面への距離とした時， を求める問題．解法 ベクトル，ベクトル，ベクトルに囲まれた三角錐の体積を求め，三角形の面積で割って３をかけることで，高さつまり…
問題 No.335 門松宝くじ - yukicoder 宝くじが２枚か３枚与えられ，それぞれ数字が個書かれている． 当選日になると１つの宝くじにつきランダムに２つの数字が選ばれる．１つ数字を自由に選ぶことができ，その３つの数字で門松列が出来れば３つの数字の最大…
解くのに10時間ほどかかった... 問題 TopCoder Statistics - Problem Statement 人が横に２列になって写真を撮る．それぞれの人はからまで番号がふられている． この時の並びは"nice"かつ"different"でなくてはいけない．"nice"とは，以上の番号がふられた人…
問題 No.210 探し物はどこですか？ - yukicoder 部屋が個あり，そのどこかにメガネがある． 番目の部屋にある確率がでその部屋を見た時に見つけられる確率がである． メガネを見つけるまでの部屋を見る回数の期待値を最小にする問題．解法 回目に番目の部屋…
問題 No.25 有限小数 - yukicoder 整数が与えられてが循環少数なら-1を有限少数なら0でない一番小さい桁の数を出力する問題．解法 まずを最大公約数で割って互いに素にする． を10で割り切れるなら10で割っておく． 次にが2の倍数ならに5をかけ，が5の倍数な…
問題 No.209 Longest Mountain Subsequence - yukicoder 個の整数が与えられる． を地形の高さだと考えた時に，の部分列から構成される山で，麓に近づくにつれて坂が緩やかになるような山の幅の最大値を求める問題．解法 ある地点を頂上だと考えた時にそこか…
問題 No.313 π - yukicoder 20万桁ある円周率のうち，一箇所だけ間違いがある． どの数字が間違っているか指摘する問題．解法1 （解法1では解けません） 円周率を20万桁まで計算して比較するという方法を取ろうとしてしまった． しかし5秒以内に計算するとな…
問題 No.165 四角で囲え！ - yukicoder 座標上に個の点があり，それぞれ点数が与えられている． を超えないように四角で囲った時最も多く囲える点の数を求める問題解法 座標圧縮と半分全列挙としゃくとり法を使う． まず，座標圧縮をする． 座標用のmapと座…
問題 No.356 円周上を回る3つの動点の一致 - yukicoder 円周上を3つの点が時計回りに移動している． それぞれ，秒で一周するとき， 同じ点から動き始める時，次に3点が一致するのは何秒後か．解法 秒後にが整数かつが整数ならば，3点が一致する． まずとの最…
問題 No.75 回数の期待値の問題 - yukicoder 1つのサイコロを繰り返し振り，出た目の合計をにする． もしを上回ったら合計を0にリセットする． サイコロの振る回数の期待値はいくらか．解法1 絶対誤差か相対誤差がに収まればいいので モンテカルロでも正解を…
問題 No.368 LCM of K-products - yukicoder 個の正整数からなる数列がある． の添字が異なる個の要素の積からなる集合をとした時， の全要素の最小公倍数をで割った余りを求める．解法 は素数)とした時， 最小公倍数は lcmとなる． ちなみに最大公約数は gc…
問題 No.367 ナイトの転身 - yukicoder のチェス盤が与えられ，ナイトとミニビショップを操作する． ミニビショップは斜めに１マスだけ移動できる駒である． ナイトでスタートし，赤いマスを通るとミニビショップになる． スタート地点，ゴール地点，赤いマ…
問題 No.366 ロボットソート - yukicoder 個の数字が並べられていて， との数字を入れ替えることができる． 昇順に並べ替えられる時はその操作回数を 並べ替えられない時はを出力するという問題．解法 添字に対してが等しくなる集合に分ける． それぞれをバ…
問題 No.365 ジェンガソート - yukicoder の数字がランダムに並べられている． １回の操作で数字を１つ選んで一番前に持ってくることができる． 数字を昇順に並び替えるための最小の操作の回数はいくつか．解法 最悪でも回の操作でソートが可能である． そこ…
問題 Problem - B - Codeforces 棒が本あり，それぞれの長さはである． それらを繋げても多角形を作ることが出来ない． 1本棒を加えるとき，多角形を作るために必要な最短の長さは幾つか．解法 の最大値をとした時， その他の棒を合わせてが得られれば多角形…
問題 Problem - A - Codeforces 直径cmの円筒があり，初めに高さcmだけ水が入っている． 毎秒mlで水を飲み，また雨によって毎秒cmだけ水かさが増すとき， 水を飲みきれるか，飲みきれるとしたら何秒かかるか．解法 が成り立つので ならば飲みきれ， が答えに…
問題 No.67 よくある棒を切る問題 (1) - yukicoder N本の棒がある． それらの棒を切ってK本の同じ長さの棒を取り出したいとき そのK本の棒の最大の長さは幾つか．解法 棒の長さの二分探索で解ける． 問題は誤差で，相対誤差または絶対誤差が以下ならよいので…
