ABC 017 D サプリメント

考えてもよくわからなくて解説を見ました. 見て理解した気になって脳死実装したものの, サンプル以外WA(!). なんでよ〜とかいいながらあちこちのブログを回ると, 自分の考察の穴がわかり, それを改善するとACできました. にしてもこれかなり難しいと思い…

Narcissu & Narcissu -SIDE 2nd- 感想とか

はじめに フリーゲームの『Narcissu 』および『 Narcissu -SIDE 2nd-』をやりました. 『Narcissu 』はこの執筆の3年前にプレイ済だったのですが, 淡路島に行く機会があったので, 無印, SIDE 2ndとリプレイとプレイをしました. とて…

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

問題 C - Cheating Nim 解法 まず, Nimなので与えられた数列のXOR和を考えます. Nimについておさらいしておくと, 山のXOR和が0のとき, 後手必勝 山のXOR和が0でないとき, 先手必勝 です. 山, 石が0のとき負けのこと, XOR和が0でないときは必ずXOR0の状態に遷…

AGC 028 B - Removing Blocks

問題 B - Removing Blocks 解法 まず, とても愚直な方法を試すと, おそらくの計算量になると思います(next_permutationを用いて取り出す順番を決め,(O(N!)), 一つ取り出すごとに隣接するブロックのコストを合算する計算(O(N))をO(N)回ほど繰り返すので.). 制…

座標圧縮を学んだ(情オリ2008 ペンキEを解きました)

問題から 問題 E: ペンキの色 - 第7回日本情報オリンピック 本選(オンライン) | AtCoder 解法 まず, 与えられる座標がグリッドマスの座標ではなく, 座標平面上の格子点の座標であることに注意しましょう. これをグリッドのマスに変換するためには, 長方形…

AtCoderのレートが水色になるまでにやったこと

水色になったので自分語りをしたくなりました. 自分にとってはそこそこの到達点なのでここでだけはいろいろ言わせてください(). はじめてのコンテストのおもひで 2018/06/16に初めてのコンテストは30分ぐらい遅れての参加だったことを覚えてます. Twitterや…

AGC 028 反省

Aのみの1完. 早ときかどうか微妙なタイムでしたが青パフォがとれ, 無事水色になることができました. Bもちょっと考えたんですけど, わからずじまい....とりあえず水色になった喜びも込めて, Aのみ書きます. A問題 問題 A - Two Abbreviations 解法 条件から,…

ABC 112 反省

全完しました. しかしC問題に時間をかけすぎてパフォは低め... A問題 問題 A - Programming Education 解法 なんかいつものA問題と少し違って驚き. 一個入力を受け取って, 場合分けをします. "Hello World"のつづりに注意します. 提出 Submission #3341710 -…

C++でNimをつくった

C++で某石取りゲームNimを作りました. Nimのコンパイラを作ったわけではありません... CPUと対決するようなものを作りました. 付録のソースコードをコンパイルしてお楽しみください. 開発環境の都合で表示がバグったりするかもしれないですが勘弁. 使い方 起…

ARC103 反省

