yukicoder 317 あとがき

yukicoder 317 に参加して頂いた方ありがとうございました。

解説は各問題の解説ページからご覧ください。

(以下ネタバレ注意)

A Unfair RPS (想定diff:1)

簡単枠です。

解説 をぜひ見てください。

Whitespace と Assembler がわかりませんでした。

B floor X (想定diff:400)

誤差問題です。

二分探索するか \sqrt(N) 辺りを探索することで解くことができます。

C half price (想定diff:800)

3bit全探索で解くことができます。(3bitってbitじゃなくないですか？)

商品の選び方を求めることに気をつけてください。

問題番号からわかるように半年くらい前に作ってました。

D count good string (想定diff:1200)

動的計画法で解くことができます。

元ネタhttps://codeforces.com/problemset/problem/1426/F

E Much Matching (想定diff:1300)

二部マッチングに見えますが、3つ目の条件より異なります。

条件を整理すると longest common subsequence のように解くことができます。

F Many Bus Stops (easy) (想定diff:1400)

N の制約よりdpでは間に合いません。

漸化式を立てると行列累乗ができます。

G Mode of long array (想定diff:1550)

想定解2で自身満々にテスターさんに渡したらセグ木で通されました...

std::set でも解けます。

H Many Bus Stops (hard) (想定diff:1600)

easyから変わったことはバスが M 台になったのと バス停が C 個に増えたことです。

バス停2\sim C が1つにまとめられることに気が付けばあとはeasyと同じです。

Cの制約と複数テストケースでないのは制約引っ掛けです。

さいごに

前回の単独コンから2か月しか経ってなかったみたいです。

テスターをして頂いた tnodino さん、 ir_1st_vil さん、 sak さん、 chineristAC さん、 yuusanlondons さん ありがとうございました。

また、コンテストを開かせて頂いたyukiさんありがとうございました。

コンテスト後の追記

CDEが難読で、FHに問題文の不備があり申し訳ありませんでした。

AtCoder 水色になりました

harurunさんのAtCoder Beginner Contest 213での成績：918位
パフォーマンス：1544相当
レーティング：1169→1212 (+43) :)
Highestを更新し、4 級になりました！#AtCoder #ABC213 https://t.co/Wdz5e8lgkx
水色になりました！！これからも頑張ります！！！ pic.twitter.com/AYzKBA4XYl

— harurun🌹 (@harurun_p) 2021年8月8日

苦節8か月強、ついに水色になりました

いつもの

実は緑も全然埋まってないんですよね。最近はもっぱら早解き3～4完で水パフォを取ってました。

何をやったか

実は何も覚えていないのですが、入緑記事と比較すると300問くらいACしてるはずなんですよね。 深さ優先探索はできるようになりました。(幅優先探索ができなくなりましたが)

作問のすすめ

作問をしましょう。

今回水色になれたのは作問のおかげと言うのは過言ですが、少なからず糧にはなってると思います。

ちなみに先週の金曜日にyukicoderでコンテストを開きました。

yukicoder.me

これからやること

とりあえず聞いたことあるけど理解していないもの書き出してみた pic.twitter.com/SMWrgtAXkG

— harurun🌹 (@harurun_p) 2021年8月9日

メモのつもりでツイートしたらなんか伸びてました。ﾄﾞｳｼﾃ...

ここに書いてあることからわかるようにDPができません....

今後の目標

年度内、つまりB2のうちに青になることを目標にしています。

水色になるためにやったほうがいいこと

・ライブラリ整備

・codeforces に出る (できればバチャもやる)

・早解きを練習する

といったところでしょうか。知識は緑のときとそこまで変わってないような気がします。

質問コーナー

書くことがなさ過ぎてTwitterで質問しました。リプしてくれた方ありがとうございます。(まだ募集中)

Q: 入水記事はいつ？
A: 書くことがない、質問を募集したいくらい

— harurun🌹 (@harurun_p) 2021年8月10日

Q: 今年の目標

A: 1400辺りです。とりあえず緑に落ちないように頑張ります。

