2024-09-24

PCK2024予選参加記

本選出場が決まった&楽しかったので書きます。

予選まで

PCK出たいな〜と漠然と思っていたところ、強い後輩（soutome、敬称略）から「PCKでませんか」と誘われ、参加。

始まる前（当日）

ミニヨーグレット（小さいヨーグレットの粒がたくさん入っているやつ。おすすめ！）を購入し学校へ向かうところで、soutomeに遭遇。道中交通系ICカードをなくしたと言っていた。出場する他のチームの話や提出システムの話をしながら登校。
- soutomeと「2人ともそこそこのパフォーマンスを出さないと予選通過できなさそう」という意見で一致したので、お互い頑張ろうみたいな話をした。
パソコン室（実施する部屋としてパソコン室が使えることになった）に着いてからは、コンテストシステムにログインしたり雑談をしたりしていた。
- 過去問を5年分くらい見た感じ、今年はUnionFindが出そうだな〜と思っていたので、soutomeに話してみた。

コンテスト

※ジャッジが詰まっていたので、（提出時の時刻 / 処理時刻）という風にかきます。

※問題を正確に覚えていない部分があります。

コンテスト開始。（13:30）

1. もらったキャンディ

print(int(input()) - 10)

AC（13:30:50 / 13:30:59）

2. 神輿の担ぎ手

神輿の担ぎ手を確保するみたいな問題だったと思う
3~4つくらい（？）の変数が与えられるので、切り上げとかをしていい感じにする
AC（13:33 / 13:37）

3. ラッキーナンバー

0~9 が並んだ文字列 s が与えられるので、その中に c はどれだけ存在するか。

print(s.count(c))

AC（13:34 / 13:40）

4. 魔法のポケット

ビスケットが右のポケットに A 枚、左のポケットに B 枚入っていて、ポケットを叩くと右が C 倍、左が D 倍になる。左右合わせてビスケットをちょうど K 枚にすることは可能か？可能なら左右のポケットを叩く合計の最低回数を求めよ。

全探索。適当に書いて1度目の提出。（13:43 / 13:55）
6番まで解いた後、1度目の提出がWAになっていたので、すこし丁寧に書いてあげるとAC。（14:08 / 14:14）

5. データセンター

一つ一つのデータ保管庫には許容量 C_i が設定されていて、今 A_i のデータ量を保持している。データを最小単位で移動させることを繰り返してなるべく使用する保管庫の数を減らしたい。どれだけ減らせるか？

C_iを降順sortして貪欲。
AC（13:49 / 14:01）

6. 湖の調査

周りが海で囲まれている島があり、これを地図にしたもの（水が.、地面が#で表されたグリッド）が渡される。湖（＝海と接していない水たまり）の数を求めよ。

グリッドを (H + 2, W + 2) に拡張（周りに海を追加）してUnionFind。
UFが本当に出て預言者になってしまった。
AC（14:03 / 14:11）

9. 壁のリフォーム

壁の高さA_iがある。A_iの要素を足し引きする操作を何回か行って、別の壁B_iと「形」を合わせたい（＝すべての i で A_i = B_i + k となる k が存在すること）。最小操作回数を求めよ。

D_i = B_i - A_i として、D_i のどれかを0にする操作のみを考えればよい。後は実験してエスパー。
AC（14:43 / 14:43）
順位表を見ると、soutomeも6まで全て通している。

11. デイリーミッション

無向グラフ上を周り、いくつかの頂点を回る。「毒の頂点」をなるべく通らずに回る方法の中で、歩く距離を最小化したい。頂点数はO(N³)が間に合うくらい。

頂点数から、ワーシャルフロイドをエスパー。(毒を通った回数, 距離)のペアを管理して、遷移をいい感じに書く。
AC（15:04 / 15:06）

10. 宇宙戦艦イヅア

(Q, P)のペアが与えられる。これを、

(Q+P+A, P) にする操作1

(Q, P+A) にする操作2

をターンごとに行って、最終的なペアの最初の値を最大化したい。

入出力はこんな感じ（t: 操作1か2か）：

N

L_1 t_1_1 a_1_1 t_1_2 a_1_2 ... t_1_{L_1} a_1_{L_1}

L_2 t_2_1 a_2_1 t_2_2 a_2_2 ... t_2_{L_2} a_2_{L_2}

...

L_N t_N_1 a_N_1 t_N_2 a_N_2 ... t_N_{L_N} a_N_{L_N}

後ろから dp[今後ろから何番目まで見たか][何回操作1を行ったか] でDP。最初嘘貪欲を書いてしまい、合計6ペナ（！？）してしまったが、DPが見えたのでよかった。

AC（16:02 / 16:03）
ACした後、順位表でF5連打を行っても更新されず、順位表凍結があることに気づく。凍結時の順位は合計90点で全体14位。

解けなかった問題

7. 地上絵

回転移動した半円の弦の部分と、線分が交差しているかを判定せよ。

最初に見た時、弧の部分の判定もしなければいけないと思っていたので飛ばした。（実は弦のみ交差の条件は問題文に書かれていなくて、制約にしか書かれていないらしい）
10を解いた後、複素数の回転移動などを使って軽く実装してみたが、WAが出たのでよくわからなかった。

