buyoh.hateblo.jp

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

AtCoder Grand Contest 026 - B rng_10s

解説を軽く読んだだけでは理解できない脳なので記事書いた.

問題

https://beta.atcoder.jp/contests/agc026/tasks/agc026_b

  • 昼:客のsnukeさんがジュースをB個買う
  • 夜:rngさんが在庫を確認し,C個以下なら翌日朝までにジュースをD個仕入れる

ある日の朝,ジュースの在庫はA個だった.snukeさんは永遠にジュースを買い続けられるか?

続きを読む

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. 1つのマスを選ぶ
  2. デクリメントする.
  3. 4近傍のうち,デクリメント後のマスの数と一致したマスがあれば,そのマスを改めて選び,ステップ2に戻ることができる.

補足

リンク付けはされていないが,公式解説がある.

https://www.slideshare.net/chokudai/chokudai001

続きを読む

codingame: Code of Kutulu 参加記録

問題概要

KutuluのMinionの攻撃を回避して最後の1人になることが目標.

sanity(SAN)の減少

  • 何もしなくても勝手に下がる.近くに味方が居ると下がりにくくなる.
  • Minionの攻撃を受けると-20.

手段

  • 敵を遠ざけるLight*1
  • 周囲の味方を回復するPlan
  • 一度だけ周囲の敵を騙すYell

戦績

今回は打ち込める時間があったためか,初Legendary.33/2092位.

前半,仕様が滅茶苦茶だったのでやり込む人少ないかなとは思いましたが,そんなことは無かった.

*1:遠ざからないこともある.Lightは最短のプレイヤーを探すためのテーブルのみに影響がある.Minionは常に最短経路を移動する.

続きを読む

最小頂点被覆問題(minimum Vertex Cover)の近似アルゴリズムの実装(draft)

1年前に同様のタイトルで記事を書きましたが,書き直します.

最小頂点被覆問題?

辺集合E,頂点集合Vから成るグラフGが与えられる.
頂点集合S⊆Vを考える.
全ての辺e∈Eが,Sに含まれる頂点に接続している時,SはグラフGの頂点被覆と呼ぶ.

集合Sの大きさが最小であるようなグラフGの頂点被覆Sを1つ求めてください.

頂点集合に重みw:V \rightarrow \mathbb{Q}^+が割り当てられている場合があります. この場合,\sum_{v \in S}w(v)を最小化します.

また,この記事では,『与えられたグラフは単純グラフである』と仮定します.

続きを読む

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

永続データ構造とは

永続データ構造 - Wikipedia

  • 変更履歴(バージョン)を記録するデータ構造.

本記事について

  • 永続データ構造の性質について取り上げたい.
続きを読む