読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

CTF for ビギナーズ Writeup & 参加記

ctf

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で何かしようということで,競プロのAC数を数えてみたいと思います. 環境 Amazon Dash Button Python 2.7.13(scapy,requests_oauthlib) ボタンが押されたことを検知 ボタンが押されたことを検知できないと何も始まらないので…

yukicoder No.429 CupShuffle

問題 No.429 CupShuffle - yukicoder N個のコップについて交換の仕方・最終配置が与えられる.ただし,X回目の交換の仕方の情報が抜けている.どのコップを交換したかを求める問題. 解法 解説を見るとX-1回目までswapを行い,一方K回目からX+1回目まで逆順…

CODE FESTIVAL 2016 qual B E - Lexicographical disorder

問題 E: Lexicographical disorder - CODE FESTIVAL 2016 qual B | AtCoder N個の文字列Siが与えられる.以下のクエリにQ回答える問題 整数kと{'a',...,'z'}を並び替えたp1,...,p26が与えられる.文字の順序がp1&ltp2<...&ltp26の時SkはN個の文字列の中で何…

yukicoder No.416 旅行会社

問題 No.416 旅行会社 - yukicoder N個の点とM本の辺が与えられ,CiとDiの間の辺を壊すというクエリがQ個与えられる.それぞれの点は何回目のクエリで点1から到達できなくなるか答える問題. 解法 辺を繋いで(この問題では壊して)ある点から到達できるかを…

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

問題 Problem - D - Codeforces 3つのクエリに答える. 1. xをmultiset Aに加える 2. xをmultiset Aから取り除く 3. を出力する 解法1 c++のmultisetを使って二分探索をする. xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい.xを反転…

Codeforces Round #365 (Div. 2) C. Chris and Road

問題 Problem - C - Codeforces N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題 解法 バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く…

AtCoder Grand Contest 002 D - Stamp Rally

問題 D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder N頂点,M辺からなるグラフがあり,Q組の兄弟がスタンプラリーを行う.i番目の兄弟はそれぞれXi,Yiにいて合わせてZiのスタンプを集めたいと思っている.通ることになる辺の最大の番号を最小にす…

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

トポロジカルソートを初めて書いた気がするので記事に残そうと思う 問題 C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder 文字列Ai,BiがN個ずつ与えられる.Ai 解法 トポロジカルソートを使う.AiとBiを左の文字から比較して初めて異な…

Codeforces Round #363 (Div. 2) E. LRU

問題 Problem - E - Codeforces N個のデータと容量Kのキャッシュがある.キャッシュのアルゴリズムにLRUが使われていて,無限のクエリが飛んできたとき,最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか. 解法 簡単に言うと,キャッシュ…

yukicoder No.23 技の選択

問題 No.23 技の選択 - yukicoder 体力がの敵を 攻撃力の通常攻撃(必ず当たる) 攻撃力の必殺技(2/3の確率で当たる) の二つの攻撃を使って倒したい.最小の攻撃回数の期待値はいくつか. 解法 解説を見たら全部DPで解いていたが,通常攻撃の使う回数でル…

CodeChef July Challenge 2016 Chef and Rectangle Array

問題 https://www.codechef.com/problems/CHSQARR の行列が与えられる.個のクエリに対して以下の操作を行う. が与えられての範囲の数がすべて等しくなるように行列の要素の数字を増やすとき,増やす数の最小値を出力する 解法 範囲の和と範囲の最大値を使…

問題を見てまず考えること

問題を見て,まず考えるべきことを問題の種類別にまとめていく. これから追加していくつもり.また,当たり前になってきたものは消していくかも. クエリ クエリを先読みしてソートしたりする 勝ち負けゲーム 対称性を作れないか 探索系 一度全探索の解法を…

yukicoder No.103 素因数ゲーム リターンズ

問題 No.103 素因数ゲーム リターンズ - yukicoder 個の整数が与えられる. 一度の操作で任意の整数をその素因数で割ることができる.同じ素因数ならば2回まで同時に割れる. AliceとBobが交互に操作を行うとき,すべての整数をにできるのはどちらか.解法 …