Q: 実力つけるのに1番貢献したと思うこと

A: バチャですね。過去問だと解説を見てしまうのでバチャのほうが良かったと思います。

Q: ICPC関連のお気持ち

A: 人数が足りません！！！(PG Battleも含めて)誰かいないかな～

Q: 作問の経験は、役に立った感じある？

A: 深さ優先探索書きまくったので多少は役に立ったと思っています。

まとめ

早解きは正義。

ここまで読んでくださりありがとうございました。次の色変記事が書けるようにがんばります。

yukicoder contest 308 あとがき

yukicoder contest 308 あとがき

yukicoder contest 308 にご参加して頂きありがとうございました。解説は各問題の解説ページからご覧ください。

各テーマは以下の通りでした。

問題	テーマ	想定diff
A	簡単枠	1
B	DFS	400
C	ダイクストラ法	1000
D	クラスカル法	1000
E	Unionfind + DFS	1200
F	セグメントツリー or BIT	1400

各問題の総評

A 「森」

簡単枠です。後々の問題のために聞いておきました。

想定解答時間:3分

B 「Easy Tree Query」

元ネタ ABC138D Ki

前計算で各頂点を根とした部分木の頂点数を求めておく問題でした。

想定解答時間:5分

C 「Robot Maze」

ダイクストラ法を使う問題でした。制約はひっかけです。

判定問題にしたらダイクストラ法に見えないかなと思って出しました。

想定解答時間:16分

D 「最小通信路」

クラスカル法を知っているかを問う問題でした。

UnionFindを使わずに深さ優先探索で連結判定をしてもACすることができます。

なお、PyPy3などの多倍長整数がある言語で二分探索することも一応できます ( 制約をこれ以上大きくすると入力でTLEする可能性があるためこの制約になりました ) 。

元ネタ ABC181F Silver Woods

想定解答時間:16分

E 「簡単な色塗り」

元ネタ ARC111B Reversible Cards

構築問題でした。意外と実装が大変です。詳しくは解説を見てください。

実はmax-flow(min-cut)でも解くことが出来ます。

ちなみに、典型90の062 Paint Allを誤読して生えた問題でした。

想定解答時間:30分

F 「Tree Xor Query」

元ネタ ABC185F Range Xor Query

木上のRangeXorです。木を上手く変換すると解くことが出来ます。yが10ビット以下なことに注目するとビットごとに考えると簡単に解けます。また、先行順巡回するとビットごとに考えなくてもACすることができます。

Testerさんに自信満々に出したらTreeライブラリでぶん殴られましたが、Euler TourはABCのレベルを超えていると思ったので制約は変えませんでした。

想定解答時間:30分

全体を通して

Eのevilケースの制約違反はmaxflowを落とそうとした残骸でした。申し訳ありませんでした。

感想

F解くの速すぎませんか？上位陣はライブラリでぶん殴ってくるとは思いましたがここまで通されるとは思ってませんでした。ABCDは大方問題なくそれなりに通して頂いたので良かったです。 Eを出したくてこのコンテストを作ったのですが、それなりに暴れてくれてよかったです。実はDは元々☆1.5想定でCに置いていたんですが、テスターさんの助言によりDになりました。かなり助かりました。

さいごに

最後に、テスターを引き受けてくださった、serpentさん、milkcoffeenさん、sakさん、koboshiさん、platinumさん、Kazunさん、まぐすたさん、ありがとうございました。

また、コンテストを開かせていただいたyukiさんありがとうございました。

AHC003 参加記

記事をお読みいただきありがとうございます。

AtCoder Heuristic Contest 003 に参加して、88,128,103,230点(システス前)で423位でした。

2021/05/31追記
システス後:2,648,223,238,697点, 416位
(88,128,103,230×30=2,643,843,096,900 < 2,648,223,238,697)

期間中ほとんどの時間費やしたにも関わらず、90,000,000,000点を超えられませでした。

おしまい