8. ルービックキューブ

ルービックキューブを実装せよ。

見た瞬間飛ばすことにした。

12.

見ていない。

終了後（当日）

コンテスト終了直後、soutomeに10が解けたことを伝えると、soutomeも1~6、9を通したのち凍結後に11を通していたらしく、チームの最終合計が110点であることがわかった。
終わった後、それぞれの解法を話したり、順位表を見たりした後、学校からの帰途についた。

結果

予選8位で通過することができました！やった〜
https://pckoshien.u-aizu.ac.jp/final/#team
パソコン甲子園ツイッター班のツイートで知ったのですが、僕の通っている高校ではPCK初出場らしいです。

感想

過去に出場したプログラミングコンテストの中でも今回はかなり集中できたので、とてもよかったです（小並感）
問題セットがかなり僕に合っていて、解きやすいと感じました。~~ところでルービックキューブ~~
soutomeが本当に強いので、助かった...（ありがとう！）

2023-07-06

PaizaBINGO Ruby正攻法最短（多分）を書いた

乱択がBANされるという風のうわさを聞いてガチゴルフをしたのですが、結局乱択の人が商品をもらったらしいです

問題

##.
.#.
.##

みたいな形式の3*3ビンゴ表（# -> true, . -> false）のビンゴ数を出力

コード

自力

a=`tr '.#
' 01_`.to_i 2;p [7,56,448,73,146,292,273,84].count{a&_1==_1}

気づかなかったやつ

a=`tr '.#
' 01_`.to_i 2;p [7,56,448,73,146,292,273,84].count{a|_1==a}

解説

a=`tr '.#\n' 01_`.to_i 2

##.
.#.
.##

を

'110_010_011'.to_i(2)

他：

''の中の改行は'\n'と同じ
バッククオートはshell呼び出し、trは置換コマンド
to_i(2)の括弧は削れる時がある
p [7,56,448,73,146,292,273,84].count{a|_1==a}

int count = 0;
for(const auto& _1 : vector<int>{7, 56, 448, 73, 146, 292, 273, 84})if((a | _1) == a)count++;
cout << count << endl;

と同じ

`[7,56,448,73,146,292,273,84]`

ビンゴである必要条件の#と.の並び（例：

#..
.#.
..#

とか

#..
#..
#..

とか）をa=`tr '.#\n' 01_`.to_i 2と同じ方法で10進数の数にして埋め込んだもの

2023-02-13

水色コーダーになりました

はじめに / 自己紹介

こんにちは。まぐげんがーです。高校1年生です。

AtCoder（アルゴ）で水色コーダーになったので何か書きます。

勉強したアルゴリズム・テクニック

コンテストで使用したことがある

二分探索
DFS
BFS
Dijkstra法
Floyd–Warshall法
nCr、nPr
約数列挙
素因数分解
modint
累積和
imos法
bit全探索
ナップサックDP
boolDP
他の様々なDP...
UnionFind
トポロジカルソート
最小全域木（Kruskal法）
座標圧縮

コンテストで使用したことがないが知っている / ライブラリに入っている / 聞いたことがある

ベルマンフォード法
強連結成分分解
偏角ソート
中国剰余定理
BIT / Fenwick Tree
Segment Tree
bitDP
削除可能UnionFind
Rolling Hash
ダブリング
最大フロー / 最小カット

AtCoder Problemsの情報

（もっと水色diffの問題を、解け！！！）

入れている拡張機能（atcoder.jp上で動くもの）

やってきたことと、それについて

ABCに出る、ARCに出ない

ARC怖くて出られていません。

JOI（日本情報オリンピック）に参加する

一昨年から参加しています。（2次予選落ち（一昨年） -> 本選140点Cランク（去年） -> 本選196点Cランク（今年））

JOIはAtCoderとはまた一風変わった問題を出題してくるので、面白いです。（来年が最後のJOIになるので、今年1年めちゃくちゃ頑張ります！！！）

Longest Streakを伸ばす

650日くらい続けました。意味は...あったかな？実感はないです（僕は精神力がカスなので途中から虚無埋めが多くなりました）

コードゴルフをする

楽しい！！！

副次的な効果として、自/他が書いた難読コードをスラスラ読めるようになります。

様々なプログラミング言語を勉強する

https://kenkoooo.com/atcoder/#/user/gengar_094?userPageTab=Languages

楽しい！！！

副次的な効果として、強い競プロerの方でC++以外の言語を使われている方のコードをスラスラ読めるようになります。

`komatta.md`を作る

ちょっと気持ちが楽になるのでおすすめです。

ライブラリを作る

僕はいつも提出の時にライブラリをまとめて（だいたい30000byteちょっとになるのですが）そのまま提出しています。

よかったこと

思い付きでコードをたくさん書いて消して...を繰り返すタイプなのですが、適当にUnionFindとかを呼び出せるおかげでトライ&エラーを繰り返すスピードが速くなりました。

よくないこと

コードの圧迫感が、凄い！

ヒューリスティックコンテストに出る

