はまやんはまやんはまやん

hamayanhamayan's blog

2020-02-01から1ヶ月間の記事一覧

Japan Tech News #006 2020/02/29

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest (20) kodai ♥⚓☠️さんはTwitterを使っています 「オタク、こういうの好きなんでしょ https://t.co/1euCbujoZ1」 / Twitter そうです。 競技プログラ…

てん vs. ほむ [yukicoder 999]

https://yukicoder.me/problems/no/999 解説 https://yukicoder.me/submissions/436467 ルールを整理してみると、最終的な選択は以下のようになる。 「ほ」はほむらちゃん、「て」はてんぷらくん。 ほてほてほて てほてほ このように、左をとるとほてと取れ…

Four Integers [yukicoder 998]

https://yukicoder.me/problems/no/998 解説 https://yukicoder.me/submissions/436454 連続する4つの整数にできるか判定することを、以下のように行う。 ABCDを昇順ソートしたときに、A+1=B, B+1=C, C+1=Dとなっていればいい。 昇順ソートするので、配列で…

注文の多い順列 [yukicoder 1001]

https://yukicoder.me/problems/no/1001 前提知識 動的計画法 解説 https://yukicoder.me/submissions/436553 難しい。 実装のため、数は全部0~N-1に直しておく。 考え方としては、挿入DPが近いかもしれない。 そっちを学んでから、以下解説を見るとわかり…

Point Add and Array Add [yukicoder 1000]

https://yukicoder.me/problems/no/1000 前提知識 遅延セグメントツリー(区間add, 1点取得) クエリ先読み 解説 https://yukicoder.me/submissions/436489 配列のある区間をコピーしてaddするようなデータ構造は持っていない。 どこから手を付けようか。 ま…

Japan Tech News #005 2020/02/27

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 競技プログラミング MIS.W冬合宿わくわく競プロ大会 メモ。来週の月曜夜から火曜夜(1d) ゆるふわ競技プログラミングオンサイト at FORCIA #3 writer料は初…

Japan Tech News #004 2020/02/24

hamayanhamayanがインターネットを巡回して得た情報まとめ。 "Japan"と言うには主語が大きすぎる。 Hottest Azure DevOps の Pipeline のハローワールドからビルド・単体テスト・デプロイ・スワップまで - かずきのBlog@hatena 有名人のかずきさんの記事 Pip…

安全素数まとめ

色々調べたまとめ。 安全素数とは pと2p+1がともに素数である場合の2p+1のこと 安全素数 - Wikipedia ちなみにこの時のpはソフィー・ジェルマン素数 ソフィー・ジェルマン素数 - Wikipedia ソフィー・ジェルマン素数、安全素数が無数に存在するかは未解決問題…

