ご迷惑を掛けているのであれば、ごめんなさい」■最近読んだこれの一種かなと思った。「「謝らない謝罪」が日本で蔓延している|ニューズウィーク日本版 オフィシャルサイト」 市長さんに聞きたい。で、あなたは迷惑をかけたと思ってるの? 思ってないの? A⇒B という型の命題において A が成り立たないなら B の内容が問われないとは最近目にした話題>20210518。内容の定まらないどうでもいいコメントを出したよね(全文を知らないでこう書くのは早計だけど、ま、気楽な立場です)。
N.times.with_index((N+1)*(N/2)){|i|...}
とか謎なことしてる……。結果的に不要な考慮だったので無駄だけど問題なし。最終更新: 2022-02-17T12:53+0900
第四回までの日記>20201111p01。
課金ユーザーじゃなくてごめんね。@atgolfer1 に流れてきたツイートを見てはじめて問題が公開されていること、第七回が行われていたこと、終了していたことを知ったよ。
やるだけ。提出 #24382962
小さい方を選ぶだけなんだけど、10 分以上切り捨てたり余りを取ったりして悩んでいたのは内緒。提出 #24383193
Ruby なので 10 進 100 桁はなんの障害でもなかった。提出 #24383281
5つのパターンをじっと見れば最終結果に影響するような文字の取り合いがないことがわかる。提出 #24383341
探索が許されていることと操作が1回に限られていること、それと遷移が足し算ではなく掛け算だという点が違うけど、問題の形としては ARC122 の C 問題 Calculator を思い出した>20210612p01.03。これが解ければ ARC122-C も解ける!
スケジューリングの問題だけど、求められているのが最適化ではなく判定だという点で、最も簡単な部類。提出 #24383711
20 分考えた。
どんな正の整数でも、テキトーに選んだ正の整数を基数としてその冪乗の和で表せるのは当然だけど(N 進数ってそういうもの)、使える数字が 0 と 1 と -1 に限定された 3 進数ではどのように事情が異なってくるか、という問題。
2×3^x = 1×3^{x+1} - 1×3^x
という感じで、2 を -1 に置き換えてから次の桁にツケをまわしていくのがいいでしょう。提出 #24384055
解けてないよ。制約が小さいから探索していいのだろうけど、それでも 100 の 100 乗になるようなバカな探索は許されない。私はバカです。
上限の揃った制約が DP だと告げている。それも3乗の。まだ8問目だからって雑な探索で解けるとなめてかかっていたのではないか?
なだらかな折れ線グラフを書きたいのだから、遷移先の幅は自ずと限られる。(W = A.sum/[N-2,1].max+1
-2, +1 はテキトー)
「ABC-D 虐殺三銃士」のひとつ「Congruence Points」を思わせる問題だけど、両目の位置を手がかりに確定した情報が得られるところが優しい。
図形問題は行列や複素数に計算を丸投げしがちなので、これは自分で式を書いた。25 分かかった。提出 #24392172
「強連結成分分解をしよう」がキーワードだった競プロ典型 90 問の 021 - Come Back in One Piece(★5)がすぐに思い浮かんだんだけど、深さ優先探索を2回するんだというアルゴリズム解説は何か所かで読んでたんだけど、これは 17 問ある★5問題のうちで解いてない3問の1つなのだった。
雰囲気は掴んでいたので雰囲気で書いた。提出 #24393748。細部が詰められてなくて無駄があるかも。競プロ典型 90 問のおかげでアルゴリズムの顔見せだけは済んでいたので、今度は実装するところまでこぎつけた。
理解が甘くて 1 TLE。実装ミス(<
にすべきところを <=
にしていた)で 1 WA。AC はこれ>提出 #24424698。
最短経路問題ならダイクストラ法なんだけど、満足度と所要時間の2つを考えなければいけないのをどう考えるか。所要時間が最短であることが第一で、満足度の高さはその次に考慮すればいいだけなんだけど、だけど、「満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません
」という文言がちょっとひっかかるよね。経路を記録して重複を排除しないといけないの?(それには無視できないコストが……)
もちろん負の移動時間はないから、同じ都市を2度訪れる経路が最短になることはない。だけど次の2つのようなパスで所要時間の合計が同じになる場合をどのように扱うか迷った。
都市 M に着いたときの満足度の総和は明らかに2、3、4を経由してきた経路の方が大きくなるんだけど、もう一方の経路は M のあとで7、8、9を経由することで取り返すことができるかもしれない。M に着いたときの満足度の低さを理由にして一方のパスを捨てていいのかどうか。
実は上の図には嘘があって、上の図のような状況の実際は下のようになっている。
これは1と M とのあいだの最短所要時間と、M と N とのあいだの最短所要時間がどちらも1つの値に決まることからわかる。最短経路であるどの2つのパスを取り上げても、分岐と合流を繰り返す第3のグラフのような関係になることが納得できたら、ある都市に最短で到着する経路のなかから最大の満足度を記録するのでいい。
セグメントツリーなんだけど、最小値を持っているインデックスをどうやって列挙するかという問題。
最小値の記録と添字の記録をセグメント木と配列で分担しようとして TLE を出したり(提出 #24408482)、セグメント木の実装ミスで大量の WA を出したりしつつ(提出 #24412768)、三度目の正直で AC>提出 #24413254。
セグメント木を上から下に下るのって苦手。(根っこが上です。逆にすると頭が働かない)
全部を分割した状態から始めて、損をしない範囲で統合していくのかなと思ったけど、並べ替えができなくて境界が入り乱れるのを、どう整理して扱えるのかわからない。
とある赤亀コーダーさんによると全体でこの M が一番難しかったらしい。
昨日これの簡単なバージョンを解いたよ>「B - すぬけ君の塗り絵 2 イージー」(提出 #24414821)。
二次元累積和かなと思うんだけど、ABC203-D Pond も競プロ典型 90 問の 081 Friendly Group(★5)もまだ解いていない。二次元累積和って累積和の累積和とは違うんだなー、という感想を持ったのは覚えてるけど、よく思い出せない。
O 問題が解けたのは初めて。
入力を圧縮したり累積を記録したりして計算量を削減するのは、競プロ典型 90 問の 089 - Partitions and Inversions(★7)ぽいなーと思った。
以下は考えたこと。
.each_with_index.each
とか謎なことしてる……。幸いにしてこれは無駄なだけで害はないけど、部分的な修正を繰り返すとこういう風に、(通して書き下したときにはありえない)謎なバグを仕込みがち。最終更新: 2021-07-19T22:56+0900
悔しいなあ。手も足も出ない方がまだあきらめがつく。
1時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、5つあるケースの最後の1つの答えが違っているのに気がついていなかった。ダメダメである。
RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。
Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう1か所(b+(d-1)%10
の %10 が完全に余計)。
プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。
答えの上限が5だと見抜いていたところは偉いと思うんだ。なぜ5かといえば、項数が1ならある桁に関して作れる数字が 1..3。2なら 2..6、3なら 3..9、4なら 4..12、5なら 5..15 ということで、最初に 10 種類の数字が作れるのが5項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。6以上に項数を増やしてもできることは増えない。
ほとんど違いませんよ。でも A から F まで6問ある中の3問しか相手にしていないのに、時間内に完成させられないんだなあ。
実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。
ただの貪欲。提出まで 15 分>提出 #24363550
AC まで 2 WA、33 分。どういうこと? 10 分時点で9割5分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き!(知らないわけではない。括弧と波括弧に使い分けがありそう? それは知らない)
AC>提出 #24361099。ほとんど違いませんよ(2回目)。
最終更新: 2022-01-25T19:28+0900
A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで4完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。
30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、3分岐のうち2つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の2択ではなく AC/WA/RE の3択にするテクニック。WA がなかったということで、中身のある2分岐にミスはなさそう。
複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。
DP です。1行目から行ごとに考える。
罠があるとすれば、同じ行から2つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。
m1 が同じ行内からもう1駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。
その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。
ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。
」で問題文が締められているのだけど、2、3回読み直したよね。え? どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています
」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。
A1+A2+...+AN≤8888
があからさまな弱点なので、そのサイズの配列にそって処理を進めることにした。不可能なペアはビットフラグにしてカードごとにまとめた。88 ビットは微妙に大きなサイズだけど気にしない。8888 サイズの配列に組み合わせをたくわえていって、かぶりが出たら答え。88 個の組み合わせの総数が 2^{88}-1 なのでどうなるかと思ったが、通った。提出 #24083340 (AC / 213 ms / 同じ内容) 想定解は組み合わせにどんどんカードを足していく深さ優先探索だったのでちょっと違う。こちらは和が小さくなるものから順番に組み合わせを作っていったのだが、無駄が多かったかもしれない。■今日の1問は「089 - Partitions and Inversions(★7)」。典型知識の組み合わせだからとっかかりのない難しさというのではないが、脳がオーバーフローするややこしさなのがつらい。制約が緩かったら再帰でも配列ナメナメでも理解に沿った素直な実装ができるのだが、それが許されないせいでコードを変形して最後の5、6行に行き着くまで何時間もかかった。AC がすごく嬉しい。■しかし毎日 AC を(1つ)増やしてもラストスパートをかける人が増えているのか日々順位は下がっているのだ。くっそー。俺は凸包の点数はいらねーんだ。2点問題が TLE するからって他の言語を使ったりしねーんだ。……なんて考えでいるあたり、「くっそー」と言いつつ全然悔しくはなさそうである。■明日の1問は 9:00 から 19:00 のあいだに提出しないといけない。家を離れている時間とほぼ重なっているのと、スマホコーディングなんて考えられないオールドタイプなせいで、かなり厳しい。チャンスは2時間。★6★7なら見込み薄。■■■一日経ったので(89 問目)>提出 #24092271 (AC / 932 Byte / 805 ms)。驚いたことに想定解法である>ツイート。6つ7つの典型キーワードが列挙されてるけど、すごい人は意識せず当たり前にそれらの考えを適用しているから逆にキーワードが見えにくかったりするのではないか。そういうことが @evima さんおすすめの書『習得への情熱 ─チェスから武術へ─ 上達するための、僕の意識的学習法』に書いてあったよ。自分は意識して自分のものにすべき段階。■「コードを変形して最後の5、6行に行き着くまで何時間もかかった」 これはつまり、問題を解くのに方程式を解くようなやり方ができていないということ。どういうことか。変数を習う前の小学生は速さを求めるのに距離÷時間を、距離を求めるのに速さ×時間を、時間を求めるのに距離÷速さを考える必要があるけれど、中学で変数と方程式を習えばどれか1つの式に変数と値を割り当てて機械的な変形・展開で解ける。求める対象に変数という形を与えることで掛けたり割ったりの対象にできる。そういう強力な道具を与えられた中学生の方がある意味小学生より楽をしている。中学生になりたい。■最終結果。75/90 問、334/423 点でぴったり 200 位。★別集計>★2(8/10)、★3(20/20)、★4(14/14)、★5(14/17)、★6(12/14)、★7(7/15)。★7は部分点付きなので、なんらかの点を取ったものは 15/17 問であり、点数にすると 67/108 点。require'prime'
して K.prime_division
をこねくりまわす方針が良くなかった。提出 #24021051 (AC / 121 ms / 同じ内容)■ソースコード共有やツイートを見てると「ポリアの数え上げ定理」や「バーンサイドの(ではない)補題」といった異次元キーワードが目に入る。チョトナニイテルノカワカリマセン。■そして今日の問題「086 - Snuke's Favorite Arrays(★5)」も数え上げ。★5つでは足りないよ。でも ABC-E かというと(最近の ABC-E は緑でも水でもなくて青ときどき黄なので)それほどではない。518 バイトは書きすぎだと思うので無駄に難しくしてる可能性あり。■■■一日経ったので(86問目)>提出 #24040292 (AC / 518 Byte / 217 ms / 同じ内容)。てっきり掃き出し法のように干渉する条件をうまくまとめて数えるのだと思った(結局ビット列を列挙して条件列でテストにかけているあたり、自分がうまくやれているとも言えないが)。