Codeforces Round #355 (Div. 2) D. Vanya and Treasure

問題 Problem - D - Codeforces の部屋があり,それぞれ宝箱が置いてある.タイプの宝箱にはタイプの宝箱を開ける鍵が入っている.タイプの宝箱を開けるまでに移動する最小距離はいくつか.解法 単純にタイプごとにダイクストラを行っていたら間に合わない.…

yukicoder No.318 学学学学学

問題 No.318 学学学学学 - yukicoder 数列が与えられる.からについて順番に,同じ数で挟まれた数をで置き換える.書き換えられた後の数列を出力する問題.解法 双方向リストを使う.大きい数から順番に以下の操作を行う. 一番左のが,一番右のがとすると,…

vimでテンプレート読み込み

vim

テンプレートの読み込みはcppの場合、 autocmd BufNewFile *.cpp 0read $VIM/template/template.cpp とするのが普通だと思う。 しかしこの方法では、touchや>で作ったファイルやwindowsの新規作成で作ったファイルなどを編集する時に読み込みがされない。そ…

Codeforces Round #353 (Div. 2) C. Money Transfers

問題 Problem - C - Codeforces 行の銀行が円周上に並んでいる.隣の銀行に送金することが可能になっている.Aさんがそれぞれの銀行に口座を持っていて,お金を預けている(または借りている).預けているお金を隣の銀行に送金することを繰り返し,すべての…

Codeforces Round #352 (Div. 2) B. Different is Good

問題 Problem - B - Codeforces 文字列が与えられる.どの部分列をとっても同じ文字列が現れないように与えられた文字列を書き換えるとき,書き換える最小の文字数は幾つか.解法 部分列は1文字だけ考えればよい.つまり,すべて違う文字になるように書き換…

Codeforces Round #352 (Div. 2) A. Summer Camp

問題 Problem - A - Codeforces 123456789101112...といったように数字を1から並べた列がある.番目にくる数字は幾つか.解法 1から順に数字をstringに積んでいき,番目にきた数字を出力する.ソースコード #include <iostream> #include <vector> #include <algorithm> using namespace s</algorithm></vector></iostream>…

yukicoder No.174 カードゲーム(Hard)

問題 No.174 カードゲーム(Hard) - yukicoder A君とB君がカードでゲームを行う.1から1000までの数字が書かれたカードがあり,その中から枚ずつ配られる.試合は回あり,試合ごとにプレイヤーがカードを出していき,大きい数字を出したほうがその数字…

Codeforces Round #350 (Div. 2) F. Restore a Number

問題 Problem - F - Codeforces AさんはBさんにある数字にその数字の長さを右に付け足して送った.しかし,送られる途中で文字の順番がバラバラになってしまった.Aさんはその数字の部分列を覚えている.送った可能性のある数字の内,その部分列を含むような…

Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

問題 Problem - E - Codeforces 対応する括弧が存在する括弧の列が与えられる.カーソルの初期位置と R : カーソルを右にずらす L : カーソルを左にずらす D : 今見ている括弧と対応する括弧の間の括弧を消して右に移動する という操作の列が与えられた時,…

Codeforces Round #350 (Div. 2) D1,D2. Magic Powder

問題 Problem - D1 - Codeforces クッキーを作ろうとしている.1つ作るのに種類の材料がずつ必要である.初めにずつ持っているとする.また,のマジックパウダーも持っており,そのパウダーはどの材料にも変えることができる.作れるクッキーの最大値はいく…

Codeforces Round #350 (Div. 2) C. Cinema

問題 Problem - C - Codeforces 人の人がいる.それぞれ使える言語は1つだけである.個の映画があり,音声と字幕は違う言語が使われている.1つの映画を全員で見るとき最も多くの人が満足できる映画はどれか. 音声に満足している人が等しいならば字幕で比…

Codeforces Round #350 (Div. 2) B. Game of Robots