Tourism [Codeforces Round #623 (Div. 1, based on VK Cup 2019-2020 - Elimination Round, Engine) D]

https://codeforces.com/contest/1314/problem/D N頂点の有向の重み付き完全グラフがある。 始点を1として、丁度K回移動を繰り返す。 ある頂点を訪れてから奇数回の移動で同じ頂点に戻ることがないように移動を繰り返したとき、 終点が1となる移動の総コスト…

Modularness [AtCoder Beginner Contest 156 F]

https://atcoder.jp/contests/abc156/tasks/abc156_f 解説 https://atcoder.jp/contests/abc156/submissions/10318264 (104) AtCoder Beginner Contest 156 - YouTube 解説AC。 これを思いつくのは厳しい。かなり賢い考え方。 けれど、見たことのあるテクは…

Roaming [AtCoder Beginner Contest 156 E]

https://atcoder.jp/contests/abc156/tasks/abc156_e 前提知識 mod上での二項定理 解説 https://atcoder.jp/contests/abc156/submissions/10312260 どこから手を付ければよいか分からなかったかもしれない。 今回数えたい組み合わせは、手順ではなく最終的な…

Bouquet [AtCoder Beginner Contest 156 D]

https://atcoder.jp/contests/abc156/tasks/abc156_d 前提知識 mod素数上での計算(割り算) 繰り返し二乗法による累乗計算 解説 https://atcoder.jp/contests/abc156/submissions/10299907 本数制限がない場合を考えよう。 すると、N種類の花を使って作れる…

Rally [AtCoder Beginner Contest 156 C]

https://atcoder.jp/contests/abc156/tasks/abc156_c 解説 https://atcoder.jp/contests/abc156/submissions/10295562 集会を開く座標Pを全探索しよう。 座標Pの最小値が得られそうで、置ける部分は[1,100]になる。 これは、その範囲でのみ集会が行われるか…

Digits [AtCoder Beginner Contest 156 B]

https://atcoder.jp/contests/abc156/tasks/abc156_b 解説 https://atcoder.jp/contests/abc156/submissions/10295358 10進数をK進数に変換するには、Kで割っていき、あまりを書いていく方法がある。 ここでKで割る回数が丁度桁数になっている。 よって、Nを…

Beginner [AtCoder Beginner Contest 156 A]

https://atcoder.jp/contests/abc156/tasks/abc156_a 解説 https://atcoder.jp/contests/abc156/submissions/10295302 問題文に書かれていることをシミュレートする。 特に注意点はない。 int N, R; //----------------------------------------------------…

Japan Tech News #003 2020/02/22

Hottest 特になし 競技プログラミング Topcoder SRM 779 - Codeforces 問題文と制約が矛盾してて、Easy落とす人が続出する問題があったが、思ったより荒れてない ArraySorting [Single Round Match 779 Round 1 - Division I Level One] SubstringQueries [S…

Jumping Kangaroo [yukicoder 997]

https://yukicoder.me/problems/no/997 前提知識 行列累乗 解説 https://yukicoder.me/submissions/433408 Wの倍数で白石を踏んでいく必要がある。 例えば、白石を必ず踏んでいく必要がある場合は、白石間の組み合わせを計算して、K乗すれば答えが得られる。…

Phnom Penh [yukicoder 996]

https://yukicoder.me/problems/no/996 解説 https://yukicoder.me/submissions/433444 雰囲気で解こうとして、解ききれなかったので、解説AC。 何となく眺めると、 phnom→penh→phn となるので、操作1→操作2とやるとomが消える感じがする。 例をみると、omが…

タピオカオイシクナーレ [yukicoder 995]

https://yukicoder.me/problems/no/995 前提知識 行列累乗 解説 https://yukicoder.me/submissions/433443 各タピオカ同士は、互いに影響を及ぼさないので、独立に計算ができる。 各タピオカについて美しさの期待値を求め、その総和をとることで、答えを導こ…

ばらばらコイン [yukicoder 994]

https://yukicoder.me/problems/no/994 解説 https://yukicoder.me/submissions/433013 N頂点に最大個数コインを置くとN枚になる。 これ以上コインがあった場合は1枚ずつにすることはできない。 よって、N

青色 [yukicoder 993]

https://yukicoder.me/problems/no/993 解説 https://yukicoder.me/submissions/433373 パターンマッチングをして文字列を書き換える。 文字列長は短く、書き換え後に再書き換えの恐れがあるリスクもないので、 先頭からaoを探してkiに変えていこう。 string…

SubstringQueries [Single Round Match 779 Round 1 - Division I, Level Two Med]

https://community.topcoder.com/stat?c=problem_statement&pm=15740 前提知識 Suffix Array/LCP 解説 テクニックとして、ある文字列の任意の2区間の大小関係は前計算しておけば、O(1)で判定することができる。 Suffix Array/LCPでそれが実現できる。 これを…

ArraySorting [Single Round Match 779 Round 1 - Division I, Level One]

https://community.topcoder.com/stat?c=problem_statement&pm=15960 前提知識 LIS 解説 なるべく少ない個数の要素を修正して、辞書順最小の非減少列を作成するという問題。 構築の部分は後で考えるとして、修正すべき要素数を考える。 修正すべき個数の最小…

Admin [SarCTF]

https://ctftime.org/task/10485 前提知識 ブルートフォース攻撃 解説 Hintを見るとかなり難易度が下がる。 パスワードの再発行でSMS認証を使っていて、いかにも特殊な感じがする。 http://sherlock-message.ru/script.js コードで該当の場所を見てみると、…

Door paradox [SarCTF]

https://ctftime.org/task/10484 前提知識 MD5 解説 ソースコードをたどると、メインロジックにたどり着ける。 http://sherlock-message.ru/script.js ここから、POSTで/api/にメッセージを投げて色々な処理を行っている。 そこが隠蔽されていて見えない。 …

Japan Tech News #002 2020/02/19

Hottest エンジニア歴17年の俺が、事業系の開発タスクをバンバン投げてくる非エンジニアに、保守の必要性を死ぬほど分かりやすく説明する。|みやたけ|note これが読みたかった テスティングとかも徐々にやっていかないと、後々組み合わせが膨大になってく…

Japan Tech News #001 2020/02/17

Hottest 高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita 競プロ有名人のe869120さんの記事。研究の素材を見つける力がすごい 競技プログラミング 競技プログラマーにおすすめするセキュリティエンジニアというお仕事…

Perils in Parallel [AtCoder Beginner Contest 155 F]

https://atcoder.jp/contests/abc155/tasks/abc155_f 前提知識 座標圧縮 UnionFind 解説 https://atcoder.jp/contests/abc155/submissions/10167980 やっとAC。実装がきつい。 公式解説の副読解説です。 まずは、動画解説見ることをお勧めします。 最初にテ…

Payment [AtCoder Beginner Contest 155 E]

https://atcoder.jp/contests/abc155/tasks/abc155_e 前提知識 桁DP 解説 https://atcoder.jp/contests/abc155/submissions/10165143 2023/08/20更新 コードがWAのものになっていたのでACのものに修正。 Twitterで言及されてる方がいて気がつきましたが、だ…

Payment [AtCoder Beginner Contest 155 E]

https://atcoder.jp/contests/abc155/tasks/abc155_e 前提知識 桁DP 解説 https://atcoder.jp/contests/abc155/submissions/10147004 制約を見ると、桁DPでよくみる制約となっている。 桁DPで考えてみると、解ける。 だが、珍しい形で下の桁から更新していく…