CとDの部分点の1.5完. とれるところは全部とれたと思う. けど立ち回りがよくなかった. C問題 問題 C - /\/\/\/ 解法 偶数添字と奇数添字でグループ分けできる. それぞれで最も数が多い数字にするのが最善であるが, その数字が同じだったときの処理が面倒(最…

ABC 110 反省

ABDの3完. A問題 問題 A - Maximize the Formula 解法 条件から, どれか一個だけ10倍して足すことができるのと同値になる. よって, が答え. 提出 Submission #3249860 - AtCoder Beginner Contest 110 感想 Aにしてはちょっとむずかしい. B問題 問題 B - 1 D…

ABC 041-D 徒競走

問題 D - 徒競走 解法 のときの部分点はnext_permutationを使うと獲得できます. 満点解法では通りを考える必要があるので, 別の解法を考える必要があります. と, うさぎの集合を見るようにすると数が小さいです. これに着目して, bitDPを行うことを考えます.…

ABC 097 C - K-th Substring

問題 Submission #3184163 - AtCoder Beginner Contest 097 解法 連続している部分文字列の中で辞書順番目のものを求める問題です. 制約と, 『連続している部分文字列』というのがポイントで, 連続している文字()をすべて列挙し,ソートして重複を取り除いた…

ABC 098 D - Xor Sum 2

最近しゃくとり方を実装していなかったので解き直しました. 問題 D - Xor Sum 2 解法 問題を見るに, いかにもなしゃくとり法です. この問題を解くうえで, xor演算の重要な性質を用います. xor演算において以下の性質が成り立ちます. 1の性質は, この演算にお…

ABC 109 反省

久々にコンテスト中に全完できました. しかし, B問題でWAを連発してしまったため, 大きくペナルティを食らってしまったのは反省事項です. A問題 問題 A - ABC333 解法 を1~3まで試します. 提出 Submission #3151567 - AtCoder Beginner Contest 109 感想 素…

yukicoder No.420 mod2漸化式

最近はyukicoderの低難易度埋めてます. その中でもおもしろいと思ったものを書き留めます. 問題 No.420 mod2漸化式 - yukicoder 解法 まず漸化式 がそもそも何を表しているか考えます. ためしにいろいろ入れてみると, ... となります. のべきがとなっている…

ARC 102 C - Triangular Relationship

問題 C - Triangular Relationship 解法 コンテスト中は, ひたすらを固定しての数を数える方法を探していた. まず, 問題文を式に表してみると, を固定してみたときとりあえずは 表すことができる. また, より が成り立ちます. また, 条件から各について より…

SoundHound Programming Contest 2018 Masters Tournament 本線 B - Neutralize

問題 B - Neutralize 解法 貪欲ができないか考えます. ある薬品を0にしたいときはK個を巻き込む必要があります. また, 個以上の区間を0にしたいときはこれを繰り返すことで実現することができます. しかし, サンプルケースを見てみるとこれは厳しそうである…

No.672 最長AB列

問題 No.672 最長AB列 - yukicoder 解法 まず愚直解を考えます. 左端を決めて左から文字列を見ていき, A, B,の数を数えながら右に行き, AとBの数が同一になったら最大値を更新します. この解法はでTLEです. この解法を詰めていきましょう. まず,ABの数が同一…

yukicoder No.390 最長の数列

問題 No.390 最長の数列 - yukicoder 解法 DPをします. としておきます. 遷移は, です. 右のを固定して配るDPにすると, 計算量はなります. 左を固定すると約数の列挙にかかるためとなり, ギリギリ間に合います. 提出 #279345 No.390 最長の数列 - yukicoder …

No.462 6日知らずのコンピュータ

問題 No.462 6日知らずのコンピュータ - yukicoder 解法 まず, がであるときを考えます このとき, 〜 桁のビットまで, ビットを立てる順番の場合の数がそのまま場合の数になります. 一度立てたビットは元に戻さないため, これらの数列たちはすべて異なるもの…

yukicoder No.491 10^9+1と回文

問題 No.491 10^9+1と回文 - yukicoder 解答 の性質に着目します. にたとえば123456をかけると, になります. ほかの数値に対しても, 数値が左側と右側にコピーされているような感じになります. これに着目すると, が回文となる場合は, 回文を掛け算した場合…

yukicoder No.496 ワープクリスタル (給料日前編)

問題 No.496 ワープクリスタル (給料日前編) - yukicoder 解法 dpします. どんなdpかというと, です. まずこのdpテーブルにまで徒歩でいったときのコストを入れておきます. このdpテーブルに対し, ワープクリスタルを1つずつ使っていき, コストが小さくなる…

yukicoder No.314 ケンケンパ

問題 No.314 ケンケンパ - yukicoder 解法 ケンケンパの生成について, 3つの状態があります. パで終わっている 末尾にケンが1回連続で出現して終わっている 末尾にケンが2回連続で出現して終わっている 遷移しうる状態は 1 → 2 2 → 1 , 3 3 → 1 よりDPを組み…

ABC 076 D - AtCoder Express

問題 D - AtCoder Express 解法 まず, サンプルをみると速度・時刻が0.5刻みで決まっていきそうなことがわかるので, 時刻・速度ともに2倍に引き伸ばします. これで多少は考えやすくなります. 前方向から順に速度を決めていくと, 減速しきれない区間が現れた…

ABC 086 Checker

問題 D - Checker 解法 まず愚直な解法について考察します. この問題の1辺が大きさの市松模様について, まずどこかの黒い正方形の左下に座標を置きます. 市松模様は無限に続いているので, この黒い正方形について右に1から2K-1, 上に1から2K-1ずらしていけ…

yukicoder No.607 開通777年記念

問題 https://yukicoder.me/problems/no/607 解法 駅に到着するごとに条件を満たしているかを調べる必要があります. 駅に到着してからの人員の増減を配列に入れて管理し, その都度累積和を取り直します. までの累積和のなかで2つ選ぶと, その差分を見ればそ…

ABC 106 反省

A問題 問題 A: Garden - AtCoder Beginner Contest 106 | AtCoder 解法 道を端っこに移動させるとの面積になります. 提出 Submission #3027981 - AtCoder Beginner Contest 106 | AtCoder B問題 問題 B: 105 - AtCoder Beginner Contest 106 | AtCoder 解法 …

yukicoder No.523 LED

問題 No.523 LED - yukicoder 解法 LEDをポチポチする順番を順列にして考えてみると, 例えばN=3のとき, ①①②②③③の並べ方を数える問題になります. このとき, 同じ番号のものは区別せず, 場合の数はとなります. 一般のNに対して答えは次の式で表されることがわ…

Haskellでオートマトン

いろいろ昔作ったコードを漁っていると, 半年前に作ったオートマトンのコードがあったのでここに供養. 作成の動機 オートマトンの講義があって, その復習というのもあったと思いますが, Haskellの勉強が主だった思います. Haskellは代数構造を扱いやすいので…