2023-07-13

ABC209-E Shiritori

問題概要
制約
ゲームの言い換え
言い換えたゲームを観察する
この解析には名前がついている
提出コード

問題概要

https://atcoder.jp/contests/abc209/tasks/abc209_e

$N$ 個の文字列 $S_{i}$ が与えられる。高橋くんと青木くんが以下のルールの元しりとりをする

高橋君が先手で、交互に文字列を言う
与えられた文字列のいずれかと一致する文字列しか言うことができない
言う文字列のPrefix3文字は前の人が言った文字列のSuffix3文字と一致していなければいけない
すでに言われている文字列でも言うことができる

高橋くんが初手で $S_{i}$ を言ったあと両者が最適に行動する時、どちらが勝つかまたはしりとりが永遠に終わらないか判定しなさい。 $i = 0, 1, 2, \dots, N$ についてこれを解きなさい。

制約

$1\ \le\ N\ \le\ 2\times 10^{5}$
与える各文字列の長さは $3$ 以上 $8$ 以下

2023-07-10

ABC168-E ・(Bullet)

考察を楽しめました。

問題概要
- 制約
考察
- の時
- の時
- 解法
提出コード

問題概要

https://atcoder.jp/contests/abc168/tasks/abc168_e

$N$ 要素の整数の２つ組の列 $( (A_{1}, B_{1})\, (A_{2}, B_{2})\, \dots\, (A_{N}\, B_{N}) )$ を与えます*1。列から一つ以上の要素を選び出す方法で、どの選んだ2要素 $(A_{i}, B_{i}),\ (A_{j}\, B_{j})$ についても $A_{i}\cdot A_{j} + B_{i}\cdot B_{j}\ne 0$ を満たすようなものの通り数を $10^{9} + 7$ で割ったあまりを出力してください。

制約

$1\le N\le 2\times 10^{5}$
$\mid A_{i}\mid \, \mid B_{i}\mid\le 10^{18}$

*1:外側の括弧と内側の括弧の間にスペースを入れることで脚注と認識させないテク。はてなブログ典型90ですか？

2023-07-05

模擬国内2016bD 夏合宿の朝は早い (AOJ2748)

解法わかった時びっくりしたので書きます

問題概要
- 制約
解法
- 誰も他人の連絡先を知らない場合
- 電話が発生する時の観察
- 例外、サイクル
結論
提出コード
感想

問題概要

https://onlinejudge.u-aizu.ac.jp/problems/2748

$N$ 人について、朝寝坊する確率 $P_{i}$ を与えられる。各人はそれぞれ何人かの連絡先を知っており、寝坊せずに起きることができたなら連絡先全員に電話して起こすことができる(起こされた人は寝坊せずに起きたことになるので、またその人も連絡先全員に電話をする)

全員が寝坊しない確率を求めてください

制約

$1\ \le\ N\ \le\ 100$

2023-07-03

模擬国内2010D Mr. リトー郵便局 (AOJ2200)

解けてうれしかったので書きました。新規性は無いです。

問題概要
- 制約
TLE解
高速化
提出コード
感想

問題概要

onlinejudge.u-aizu.ac.jp

$N$ 頂点 $M$ 辺の無向グラフがある。無向グラフの各辺は「陸路」か「海路」であり、海路である辺は船が無いと利用することができない。陸路はそのような制限は無いが、船をもっている状態で陸路を移動する場合、船は移動前の頂点に置いていくことになる。それぞれの辺には非負整数の重みがある。

$R$ 要素の数列 $Z$ を与える。あなたは一隻船をもった状態で頂点 $Z_1$ にいる。船はこれ以外に存在しない。この状態から $Z_2, Z_3, \dots, Z_R$ をこの順に含むような移動の方法で(連続で含んでいる必要は無い)、通った辺の重みの最小値を求めよ。

制約

$2\ \le\ N\ \le\ 200$
$1\ \le\ M\ \le\ 10^{4}$
$1\ \le\ R\ \le\ 10^{3}$
それぞれの辺のコストは $1$ 以上 $10^{3}$ 以下
条件を満たす( $Z$ を部分列に含む)移動の方法が存在する
多重辺が存在するかもしれない。
入力は複数のテストケースで構成される
メモリ制限: $131072$ KB
TL: $8$ sec

2023-05-21

AtCoderで入青しました。記録や雑談です。

来たわよ！ pic.twitter.com/klRkf3JWHO
— カスタネット (@zawakasu) 2023年5月13日

zawatinさんのパナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）での成績：112位
パフォーマンス：2400相当
レーティング：1532→1655 (+123) :)
Highestを更新し、2 級になりました！#AtCoder #パナソニックグループプログラミングコンテスト2023（ABC301）
— カスタネット (@zawakasu) 2023年5月13日

初カンスト + 最高順位更新を達成しながら正の色変をしました。嬉しい限りです。

入水記事はこちら

記録画像

自分のスペックは

