トヨタ自動車 プログラミングコンテスト2022(AtCoder Heuristic Contest 015)
— titia (@titia_til) October 30, 2022
傾けた後、さらにもう一回傾けたときのscoreの和を評価値にした。
さらにもう一手先読みして同じ評価値を使おうとしたらTLEが出てきつかった。(途中までは元の評価値を使うことにした)
2022年10月30日日曜日
トヨタ自動車 プログラミングコンテスト2022(AtCoder Heuristic Contest 015)
2022年10月29日土曜日
yukicoder contest 366
No.2112 All 2x2 are Equal
No.2113 Distance Sequence 1.5
2022年10月28日金曜日
AtCoder Regular Contest 146
AtCoder Regular Contest 146 ABの二完。
— titia (@titia_til) August 20, 2022
A 大きい三数の入れ替え
B 大きいbitから貪欲に、ANSの最大値のそのbitを1にできるか? と考える。そのときに必要な回数をもちこし、変化させたA[i]=0としておく(その後はもっと小さいbitしか考えないので)。
C - Even XOR
D - >=<
2022年10月27日木曜日
AtCoder Regular Contest 148
D Bobが勝つためには、sample2のような真似する方法と、Mが偶数のとき、和がM/2になるものを偶数個作る方法しかない。考え方はあっていたのに実装ミスで2ペナしたのもったいなかった。
— titia (@titia_til) September 11, 2022
E - ≥ K
2022年10月24日月曜日
Codeforces Round #829 (Div. 1)
Codeforces Round #829 (Div. 1) DのTLEが取れない!
— titia (@titia_til) October 23, 2022
A 隣りにある1とー1で0を作る。
B xはx+1個欲しい
C 最初の(0の個数)個に1が何個あるか。一個ずつ期待値を計算してその和
D 空きマスからダイクストラしてTLE。PyPyで通している人がいたので高速化に走ったがダメだった。解法がまずい?
D. The Beach
yukicoder contest 365
No.2103 ±1s Game
No.2104 Multiply-Add
キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274)
キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274)Eまで。
— titia (@titia_til) October 22, 2022
C DFS
D 部分和問題
E bitDP
F Fraction使ってイベントソートしたが上手くいかず。
G フローだと思って考えていたけどグラフが構築できなかった。
F - Fishing
G - Security Camera 3
2022年10月21日金曜日
パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 273)
パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 273) Eまで。C~Eどれも難しかった。
— titia (@titia_til) October 15, 2022
A 階乗であることに後で気付いた。
B Bにしては実装難。
C 問題内容の把握が難しい。各数字が何番目かを予め調べる。
D 実装問題。
E 木を作る。DELETEなら親へ戻る
F - Hammer 2
G - Row Column Sums 2
2022年10月20日木曜日
AtCoder Regular Contest 151
AtCoder Regular Contest 151 BよりCがいけそうと思ってCをやっていたが、1caseがWAが取れず。遅解き二完でひどい。
— titia (@titia_til) October 16, 2022
A (0,1)のもの、(1,0)のものの個数をそれぞれ調べる。
B union-findでつなぎながら、答えを加算していく。
C 同じ数字が隣あっているものの個数を調べた後……?
C - 01 Game
D - Binary Representations and Queries
E - Keep Being Substring
2022年10月19日水曜日
Codeforces Round #826 (Div. 3)
F. Multi-Colored Segments
G. Kirill and Company
Codeforces Round #828 (Div. 3)
Codeforces Round #828 (Div. 3) E2が分からなかった。
— titia (@titia_til) October 16, 2022
B 偶数と奇数の代表を1個ずつ処理。
C 何個先にgがあるか。
D 2で割れる回数が大きい方から使う
E1 a~cを全探索。lcmを使って処理。
F 範囲がxのとき、(x-1)/2以下の全ての数を含んでいればOK。indexの最小と最大を管理
E2. Divisible Numbers (hard version)
2022年10月16日日曜日
Codeforces Global Round 23
D. Paths on the Tree
E1. Joking (Easy Version)
2022年10月15日土曜日
yukicoder contest 364 (Do you know Cherry Contest?)
yukicoder contest 364 (Do you know Cherry Contest?) Eが分からなかったのでマラソンに行った。
— titia (@titia_til) October 14, 2022
C 過去への移動回数を探索。
D 減ったとき、増えたときでの最大scoreを持つDP
F ロリハ
マラソンの最後の提出が135……まで伸びてびっくり。
— titia (@titia_til) October 14, 2022
(x, x, x)という形なら点数調べるの簡単なので、この場合に限定して乱択しました。xは1~6の範囲にしたらsampleの点数が一番が高くなったのでそれで。
No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
2022年10月14日金曜日
ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)
ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268) ABCEFの五完。
— titia (@titia_til) September 10, 2022
A len(set(A))
C Q[P[i]]=iなる配列を考えると分かりやすい。
E 差分計算。難しいがやることは分かるので頑張る。実装で双対セグ木を使った。
F (a,b)=(xの個数,数字の和)とすると、a/bでソート。
最後、DでWAが取れなかったけど、DのWAの原因はN=1の場合分けをしていなかったためでした。
— titia (@titia_til) September 10, 2022
テストケースの名前見てはじめて気付いたので、最初D飛ばしたのは正解。
G - Random Student ID
Ex - Taboo
Codeforces Round #827 (Div. 4)
F tにa以外が現れたらYES。otherwise sにa以外が現れたらNO。sもtもaのみのときは長さを比較。
— titia (@titia_til) October 13, 2022
G 使っていない中で最大のものを使う。使ったやつのbitはもう見ないので、((1<<32)-1)^xで&する。
2022年10月13日木曜日
AtCoder Regular Contest 149
AtCoder Regular Contest 149 Cまで三完
— titia (@titia_til) October 2, 2022
A 全探索できることにずっと気付かなかった。
B 片方をソート
C 3で割った余りが1,2のものを並べた後、適切に3の倍数を並べる。1+2が素数に気付かずWA。素数の最大値が10^6(正しくは2*10^6)としており3WA。
D マージテクだよね? と思うもバグらせて終了。
D - Simultaneous Sugoroku
2022年10月12日水曜日
yukicoder contest 341
No.1917 LCMST
2022年10月11日火曜日
Codeforces Round #825 (Div. 2)
D. Equal Binary Subsequences
2022年10月10日月曜日
AtCoder Beginner Contest 272
AtCoder Beginner Contest 272 Fが分からなかった。
— titia (@titia_til) October 8, 2022
A sum
B 人iが参加した舞踏会一覧を持って全探索。
C 偶奇で分ける
D BFS
E 各数が0~500になるのはいつかを調べる。答えが500以上になるなら、愚直に計算。
G Mの候補はある二数の差の約数なので、乱択する。
F - Two Strings
2022年10月9日日曜日
AtCoder Regular Contest 150
AtCoder Regular Contest 150 Cまで。ABでハマったのが痛い。
— titia (@titia_til) October 9, 2022
A 場合分けがんばる。
B 商(B/A)を一つずつ減らしていく
C 問題内容を理解するのが難しいが、理解できれば01BFS
D - Removing Gacha
2022年10月8日土曜日
Dytechlab Cup 2022
Dytechlab Cup 2022
— titia (@titia_til) October 7, 2022
B x^2~(x+1)^2で3個
C 正方形の残りの1マスとx方向y方向とも偶数マス離れた場所には行けない。最初の3マスが角にある場合、端しか行けない。
D 一つの辺しか使わない。辺ABを、直接1とnにつなぐか、1~xとx~nの距離が最短のところまで一点を運び、縮約した後、1とnへつなぐ。
E. Ela Goes Hiking
2022年10月4日火曜日
yukicoder contest 313
No.1677 mæx
2022年10月2日日曜日
yukicoder contest 362
No.2089 置換の符号
No.2090 否定論理積と充足可能性
estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)
estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014) おつかれさま。
— titia (@titia_til) October 1, 2022
最後C++に書き直そうとしましたが、時間切れで終了。悲しい。
・新しい頂点のウェイト/周囲の長さ
を評価値に次の四角形を作る
・大きいウェイトの頂点に至る答えの列を元にやり直す
という感じでやりました。
estie プログラミングコンテスト2022(AtCoder Heuristic Contest 014)
— titia (@titia_til) October 1, 2022
解説放送を見て、似た考察はしていたのだけど、うーん……、という感じでした。
解説と感想をだらだら書きます。
この感想ツイートが長くなったので、こっちにまとめておきます。
序盤は、「オセロっぽいな」と思い、オセロの評価値として「自分が置ける位置の個数」が有名なことにならい、「次に作れる長方形の個数」を評価値にしようとしました。が、これで長時間回してもあまり伸びない。なので、それに代えて、
・長方形の周囲の長さ
・次におく頂点のweight
・長方形を作ったとき、新たに作れるような長方形の個数
あたりを評価値に。
最終的には、
・次におく頂点のweight/(長方形の周囲の長さ^(1~4のランダムな数))
にしました。(それをheapqに突っ込み、上位三つのうちからランダムに採用)
解説放送を見ると、weightは取り入れなくて良かったらしいので、それを消して回して実行してみたけど、うちの環境だと点数は伸びません……。(PyPyだし、実行回数が足りないのか? と思い、10倍の時間回したので比較したら多少は伸びたが、50ケースで+100万もなさそう)
解説放送で言っていた「枠」という概念にはたどり着けなかったけど、まあそれっぽいことは考えていたとは思う。
「枠」は思いつけたとしても実装に反映できたか自信ないし、評価値については及第点かなぁ。
山登り・焼き鈍しについては、
・部分的に残して作り直す
としていました。答えの列のある長方形を見て、それを作るのに必要なものたちだけでやり直す、という山登りです。
・最終スコアが大きい答えの、ランダムな長方形一つ
を残すのに加えて、weightの大きい頂点までいったものを採用したいと思っていたので、
・(スコアは悪くても)weightの大きい頂点(長方形)
を残してやり直すことも実装しました。
解説放送では、部分的に壊してやり直すと言っていて、そっちかー、という感じに。
その方が自然な山登りだけど、大きいweightのものを残したいと思ったので、考えなかった。
どのくらい差があるのかは分からないけど、weightが大きい頂点を残したい、と思ったのは筋が悪かったのかな……。
感想書いたけど、何を反省すべきかよく分からない!
高速な言語(C++かRustで書くのは考えた)で書いていれば気付けたことはあったかもしれないけど、気軽に色々試すなら慣れているPythonの方が良い、と思ってPythonで書いているので。
最後、C++に書き換えようと思ったとき、書き換え時間の見積もりがまずくて終わらなかったのは良くないけど、そんなことを反省しても、という気がするので。