これだけだと少し悲しいので、供養の意味も込めて、日記っぽくして書いておきます。(期間中一応メモをつけてました、メモ部分はコードで囲ってあります)

5/22

とりあえず、xの差、yの差で愚直解 (xとyどっち先にやるかで差が出る)
コストの平均をメモして、愚直の2択を選ぶ、帰ってきた平均をメモして繰り返す

愚直解を投げるのに、スコアの入力の受け取りを忘れたりしてペナを量産してました。

1万ケーステストケース生成しました。

カスみたいなclarを投げました。ごめんなさい。

5/23

負の辺がなさそうなので、ダイクストラをしてみる
辺は10000テストケースの辺の値の平均にする
最初だけ愚直に2択ランダム
その後はコストをメモして更新しながらダイクストラ
(間に合わなさそうなら部分ダイクストラ？そもそも遠回りするメリットないから、どこで曲がるかの判定だけでいいかも)
->つもりだったが結局部分的なdpをして経路復元をした

(sik,sjk)から(tik,tjk)のDPをしてみました。
https://atcoder.jp/contests/ahc003/submissions/22860551

5/24

平均のメモをcountごとに調整
ダイクストラやったほうがよさそうなことが判明(時間足りなさそうだったら、後ろのほうだけでも)

辺の重み予測とか色々やってました

5/25

ダイクストラをバグらせる

そのままです。提出はなし。

5/26

提出してみるとめっちゃ下がった
原因は明らかな遠回りをしてしまっている
DPに戻した

ダイクストラしたら点数が下がりました。原因は辺の重みの予測を失敗していたらしい。

始点と終点のx座標or y座標が同じとき dpをしていなかったので、±1の範囲でdpしました
関数化してなかったせいで実装が地獄でした。
https://atcoder.jp/contests/ahc003/submissions/22934124

5/26 深夜

点数で追い越せないからレートで追い越した pic.twitter.com/vaQ56fed0m

— harurun🌹 (@harurun_p) 2021年5月26日

AHCのレートで順位表を色付けするスクリプトを作って遊んでました。
あとから見ると、レート高いのに負けてて悲しくなっています。
スクリプトURL:
greasyfork.org

翌日寝坊しました。反省しています。

5/27

パラメータいじったけどあまり変わらなかった
他のDPの場所も1マス広げてみたい

辺の重みと増分を色々といじりました。

5/28

ローカルジャッジが3日目からバグっていたことが判明
どうりで点数がかわらないわけで...

ローカルジャッジのために以下のスクリプト(Python)を使ってました。

import sys
import os
M=0
N=10000
if len(sys.argv)>3:
  raise Exception
elif len(sys.argv)==3:
  N=int(sys.argv[-1])
  M=int(sys.argv[-2])
  if M>=N:
    raise Exception
elif len(sys.argv)==2:
  N=int(sys.argv[-1])
with open("result.txt",mode="w")as f:
  pass
for i in range(M,N):
  t=str(i).rjust(4,"0")
  input_file=f"in/{t}.txt"
  os.system(f"cargo run --release --bin tester {input_file} solve/main9.exe >> result.txt")

f=open("result.txt")
L=f.read().split()
f.close()
s=0
for i in L:
  s+=int(i)
print(s/(N-M))

バグっていたというか変え忘れなんですが、main9.exeの部分が3日目あたりのmain3.exeになってました。
(Rustのコードを少し変えて、スコアだけを出力するようにしてました)

5/29

dpの小手先改善
tabnineの自動入力に頼った結果、添え字バグ

(sik,sjk)から(tik,tjk)のdpの範囲を上下左右に1つづつ広げました。
思った以上に実装が地獄で、大変でした。

こんな感じ。すべて場合分けしました。

tabnineで自動入力しまくってましたが、たまに変になってバグりました。
あったほうが100倍いいのでtabnineはおすすめです。

パラメータガチャのためにたくさん回し続けてたら、tester.exeが削除されてしまいました。(まぁコンパイルし直せばいいだけでしたが)

結局、辺の重さを3500、増分を0にしました。

