ミーハーなので新海誠映画の『天気の子』を見てきました。 前情報で、監督自身が賛否両論のある映画にしたよといっていたり、Twitterでも 「俺達の新海誠が帰ってきた～😂」などと新海オタクがつぶやいていたのを含みながら鑑賞しました。 以下ネタバレありで

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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