buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

codevs reborn に参加しました

しました。 codevsとは codevs.jp ゲームAIを作って強い人が優勝。 tl;dr 結果 17/112位 ずっとシルバー(30位以内)をキープしていたようなしていなかったような*1。 前回参加した、codevs for student(以下codevsFS)は社会人含めて27~30位ぐらいだったので、…

Codingame Code a la Mode に参加した

結果 Legendary到達.38/1543.Legendary到達後はコード触ってない(触ると落ちそうだったので). 問題概要 客が常に3人居て,何か料理を注文している.適切な料理を出すと,スコアを獲得する. なるべく高いスコアを獲得したい. 料理は,皿と複数の食材か…

LeetCode - Subarrays with K Different Integers

解けなかった 問題 leetcode.com K種類の整数から構成される連続部分配列をgoodと呼ぶ. 入力から与えられる配列の連続部分配列のうち,goodな配列はいくつ存在するか?

NIKKEI Programming Contest 2019 - E Weights on Vertices and Edges

問題文 atcoder.jp 頂点重みX 辺重みY の無向グラフが与えられる. 次の条件を満たすように,なるべく少ない辺を削除したい. 削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。

Code Festival Team Relay (Parallel) - D 数直線

雑でごめんなさい 問題 cf18-relay-open.contest.atcoder.jp 数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。 次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が…

COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――

この程度の愚直DPが間違ってたのダメ 問題文 beta.atcoder.jp スタミナとよばれる概念があり,0で空,Xで満タンである.時刻1単位でスタミナは1回復する 時刻0にてスタミナはXである T_1..T_NからK個のタイミングを選んで,スタミナを0にして,スタミナを減…

ハル研究所プログラミングコンテスト2018に参加しました