最終的な提出コード
atcoder.jp

感想とまとめ

コンテストが終ってから、最初だけdpして、後半ダイクストラすればよかったなと思いました。次の短期コンテストは頑張ります。
長くなりましたが、最後まで読んでくださった方、そうでなかった方もありがとうございました。

yukicoder contest 290 A programing 感想

問題

yukicoder.me

解説

https://yukicoder.me/problems/no/1469/editorial

小学生のような感想

解説に書いてある通り、O(|S|^2)を落とすために試行錯誤していたら、|S|が大きくなってしまいました。
すべてはO(|S|^2)解法で5*10^5が通ったC++のせいです。

問題文に書いてある通り、Bashでは通りませんでした。
謝罪します。
(bashでpython使おうとしたら、権限がなくてダメでした)
(2021/04/09 23:31 追記) Bash(外部呼出しあり)でACしている方を確認しました。(解読不能)

↑普段触らないJavascriptやRustでもACを確認しました。

Javascriptは入出力が意味不明で死にました。

Rustで文字列は二度と触りたくなくなりました。文字列(i番目のアクセス)遅すぎませんか。

提出一覧を見てて思いましたが、PyPyでTLEしている人が多い印象でした。
PyPyは文字列の足し算は遅いので、今回は足さずに出力する方法があります。
あとは、|S|=1のコーナーケースでREになっている人もいました。
(原案時には|S|=0、つまり空文字列を入れようとしていましたが、Javaが空文字列受け取れなかったので削除しました。)

制限時間が3secになってたのは、aseertをpythonでやったら2secだとTLEしたからです。

たぶんまた今度なんか出すと思います。

yukicoder April Fool Contest 2021 C 114101097100032118101114116105099097108108121

謝罪

WIPのままでした。ごめんなさい。

謝罪その2(2021/04/01 23:22 更新)

programmingのスペルを間違えておりました。申し訳ございません。

問題

No.3075 114101097100032118101114116105099097108108121 - yukicoder

解説

解答は2通りあります。
https://yukicoder.me/problems/no/3075/editorial
ちなみに、テストケースは10個ありますが、そのうち5個は入力をそのまま出力してもACになります。

統計

コンテスト中の提出で "input"と"INPUT"の割合を(手動で)計算しました。
input 82%(50/61)
INPUT 18%(11/61)
AC数 61(writerのACを除く)

エスパー縦読みしない限り、解法としてはINPUTのほうが面倒です。(4-1=3を使う。ASCIIコードだと断定するなどエスパー要素が強い。)

感想

コンテスト前まで心配でしたが、それなりに解かれていて(☆1最難関にはならなかったので)、安心しました。
スペシャルジャッジで提出言語が取得できるようになって欲しいと思いました。

yukicoder 初めてのWriter

初めてのWriter

yukicoder contest 285に１問出させて頂きました。TesterをしてくださったNatsubiSoganさん、色々と教えていただきありがとうございました。また、解いてくださった方もありがとうございました。
問題
yukicoder.me
解説
https://yukicoder.me/problems/no/1416/editorial

感想

思ったよりWAが出ませんでした。

サンプルの特徴として、

• 昇順にソートされている
• n=Σpow(2,k)になる

という罠を仕掛けましたが引っかかる人が全然いませんでした。
(1番目はsort忘れ。2番目はWriter解のように解くとREする引っ掛け)
当初は☆1で作ってたため、答えがintに収まるようにしています。
ちなみに、Python以外でも通ることを確認するためにCとC++とJavaでも通しました。Javaが難しかったです。

元ネタ

atcoder.jp
葉→頂点
と読み変えると同じ問題です。

最初は二分木という言葉を使っていましたが、味気がなかったため、意味のわからない問題文になりました。あんなショッピングモールが実際にあったら倒壊してますよ。
地下k階とする案もあってこっちのほうが物理法則的に自然でしたが、地下0階ができてしまうので諦めました。
オリバー君をイギリス人とすることで解決しました。

次

たぶんやります。