問題 Problem - B - Codeforces ロボットが体いる.それぞれのロボットに番号が付けられている. 左のロボットから順番に,「ロボットの番号を一番左のロボットの番号から自分の番号まで言う」ことを行うとき,回目に言われるロボットの番号は幾つか.制約 …

Codeforces Round #350 (Div. 2) A. Holidays

問題 Problem - A - Codeforces 火星では1年が日続く.また,地球と同じように1週間は平日が5日,休日が2日ある. 1年の休日の数の最大値と最小値はいくつか.解法 7で割り,最大値を求めるときは余りに対してできるだけ休日から割り当て,最小値を求…

yukicoder No.241 出席番号(1)

問題 No.241 出席番号(1) - yukicoder 人の生徒がいて,それぞれ出席番号を割り振る. 1人1つ割り当てられたくない数字があるのでそれを避けるような割り振り方を1つ出力する問題.解法 2部マッチングで解く. 生徒から割り振ることのできる番号へ結び,…

yukicoder No.132 点と平面との距離

問題 No.132 点と平面との距離 - yukicoder 3次元上の点と個の点が与えられる. をから点を通る平面への距離とした時, を求める問題.解法 ベクトル,ベクトル,ベクトルに囲まれた三角錐の体積を求め,三角形の面積で割って3をかけることで,高さつまり…

yukicoder No.335 門松宝くじ

問題 No.335 門松宝くじ - yukicoder 宝くじが2枚か3枚与えられ,それぞれ数字が個書かれている. 当選日になると1つの宝くじにつきランダムに2つの数字が選ばれる.1つ数字を自由に選ぶことができ,その3つの数字で門松列が出来れば3つの数字の最大…

Topcoder SRM 690 Div 2 Hard WolfHockeyTeamEasy

解くのに10時間ほどかかった... 問題 TopCoder Statistics - Problem Statement 人が横に2列になって写真を撮る.それぞれの人はからまで番号がふられている. この時の並びは"nice"かつ"different"でなくてはいけない."nice"とは,以上の番号がふられた人…

yukicoder No.210 探し物はどこですか?

問題 No.210 探し物はどこですか? - yukicoder 部屋が個あり,そのどこかにメガネがある. 番目の部屋にある確率がでその部屋を見た時に見つけられる確率がである. メガネを見つけるまでの部屋を見る回数の期待値を最小にする問題.解法 回目に番目の部屋…

yukicoder No.25 有限小数

問題 No.25 有限小数 - yukicoder 整数が与えられてが循環少数なら-1を有限少数なら0でない一番小さい桁の数を出力する問題.解法 まずを最大公約数で割って互いに素にする. を10で割り切れるなら10で割っておく. 次にが2の倍数ならに5をかけ,が5の倍数な…

yukicoder No.209 Longest Mountain Subsequence

問題 No.209 Longest Mountain Subsequence - yukicoder 個の整数が与えられる. を地形の高さだと考えた時に,の部分列から構成される山で,麓に近づくにつれて坂が緩やかになるような山の幅の最大値を求める問題.解法 ある地点を頂上だと考えた時にそこか…

yukicoder No.313 π

問題 No.313 π - yukicoder 20万桁ある円周率のうち,一箇所だけ間違いがある. どの数字が間違っているか指摘する問題.解法1 (解法1では解けません) 円周率を20万桁まで計算して比較するという方法を取ろうとしてしまった. しかし5秒以内に計算するとな…

yukicoder No.165 四角で囲え!

問題 No.165 四角で囲え! - yukicoder 座標上に個の点があり,それぞれ点数が与えられている. を超えないように四角で囲った時最も多く囲える点の数を求める問題解法 座標圧縮と半分全列挙としゃくとり法を使う. まず,座標圧縮をする. 座標用のmapと座…

yukicoder No.356 円周上を回る3つの動点の一致

問題 No.356 円周上を回る3つの動点の一致 - yukicoder 円周上を3つの点が時計回りに移動している. それぞれ,秒で一周するとき, 同じ点から動き始める時,次に3点が一致するのは何秒後か.解法 秒後にが整数かつが整数ならば,3点が一致する. まずとの最…