ハル研究所プログラミングコンテスト2018とは www.hallab.co.jp 自分にとっては 2度め. 2019年卒なので,今回が最後. 今年の成果 16位.食べられないクッキー獲得! 例年より参加者数が多いらしい. 問題概要 20x20のオーブンと,2つのレーン(SmallLane,La…

yukicoder No.741 AscNumber(Easy)

問題概要 0~9で構成されるN文字の文字列のうち、桁が昇順になるものはいくつか?

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

解説ACしてから理解しようとしたら辛かった https://yukicoder.me/problems/no/75 https://yukicoder.me/submissions/285676 問題概要 さいころを振って,でた目を累積する.これを1手とする. 累積値がKになったら終了.超えたら0にリセットする. 手数の期…

定数倍高速化

アルゴリズムとはほぼ無関係. スタート地点 遅いコード 2797 ms Submission #3108991 - AtCoder Regular Contest 025 namespace Twoを修正します. 一番早いantaさんを見て絶対届かないと思いました.

AtCoder Regular Contest 027 - D ぴょんぴょんトレーニング

解説とは違う方法なので 問題 N個の石があって,i番目の石はi+1..i+H\[i\]にジャンプ出来る. 次のD個のクエリに答えたい:s番目の石からt番目の石へ移動する方法の数を答えよ. キーワード 行列演算表現を用いた動的計画法 行列が乗ったセグメントツリー

データアクセスに制限のある Binary Indexed Tree () の高速化

タイトルについて 正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です Binary Indexed Tree とは 以下のクエリに時間O(logN)で答えることが出来るデータ構造. 初期化 サイズNの配列の要素を0に初…

AtCoder Regular Contest 061 - E すぬけ君の地下鉄旅行 / Snuke's Subway Trip

解説と若干違っていたので 概要 https://beta.atcoder.jp/contests/arc061/tasks/arc061_c 鉄道会社の乗り換えを最小化せよ かなり雑なブログ記事です

AtCoder Grand Contest 026 - B rng_10s

解説を軽く読んだだけでは理解できない脳なので記事書いた. 問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_b 昼:客のsnukeさんがジュースをB個買う 夜:rngさんが在庫を確認し,C個以下なら翌日朝までにジュースをD個仕入れる ある日の朝,…

AtCoder Regular Contest 091 - E LISDL

本番の時は N = A+B or N+1=A+B で考察してWAでした. 問題文 最長増加部分列の長さがA,最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ. 提出 Submission #2751681 - AtCoder Regular Contest 091 解説を殆ど*1見ずにACした. *1:…

AtCoder Chokudai Contest 001 高橋君の山崩しゲーム

参加はしていましたが,改めて解いてみた. 問題概要 30x30のグリッドがあり,各マスに自然数が書き込まれている.次の一連の流れを1手とする.手数を最小化せよ. 1つのマスを選ぶ デクリメントする. 4近傍のうち,デクリメント後のマスの数と一致したマ…

codingame: Code of Kutulu 参加記録

問題概要 KutuluのMinionの攻撃を回避して最後の1人になることが目標. sanity(SAN)の減少 何もしなくても勝手に下がる.近くに味方が居ると下がりにくくなる. Minionの攻撃を受けると-20. 手段 敵を遠ざけるLight*1 周囲の味方を回復するPlan 一度だけ周…

stick xor 余談

作文に関する余談など.有用な解説についてはyukicoderの解説ページを参照してください.

変更履歴を保存するデータ構造に関するメモ(定義とか)

永続データ構造とは 永続データ構造 - Wikipedia 変更履歴(バージョン)を記録するデータ構造. 本記事について 永続データ構造の性質について取り上げたい.

AtCoder Petrozavodsk Contest 001 - D Forest

嘘解法かもしれないので程々に. 2つのコーナーケースを記事に載せたのでぜひ. 問題文 https://beta.atcoder.jp/contests/apc001/tasks/apc001_d 公式想定解法 考察すると次が分かる 各連結成分のうち,必ず使わなければならない頂点は 1 個 全て合わせて2(…

yukicoder No.629 グラフの中に眠る門松列

2018/02/24 表現を修正 writerしました 問題 https://yukicoder.me/problems/no/629 ざっくり説明:グラフと頂点に割り当てる数字が与えられる.門松パスは存在するか? 本記事の目的 グラフに含まれる,門松パスの個数を O(M) で求める. cielさんの提出コ…

AtCoder Grand Contest 002 - D Stamp Rally

勉強になるとTLで見かけたので 問題 agc002.contest.atcoder.jp キーワード 並列二分探索

平面 traveling salesman problem の厳密解を求める.

平面tspの分岐限定法のコードをなんとなく書いてみたけれども,全然早くならなかった. Traveling Salesman Problem (TSP) N個の都市と都市間の距離が与えられる.全ての都市をちょうど一度ずつ巡って始点に戻る順回路の中で移動距離が最小のものを出力する…

Kの重複を許す区間スケジューリング問題

2018/02/22 更新 文章を修正 区間スケジューリング問題 http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用. 区間スケジューリングは次の問題である.仕事が n 個与えられる.各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定さ…

Kuin で 競技プログラミング(yukicoder No.4 おもりと天秤) の問題を解く

2019/02/15 追記: コードが動かなくなっていたので,書き直しました. #316677 No.4 おもりと天秤 - yukicoder math@knapsackを使ったバージョンも載せます. #316679 No.4 おもりと天秤 - yukicoder Kuinとは? プログラミング言語「Kuin」 「Kuin」は、簡…

AtCoder Regular Contest 028 - B 特別賞

別解法シリーズ.別解で通すのは楽しいよ. 問題 arc028.contest.atcoder.jp

AtCoder Regular Contest 044 - C ビーム

少しだけヒントを見てしまったが,面白かったので解説を書く. arc044.contest.atcoder.jp 概要 レーザを避けるために必要な最小移動距離を求めよ.

yukicoder No.550 夏休みの思い出(1)

想定解とは違うけれども大丈夫そうなので解説を書いてしまった. 問題概要 No.550 夏休みの思い出(1) - yukicoder 三次方程式を解け. 解は整数であることが分かっている. submission #192857 No.550 夏休みの思い出(1) - yukicoder

yukicoder No.545 ママの大事な二人の子供

問題はこちら. - No.545 ママの大事な二人の子供 - yukicoder コンテスト中に半分全列挙のアルゴリズムを調べ,書きなぐってAccept通したので,その考え方を書きます. 問題文 個のアイテムがある. 番目のアイテムをA君に渡すとA君はポイント喜ぶ. 番目の…

scheme / commonLispで解く競技プログラミング (1)

lispをもう少しだけ詳しくなりたかった. Lispってなに? とても古い言語 C言語と比べてとてもシンプルな言語. emacsLispとかで息してる言語. Lisp言語を選ぶメリット ないと思います. オレオレ言語を作りたいとき,Lispライクな言語設計にすると,とても…