大学: 情報系の学部:B3
プログラミング・コンピュータ: 大学はじめ(3年目)
タイピング: 寿司打高級コースで平均1万3000円(+3000円)
競プロで使えるかもしれない(ABC-BCDくらいを通せる)レベルに習得している言語はC、C++のみ
- Python、Luaもできるかもしれない
- 最近はLua、Kotlinを勉強している
エディタはVim。補完機能/スニペットプラグインは使用していない
数学力: 高校数学の教科書に乗っているような問題が解ける程度

です。一つの目安として見てもらえたら幸いです。

AtCoder Archivement

ABC埋まり状況

キーボードを変更する機会があったのですが、その際にタイピング練習目的でAを全埋めしました。

ARC、AGC埋まり状況

ACするまで解説を開かないことが多いので、難易度が高いARCやAGCはなかなか埋まりません。

Difficulty別埋まり状況

入水時から

緑diff: +70問
水diff: +100問
青diff: +110問
黃diff: +15問

解きました。入青した現在でも黃色diffの問題は難しく感じています、ABCでもなかなか解けないです。

典型コンテスト埋まり状況

典型90: 星3、4制覇。星5が一問残り。星6はちょこっと解きました

数ヶ月放置した後に一気に5 ~ 10問解くと実力が向上している様に感じられて良い

EDPC: W, X, Y以外を解きました。

TDPC: あまり埋まってないです

他コンテストサイト

Codeforces

平日は週4で一限が入ってしまい、なかなか参加できないです。

AOJ

yukiocder, Topcoder等

は殆ど問題を解いてないので割愛します

合計2500問届かないくらいですね。入水してからは大体1000問解いていました。

精進で意識していること

こんなトピック作っといてなんですが、あまり無いです。

解説はACするまで見ない
自分や他人のライブラリで実装をサボる方針がないかを考える
何が理解できていて、何が理解できていなかったか(未証明な解法をしていないか)を確認するためにACした問題は解説等を書く
- 自分はScrapboxに書いています*1

くらいです。

コンテスト中に意識していること

こんなトピック作っといてなんですが、あまり無いです。

制約メタを張る
- 頼りすぎるのはダメだと思います。が、ABCだとまぁメタがあたるあたる。
順位表を監視する
- EFよりGが解かれているのにEFを粘るのはかなり渋い

くらいです

競プロ関係でおすすめしたいこと

こんなトピック作っといてなんですが、あまり無いです。

標準入力、標準出力はスニペット/ライブラリを用意する
- 自分はout(A)とするとAというvectorが出力されるような関数を用意しています。これ用意してから世界変わった
Makefileを用意して、makeコマンドでソースコードをコンパイルする
- コンパイルオプションとか毎回書いてると辛い
無理にRatedにしない
- TwitterとかだとRatedで参加しないやつはカス！みたいな主張が多いですが、別にそんなこと無いと思います。
- 体調が悪い日、気分が乗らない日等は普通にUnratedでも良いと思います。

くらいです

雑談

ICPC

戦犯しそうで既に震えている

AOJ-ICPC、実装はどの問題も重いし、難易度400超えた当たりから考察面でも長時間詰まってしまう。

競プロ以外の活動

ゲーム制作サークルでゲームを作ったりしています(Siv3Dたのしい)。今年自分が新入生にC++を教えるのですが、資料作成が厳しい。

学業

つらい

お金

ABC301で学生40位だったらしく、賞金をいただきました。ありがとうございます。初めて競プロから形ある利益が生まれました。

課題

今学期はまだ一つも落としてないけど、大体低い点数つけられて厳しい

進路

つらい

本

グラフ理論の本の演習問題をやってます。終わらん。

きのこたけのこ戦争

普段はたけのこを食べることが多いのですが、コンテスト中はきのこを食べることがあります。

甘さ控えめで食べても集中が切れたりしない

コンテスト中の飲み物

レッドブルで翼を授かっています
- ルビー味が好きなのですが、近場でどこも売ってなくて悲しい

睡眠vsごはん

大学に入るまでは食べることが好きでしたが、大学に入ってからは寝ることが何よりの幸せになりました。老化？

unionfind

問題解く時にunionfindを張ろうとすると「それDFSで良くない？」警察が心の中から湧いてでてきます。

それに対抗するべく、グラフを連結成分分解するライブラリを書きました -> 自作ライブラリで入出力の次に使うほど使用率が高くなりました。

ABCのCDEにグラフがでてくると、連結成分をこねくりまわして解けることが多いみたいですね！

ゲーム

世界樹の迷宮リメイクが楽しみ〜〜〜

現実が今そこそこ忙しいので、発売直後に買えるかが微妙

Fenwick Tree

BITと呼ぶ人が多いのですが、ちょっと紛らわしいなぁって思っています。

自分の作問

感想まってます！！！！！！！！！！！！！！！！！！！！！！！！是非チャレンジしてみてね！！！！！！！！！！！！！！！！！

ライブラリ整備

自分の自作ライブラリはここです

設計・ドキュメント等に不満があるので全部作り直す予定です。(ここで言うことで後に引けなくする)

独り言

コンテスト中は独り言で

「頼む」
「ありえね〜」
「setを窃盗！」

とかよく言ったりしています。

コーヒー

インスタントのお湯入れて飲むコーヒーを飲んでから缶/ペットボトルのコーヒーが飲めなくなってしまった。