yukicoder No.75 回数の期待値の問題

問題 No.75 回数の期待値の問題 - yukicoder 1つのサイコロを繰り返し振り,出た目の合計をにする. もしを上回ったら合計を0にリセットする. サイコロの振る回数の期待値はいくらか.解法1 絶対誤差か相対誤差がに収まればいいので モンテカルロでも正解を…

yukicoder No.368 LCM of K-products

問題 No.368 LCM of K-products - yukicoder 個の正整数からなる数列がある. の添字が異なる個の要素の積からなる集合をとした時, の全要素の最小公倍数をで割った余りを求める.解法 は素数)とした時, 最小公倍数は lcmとなる. ちなみに最大公約数は gc…

yukicoder No.367 ナイトの転身

問題 No.367 ナイトの転身 - yukicoder のチェス盤が与えられ,ナイトとミニビショップを操作する. ミニビショップは斜めに1マスだけ移動できる駒である. ナイトでスタートし,赤いマスを通るとミニビショップになる. スタート地点,ゴール地点,赤いマ…

yukicoder No.366 ロボットソート

問題 No.366 ロボットソート - yukicoder 個の数字が並べられていて, との数字を入れ替えることができる. 昇順に並べ替えられる時はその操作回数を 並べ替えられない時はを出力するという問題.解法 添字に対してが等しくなる集合に分ける. それぞれをバ…

yukicoder No.365 ジェンガソート

問題 No.365 ジェンガソート - yukicoder の数字がランダムに並べられている. 1回の操作で数字を1つ選んで一番前に持ってくることができる. 数字を昇順に並び替えるための最小の操作の回数はいくつか.解法 最悪でも回の操作でソートが可能である. そこ…

Codeforces Round #349 (Div. 2) B. Coat of Anticubism

問題 Problem - B - Codeforces 棒が本あり,それぞれの長さはである. それらを繋げても多角形を作ることが出来ない. 1本棒を加えるとき,多角形を作るために必要な最短の長さは幾つか.解法 の最大値をとした時, その他の棒を合わせてが得られれば多角形…

Codeforces Round #349 (Div. 2) A. Pouring Rain

問題 Problem - A - Codeforces 直径cmの円筒があり,初めに高さcmだけ水が入っている. 毎秒mlで水を飲み,また雨によって毎秒cmだけ水かさが増すとき, 水を飲みきれるか,飲みきれるとしたら何秒かかるか.解法 が成り立つので ならば飲みきれ, が答えに…

yukicoder No.67 よくある棒を切る問題 (1)

問題 No.67 よくある棒を切る問題 (1) - yukicoder N本の棒がある. それらの棒を切ってK本の同じ長さの棒を取り出したいとき そのK本の棒の最大の長さは幾つか.解法 棒の長さの二分探索で解ける. 問題は誤差で,相対誤差または絶対誤差が以下ならよいので…

yukicoder No.38 赤青白ブロック

問題 No.38 赤青白ブロック - yukicoder 赤,青,白の各10個のブロックがあり,一列に並べられている. すべてのブロックに対して 赤の左右Kr個離れた位置に赤がない 青の左右Kb個離れた位置に青がない を満たすように赤と青のブロックを抜くときの最大のブ…

yukicoder No.199 星を描こう

問題 No.199 星を描こう - yukicoder XY座標上の点が5つ与えられる.点を線で繋いで星が描けるかどうかを判定する.解法1 それぞれの頂点を結ぶ線分をすべて考えて, 他の線分と交わる回数が2回のものが5つあれば星を描ける(端は数えません). 交点の求…

POJ 2932 Coneology

問題 2932 -- Coneology 平面上に円がN個あり,それらが交わることはない. どの円にも囲まれていない円はいくつあるか.解法 x座標の小さい方から走査していく. 走査する直線が円の左端にぶつかった時,その円が他の円に含まれているか調べる. この時,調…