一応AtCoder ヒューリスティックレーティングも水色です。

ヒューリスティックが強くなるにつれて（というか、長期コンを経るにつれてと言った方が正しいかもしれませんが）、「コードを書きやすくするための実装力」がついていきました。（例えば、処理をブロックごとに関数に分ける、変数名をわかりやすくするなど）

（あと、ヒューリスティックコンテスト、単純にめちゃくちゃ面白いのでみんな出てくれ～）

除夜コン2022

半分寝ながら灰diff54問を解きましたが、思えばあの後から速解きが上手になったのかな、と思います（いつも半分寝ながらコンテストやってる、ってこと！？）

最後に

水色コーダーになることができて本当に嬉しいです！（自分の中で、特段何かができるようになったわけでもないのに、するっと水色になってしまった感触がありますが...）

次の目標

今年中にアルゴとヒューリスティックどっちも青色コーダーになりたい！！！！！！

2023-01-01

RubyでAAを作ってAtCoderの問題を解く

atcoder.jp

1. 空白が入らないようにしながらACするコードを書く

eval"K,=%s
i,s=0,''
(s+=(1<<i)&K>0??2:'0';i+=1)while(1<<i)<=K
$><<s.reverse"%gets.chomp

$><< : print。後ろに空白を入れなくて済む。
eval"%s"%gets.chomp : %sの部分にgets.chompを入れてRubyのコードとして実行
解法は冗長なやつの方がよいです　あとでかさ増しする労力が減ります
Rubyだとputs gets.to_i.to_s(2).gsub('1','2')とかでACになります

2. 適当にかさ増しする

eval"Happy,New,Year,__2023='Happy','New',%s,2||0||2||3
happy,new,year=0,'',2023
Author='gengar_094'
Twitter='@gengar094kypro'
Today='2023/1/1'
'tyAtCoder!'
(new+=(1<<happy)&Year>0??2:'0';happy+=1)while(1<<happy)<=Year
$><<new.reverse"%gets.chomp

AtCoderに提出する予定の場合、tyAtCoderなどAtCoderへの感謝の気持ちを忘れずに入れましょう

3. AAを作る←大変！

#      #                                          #      #                      #       #
#      #                                          ##     #                       #     #
#      #  ######   # #####   # #####   #      #   # #    #   ####   #        #    #   #   ####    ######   # ######
######## #      #  ##     #  ##     #  #     #    #  #   #  #    #  #        #     # #   #    #  #      #  ##
#      #   ######  #       # #       #  #   #     #   #  # ######## #   ##   #      #   ########   ######  #
#      # ##     #  ##     #  ##     #    # #      #    # # #         # #  # #       #   #        ##     #  #
#      # #     ##  # #####   # #####      #       #     ##  #    #   # #  # #       #    #    #  #     ##  #
#      #  #####  # #         #           #        #      #   ####     #    #        #     ####    #####  # #

4. AAの形にRubyコードに空白を入れて、`gsub(/\s/,'')`で空白と改行文字を削除して実行するコードに直す

行末の改行がなくなると動かなくなるので、代わりにセミコロンを入れます

eval"
H      a                                          p      p                      y       ,
N      e                                          w,     Y                       e     a
r      ,  __2023   = 'Happ   y ','Ne   w      '   , %    s   ,2||   0        |    |   2   ||3;    ;happy   , new,ye
ar=0,'', 2      0  23     ;  ;A     u  t     h    o  r   =  '    g  e        n     g a   r    _  0      9  4'
;      T   witter  =       ' @       g  e   n     g   a  r 094kypro '   ;T   o      d   ay='2023   /1/1';  '
t      y  A     t  Co     d  er     !    ' ;      (    n e w         + =  ( 1       <   <        ha     p  p
y      ) &     Ye  a r>0??   2 :'0';      h       a     pp  y    +   = 1  ) w       h    i    l  e     (1  <
<      h  appy)  < =         Y           e        a      r   ;;$>     <    <        n     ew.r    evers  e ;       ".gsub(/\s/,'')%gets.chomp

5. 完成！

こたつがめさんのICPCのやつ毎回すごいなあと思っていたので、それっぽいことをやってみました
12/31の午後6~7時くらいから作り始めたので間に合うかどうか不安でした
コードゴルフのテクが活きました　Ruby Golf最高！

2022-02-13

JOI'22本選　参加記

参加しました。

100 - 35 - 5 - 0 - 0　でした。DEの部分点通したかったなぁ…

時間配分

0（時間）:00（分）一問も完答できないかもな～とか思いながら問題のPDFを開く

～0:05 1の部分点解法を書く　+25点

～0:15 1の遅い解法を書く　+35点

～0:29 2の部分点解法を書く +10点

～0:51 2を誤読

～1:00 2の部分点解法その2を書く　+25点

～1:11 3の部分点解法を書く +5点

～2:00 その後3を読むもわからない　1の満点解法を書く +40点

～3:10 5の部分点解法を書くも、TLE　かなしい

～3:56 4の部分点解法を書くも、TLE　かなしい

感想

たのしかったです（小並感）

来年も本選に行けるといいなぁ…