うまい！

ARC試験管

典型とアドホックがいい感じに混ざっているような気がする。解いてて楽しい。試験管じゃないARCは解けなさすぎて苦行

制約メタ

自分はこんな感じのメタを張っています。

N <= 20 ・・・・bit全探索/bitDP
- 高速ゼータ変換等を疑うレベルにまだ達していない
0 <= A_i <= 10⁵ ・・・・バケット法/数列ではなく集合として考えるとうまくいく
N <= 100 ・・・・4乗(3乗ではなく)
10^{100000}・・・桁DP
N <= 2000の木・・・・二乗の木DP/各頂点毎に独立に解く
N <= 10^{12} ・・・・約数列挙/素因数分解
T <= 100ケースN <= 10⁹・・・約数列挙/素因数分解

腹痛

AtCoderコンテスト前ほぼ毎回腹痛と下痢に悩まされます。普段からお腹が弱いなんてことは無いです。なんでなんですかね？

好きな問題

好きというより、解いて印象に残っていると言ったほうがよいかも

はてなブログ

ネタが生まれたら書こうと思っていますが、ネタが生まれません。

青色に対する偏見

黄色になれずに or 青黄を反復してTwitterで心を痛めている人が多い気がします。そんなこともあって青を試される大地と勝手に読んでます。いや、青だから海原？

がんばるぞ〜

ビートボックスでぶち上がる活動

イヤホンとかつけて聞くと良い！

www.youtube.com

GBB23、会場東京らしいですね！大興奮！(自分は観戦いけないのですが...)

www.youtube.com

1600万再生！！！！凄すぎる！！！！

シャニマスの好きな曲

Overdrive Emotion
- サビ前の勢い上がっていく所(Bメロっていうのかな)がたまらない！
- ビートボックス聞いてぶち上がる活動と同じ栄養素を含んでいる可能性がある
- あさひの歌声が好き。コミュで聞ける声とは全然異なり大人びていて、「迷光をまとった姿」を体現している気がします！
PRISM
- サビのリズムが良すぎる。イルミネの曲聞きながら首を縦に振る変人になってしまう。
- 今年のクリスマスはサンタさんに重低音強化PRISMをお願いするつもりですが、学業がカスな悪い子なのでサンタは来ないです。かなし〜
太陽キッス
- 最近までサビの歌詞の「振り (Free) まいていこう (Go) 天下無双の笑顔」の(Free)をピースだと思っていました。耳が悪い

青色

灯織ちゃんカラーだ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！うおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお

*1:チーム向けと書いてありますが、自分は個人で利用しても便利だと感じています

2023-01-16

頭にやさしいABC285-E

前置き

必死に考えてやっとの思いで解けたのにパフォが1500くらいしかでなくてひっくりかえっちゃった。

間違いを書いていたらごめんなさい。間違いを発見した場合は https://twitter.com/zawakasu に報告くださると幸いです。

問題概要

atcoder.jp

一週間が $N$ 日の世界で次の条件を満たすように平日と休日を割り当てる。

少なくとも週一回休日を設ける
毎週同じ割り当て方をする

数列 $A$ を与える。ある日の得点を以下に定める。

休日なら0
最後の休日からその日までの日数を $x$ 、その日から次の休日までの日数を $y$ とした時、 $A_{\min(x, y)}$

適切に休日と平日を割り当てた時の得点の最大値を求めよ。

制約

$1\ \leq\ N\ \leq\ 5000$

$1\ \leq\ A_i\ \leq 10^{9}$

観察

2022-10-04

AtCoderでRating1200を達成しました。記録画像です

入水しました。ありがとうありがとう。青はまだまだかかりそう pic.twitter.com/NduRi2fA23
— カスタネット (@zawakasu) 2022年9月24日

ありがとうありがとう

プログラミングやパソコンを触りだして一年半(大学で習っているだけで実務経験等は0)
大学の偏差値は低い
大学レベルの数学知識は簡単な行列計算、微積分くらいしかない
- 競プロでありがちな代数の知識はほぼゼロです
寿司打は1万3000円くらい

という感じのスペックです。同じ境遇の人も同じじゃない境遇の人も参考にどうぞ～

実はlibrary-checkerの1は 'A + B' ではないらしい
AtCoderは1100問程度、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita によると1200問で入水者90パーセントらしいので妥当な精進量だと思います
- 今データ取り直すと90%ボーダー増えてるかも？誰か調べてほしいな(他力本願)

部活の先輩後輩と「毎日5問ACする、そのうち一問以上はRating + 1色diff以上」という約束をお互いに課していた時期がありました。
今も続いているのがベストなのですが、自然消滅的な感じで自分は続かなくなってしまいました。ごめんなさい。ごめんなさい。
- 今見たら一人だけまだ続いている人がいました。偉すぎる。
  - その人も淡々とレートを伸ばしてますね・・・継続大事・・・
参考に、自分が入緑したのは4月後半なので、ほとんどの緑diff、水diffは緑になってから解いたことになりますね・・・

水diffも比較的多めに解いてると思う。My自画自賛ポイントです

ARCは100問も解いてないらしい