2021年08月14日 (土) [AtCoder] 今日は ABC214。D 問題 Sum of Maximum Weights がそこそこ難しかったみたい。自分はといえば、１時間ほど書いては消してを繰り返して、とうとう Union-Find にたどり着いた。UF を除けば入出力を入れてもたったの４行だった>提出 #25051751。このシンプルな解答に至る道筋が見えにくかった。キーワードは競プロ典型 90 問の 39 問目「Tree Distance（★5）」に対する「答えへの貢献度を考える：主客転倒」だと思う。貢献度を考えるためにソートする手順がある。Ruby での提出を見ると、水色の４人はさすがの瞬殺だった様子。自分は緑だったのでしゃーない、そんなもんだ。■ E 問題も同じように何か見抜くべきからくりがあるらしいんだけど(Tweet)、解けてはいない>提出 #25061393。２択で４分の３間違えてるんだから、ある意味４分の３正解しているのでは？(375 点ちょーだい)■■■@2021-08-18 今日解いた「ARC029-C 高橋君と国家」(提出 #25133976)。Sum of Maximum Weights が水色前半なのに対して、高橋くんと国家は青色後半。自分としては同じくらい難しいと思うので、知識が行き渡って参加者のレベルが底上げされてる結果だと思うんだよね。厳しい。
2021年08月12日 (木) 今日、雑談の中でマイツールというソフトウェアの名前が出た。最近どこかで目にしたなと思っていたら、お風呂で判明した。数日前から読み始めた『べてるの家の「非」援助論 : そのままでいいと思えるための25章』(べてるの家 (著)/浦河べてるの家 (著) / シリーズケアをひらく)の最初のページに MUG 日高という集まりの名前が出てきていた。日高における Mytool User's Group の略である。そこで書かれているのは 1991 年の出来事だから、30 年後に何の偶然か Mytool という単語が自分の目の前で衝突したということになる。そんなに広く日本全国で使われていたとでも？
2021年08月09日 (月) [AtCoder] 昨日の ABC213。前回が３完だったので今回は E 問題まで解けて良かったんだけど、E 問題を提出したのがコンテスト終了から６分後だったのだよね>提出 #24891967。１発 AC なのが余計に悔しい無念の４完。■どこかの週記で E 問題が 01BFS だと読んだ。名前だけは知っている！「01-BFSのちょっと丁寧な解説 - ARMERIA」実装の練習をして次は時間内に……。幅優先探索とダイクストラ法の中間みたいな位置づけなのか。両端キューの先頭から処理を開始して先頭なり末尾なりに要素を追加するっていうけど、そのあと処理をどう継続するのかがよくわからなくて実装が見えないんだよね(だから名前だけを知っている状態)。えっと、デックをイテレートしようとするからわからなくなるのであって、空になるまで shift を繰り返すみたい。■例題に挙げられている「器物損壊！高橋くん」は先月解いていた>提出 #24378783。しかしこれも 1.8 KB 書いていてかなり時間をかけたはず。たしか連結成分を列挙してから２回、塀を壊しての連結成分のマージを行った。結局 01BFS って、固有の実装テクニックがなくてもなんとかなるのでは？ だけど早く書きたいねえ。
2021年08月08日 (日) はやってるらしいのをやった>Congnitive。結果>png>link。■歪みが強いのは「選択的抽出 〜良い面を無視して悪い面だけを捉える考え方〜」１つだけ。うんうん、バランスがとれているってことだ(自賛)。■中くらいの歪みは８つ(スコア順)。「問題回避 〜責任や面倒な物事から回避する信念〜」「否定的予測 〜将来に対して悲観的な予測をし、それが必ず現実になると思い込む考え方〜」「破局視 〜あるひとつの出来事で、破局的な見方をしてしまう考え方〜」「感情的理由づけ 〜自分の直感を事実だと決め込む考え方〜」「過度の一般化 〜一部をとりあげて、全体に適応させる考え方〜」「協調主義 〜全体の幸福があってはじめて個人の幸福があるという信念〜」「恣意的推論 〜根拠もないのにあれこれと思考を巡らせて結論づける考え方〜」「肯定面の否認 〜どんな出来事でも「悪い出来事」にすり替えてしまう考え方〜」■当てはまらないのは「誤ったレッテル」「倫理的非難」「誇張と矮小化」「外的無力感」「全か無か思考」「自己関連づけ」「抽象的な質問」「内的無力感」「自己期待」「断定的思考」「依存」■当てはまる方も当てはまらない方も、さもありなんといった結果。最悪を予測しておけば現実はそれよりマシなはずだし(「選択的抽出」「否定的予測」「破局視」「肯定面の否認」)、物事をなんとかできると自分を恃みにできるスーパーマンではないし(not「自己期待」)、だけど根っこのところで根拠のない楽観思考を持っていて備えが甘い(無責任)。事実と異なることが大嫌いで(not「誇張と矮小化」)、枠にはめられることも大嫌い(not「誤ったレッテル」not「倫理的非難」not「断定的思考」)、だからやらない。だけど思い込みの強さ(「感情的理由づけ」「過度の一般化」「恣意的推論」)からの誤りは不可抗力じゃないですか？ あとは「依存」傾向がゼロなんだけど、卵が先か鶏が先かはともかくとして、必然ではあるよね。頼り頼られる関係がない。関係が存在しない！ あとまだ出てきてないのは「協調主義」。たとえば仕事のうえで面倒の総量が 100 あるとして、自分の面倒が 20 減った代わりに他人の面倒が 20 増えたのでは何も変わっておらず、たとえ自分の面倒が増えたとしても面倒の総量が減るのが正しい、という考えはある。■ここで「正しい」という言葉を選ぶのが自分という人間であるが、そこには落とし穴がある。まるで主観ではなく客観ですよみたいな顔をして自分の価値判断を他人に押しつける理由にすると戦争を生む。目立った傾向は見られなかったけど「倫理的非難」や「断定的思考」に至る罠。正しさは常に批判し続けなければいけない。■俺が「定石」って言葉を嫌うのがまさにこれ。「定石だから」なんて言い草は「正しいから正しい」「みんながそう言うから正しい」なんてのと同じで、議論の材料にはならない。デザインパターンが定石集みたいなものだけど、そのカタログは「こういうときにはこれを使う」という形式では書かれていない。読者が複数のパターンを比較考量して最適な判断を下すための材料を提供しようとしている。
2021年08月07日 (土)
「読解力より、音読み単語｜shinshinohara｜note」から「速度はみんな速さに読み替えろ！距離は遠い近いと読み替えろ！その上で、足の速いやつ、遅いやつ思い浮かべて考えて見ろ。ほんなら間違えにくくなるから。
」■揚げ足を取るつもりもないしょうもない話。たしか自分が中学生だったときには、「速度」と「速さ」に使い分けがあった。負になり得るのが速度で、常に正の値しか考えないのが速さ。だから読み替えちゃうとちょっと不都合があるな、と。まあ、それ以前の段階の子供の話らしいけど。
2021年08月06日 (金) 今日知った用語「差し込み印刷」■Word の機能で、Excel の表などから特定のフィールドを埋め込むテンプレート機能。Tabular Data Control とか XSLT でやるアレ。Shadow DOM はわからない。Excel なら当然だけど、Word にそういうデータ連携機能があるって知らなかったな。(同じく知らなかった人が古から伝わるテンプレートを破壊(直タイプ)して消えたみたいな経緯だとおぼろに理解している。今日の話)■埋め込みフィールド(MERGEFIELD フィールドコード)に暗号のようなパラメータを与えてカンマ区切りにしたりできる。埋め込まれた結果の数字や文字列にスタイルを指定しても無駄。パラメータとして与えるフォーマット文字列にスタイルが設定できるのには驚いた。たしかにそれが Word の機能であり、みごとな応用だと思う。
2021年08月05日 (木)
新聞に載っていたというどこかの市長のコメントの一部「ご迷惑を掛けているのであれば、ごめんなさい
」■最近読んだこれの一種かなと思った。「「謝らない謝罪」が日本で蔓延している｜ニューズウィーク日本版 オフィシャルサイト」 市長さんに聞きたい。で、あなたは迷惑をかけたと思ってるの？ 思ってないの？ A⇒B という型の命題において A が成り立たないなら B の内容が問われないとは最近目にした話題>20210518。内容の定まらないどうでもいいコメントを出したよね(全文を知らないでこう書くのは早計だけど、ま、気楽な立場です)。
2021年08月02日 (月) 「高性能エアコンの「サーモカメラで気温の高いところを冷やす機能」、食事を勝手に冷やしたりキッチンの温度を破壊する困り事があるらしい - Togetter」■へー、そんな(アホな)機能が。エアコンについて書いたのはもう８年前だった>20130627。俺は小賢しい道具より馬鹿でも素直な道具が好きだよ>20181102, 20180825, 20150410, 20191208, 20181118。だから補完機能はありでもオートインデントやオートコンプリートや自動整形は耐えられないんだな。■使用しているカレンダーアプリが、登録した予定の開始(終了)時刻を修正すると玉突きで終了時刻や後ろの予定の時刻をずらす。たしかにぴったりはまれば「わー便利ー」な機能だろうけど、そうでない状況ももちろんある。問題はそういうとき、機械が黙ってやるお節介が人間を謀るところにある。修正してない予定が知らん間に狂ってるんだから。でもこういうのを許す、奨励する文化がスマホ(に限定されない時代？)にあると思ってる。そして嫌ってる。
2021年07月31日 (土) [AtCoder] ABC212。D も E も F も、制約が厳しかった。ABC3完ですよ。配列を使ってソート列を伸ばしていくのは良くない。それはわかっているが道具が見つからなかった。TLE×1 で終わった D 問題はプライオリティキューの出番だったのだろうか、ということに今になって思い至るあたりどうかしてる。しかもそれでも４完なのであり、８問体制なら５、６完を狙いたい。なのに３完……。もうダメだよ。■まーた緑大好きムーブが発動しちゃったか。逆Vの字で落ち込むのはもう何度目だろう。ARC で負けても持ちこたえるために ABC ではレートを蓄えないといけないのにな。
2021年07月24日 (土)
[AtCoder] 今日の ABC211-E Red Polyomino。K マスの連結な形を列挙して照合するのかなと思って、時間的には間に合うみたいなんだけど(サンプルの３が最大ケースだよね)、答えが合いません。■ C 問題が競プロ典型 90 問の 008 - AtCounter（★4）そのままだった。同じ文字が２回現れるというようなひねりくらいあるかと思って何度も chokudai の文字を眺めたけど、どの文字も１回しか出てこないのだった。■E 問題。C1 の初期化を見直したらサンプルの３が合ったので提出した>提出 #24521210 (1 WA)。なんでだよー。■やった！ 提出 #24522032。さっきの提出でもまだ C1 の定義がテキトーだった。たとえば N が 3 で K が 7 のようなとき、中心部分を塗らない形があるのに考えられていなかった。■N.times.with_index((N+1)*(N/2)){|i|...} とか謎なことしてる……。結果的に不要な考慮だったので無駄だけど問題なし。
2021年07月21日 (水)
最終更新: 2022-02-17T12:53+0900
♪ [AtCoder] 第七回 アルゴリズム実技検定 過去問
第四回までの日記>20201111p01。
課金ユーザーじゃなくてごめんね。@atgolfer1 に流れてきたツイートを見てはじめて問題が公開されていること、第七回が行われていたこと、終了していたことを知ったよ。
A - チェックディジット
やるだけ。提出 #24382962
B - 蒸気圧
小さい方を選ぶだけなんだけど、10 分以上切り捨てたり余りを取ったりして悩んでいたのは内緒。提出 #24383193
C - 入力チェック
Ruby なので 10 進 100 桁はなんの障害でもなかった。提出 #24383281
D - 書き換え
５つのパターンをじっと見れば最終結果に影響するような文字の取り合いがないことがわかる。提出 #24383341
E - 青木君のいたずら
探索が許されていることと操作が１回に限られていること、それと遷移が足し算ではなく掛け算だという点が違うけど、問題の形としては ARC122 の C 問題 Calculator を思い出した>20210612p01.03。これが解ければ ARC122-C も解ける！
F - ダブルブッキング
スケジューリングの問題だけど、求められているのが最適化ではなく判定だという点で、最も簡単な部類。提出 #24383711
G - べき表現
20 分考えた。
どんな正の整数でも、テキトーに選んだ正の整数を基数としてその冪乗の和で表せるのは当然だけど(N 進数ってそういうもの)、使える数字が 0 と 1 と -1 に限定された 3 進数ではどのように事情が異なってくるか、という問題。
2×3^x = 1×3^{x+1} - 1×3^x
という感じで、2 を -1 に置き換えてから次の桁にツケをまわしていくのがいいでしょう。提出 #24384055
H - 折れ線グラフ
解けてないよ。制約が小さいから探索していいのだろうけど、それでも 100 の 100 乗になるようなバカな探索は許されない。私はバカです。
@2021-11-15 TLE→AC
上限の揃った制約が DP だと告げている。それも３乗の。まだ８問目だからって雑な探索で解けるとなめてかかっていたのではないか？
- 提出 #27281059 (TLE×4) 腰を据えてもこれである
- 提出 #27281255 (AC / 476 ms)
なだらかな折れ線グラフを書きたいのだから、遷移先の幅は自ずと限られる。(W = A.sum/[N-2,1].max+1 -2, +1 はテキトー)
I - ほくろ
「ABC-D 虐殺三銃士」のひとつ「Congruence Points」を思わせる問題だけど、両目の位置を手がかりに確定した情報が得られるところが優しい。
図形問題は行列や複素数に計算を丸投げしがちなので、これは自分で式を書いた。25 分かかった。提出 #24392172
J - 終わりなき旅
「強連結成分分解をしよう」がキーワードだった競プロ典型 90 問の 021 - Come Back in One Piece（★5）がすぐに思い浮かんだんだけど、深さ優先探索を２回するんだというアルゴリズム解説は何か所かで読んでたんだけど、これは 17 問ある★５問題のうちで解いてない３問の１つなのだった。
雰囲気は掴んでいたので雰囲気で書いた。提出 #24393748。細部が詰められてなくて無駄があるかも。競プロ典型 90 問のおかげでアルゴリズムの顔見せだけは済んでいたので、今度は実装するところまでこぎつけた。
K - 急ぎ旅
理解が甘くて 1 TLE。実装ミス(< にすべきところを <= にしていた)で 1 WA。AC はこれ>提出 #24424698。
最短経路問題ならダイクストラ法なんだけど、満足度と所要時間の２つを考えなければいけないのをどう考えるか。所要時間が最短であることが第一で、満足度の高さはその次に考慮すればいいだけなんだけど、だけど、「満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません
」という文言がちょっとひっかかるよね。経路を記録して重複を排除しないといけないの？(それには無視できないコストが……)
もちろん負の移動時間はないから、同じ都市を２度訪れる経路が最短になることはない。だけど次の２つのようなパスで所要時間の合計が同じになる場合をどのように扱うか迷った。
都市 M に着いたときの満足度の総和は明らかに２、３、４を経由してきた経路の方が大きくなるんだけど、もう一方の経路は M のあとで７、８、９を経由することで取り返すことができるかもしれない。M に着いたときの満足度の低さを理由にして一方のパスを捨てていいのかどうか。
実は上の図には嘘があって、上の図のような状況の実際は下のようになっている。
これは１と M とのあいだの最短所要時間と、M と N とのあいだの最短所要時間がどちらも１つの値に決まることからわかる。最短経路であるどの２つのパスを取り上げても、分岐と合流を繰り返す第３のグラフのような関係になることが納得できたら、ある都市に最短で到着する経路のなかから最大の満足度を記録するのでいい。
L - たくさんの最小値
セグメントツリーなんだけど、最小値を持っているインデックスをどうやって列挙するかという問題。
最小値の記録と添字の記録をセグメント木と配列で分担しようとして TLE を出したり(提出 #24408482)、セグメント木の実装ミスで大量の WA を出したりしつつ(提出 #24412768)、三度目の正直で AC>提出 #24413254。
セグメント木を上から下に下るのって苦手。(根っこが上です。逆にすると頭が働かない)
M - 分割
全部を分割した状態から始めて、損をしない範囲で統合していくのかなと思ったけど、並べ替えができなくて境界が入り乱れるのを、どう整理して扱えるのかわからない。
とある赤亀コーダーさんによると全体でこの M が一番難しかったらしい。
N - モノクロデザイン
昨日これの簡単なバージョンを解いたよ>「B - すぬけ君の塗り絵 2 イージー」(提出 #24414821)。
二次元累積和かなと思うんだけど、ABC203-D Pond も競プロ典型 90 問の 081 Friendly Group（★5）もまだ解いていない。二次元累積和って累積和の累積和とは違うんだなー、という感想を持ったのは覚えてるけど、よく思い出せない。
O - コンピュータ
O 問題が解けたのは初めて。
入力を圧縮したり累積を記録したりして計算量を削減するのは、競プロ典型 90 問の 089 - Partitions and Inversions（★7）ぽいなーと思った。
以下は考えたこと。
- ある B より後ろにあって、前にある B と同じかそれより小さい B は無視できる。
- だから N 個の入力は、B の増加列といくつかの A を足してまとめたもののペアとして圧縮できる。
- 最終日までに得られる報酬の総額は決まっている。コンピュータに支払う金額をどれだけ減らせるかという問題。
- 十分な資金があるなら明らかに B の最大値と同じ値段のコンピュータ１つだけを買うのが最適。
- しかし資金が足りない場合は目の前の障害(B)を超えられるだけのコンピュータを買って、目先の報酬を得るようにしなければいけない。
- なんですかね、貧しさ故に最適な選択ができないって、現実ですか。保険とか追証とか宝くじとか。
- 複数の買い方。障害(B)が１、２、５、６、９と並んでいるときに、１を買って５を買って９を買うのがいいか、２を買って６を買って９を買うのがいいか。局所的な判断では決まらないので貪欲法は使えない。
- 迷うたびにキューを伸ばすと爆発するので DP っぽいなー。
- N^2 のループは許されていないので、すべての i についてそれより後ろにあるすべての要素を処理対象にすることはできない。
- i<j<k とする。コンピュータはできるだけ買わないのが正解だから、ある i と j がともに k にある障害を越えるというとき、j から k への遷移が i から k への遷移より得するということはない。
- i を通過する時点ですでに k を超えられるだけのコンピュータを買う資金があるのだから、到達地点が同じ k なら j で足踏みする価値がない。
- j で足踏みする価値は k より遠くへ(k を超えて一足飛びに)到達できる可能性にある。
- という感じであとはがんばってコーディングする。提出 #24429839
.each_with_index.eachとか謎なことしてる……。幸いにしてこれは無駄なだけで害はないけど、部分的な修正を繰り返すとこういう風に、(通して書き下したときにはありえない)謎なバグを仕込みがち。
2021年07月18日 (日)
最終更新: 2021-07-19T22:56+0900
♪ [AtCoder]AtCoder Regular Contest 123／C 問題 1, 2, 3 - Decomposition (+ B + A)
悔しいなあ。手も足も出ない方がまだあきらめがつく。
提出 #24373137 (WA×20 / RE×12 / AC×2)
１時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、５つあるケースの最後の１つの答えが違っているのに気がついていなかった。ダメダメである。
RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。
Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう１か所(b+(d-1)%10 の %10 が完全に余計)。
プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。
答えの上限が５だと見抜いていたところは偉いと思うんだ。なぜ５かといえば、項数が１ならある桁に関して作れる数字が 1..3。２なら 2..6、３なら 3..9、４なら 4..12、５なら 5..15 ということで、最初に 10 種類の数字が作れるのが５項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。６以上に項数を増やしてもできることは増えない。
提出 #24375535 (AC)
ほとんど違いませんよ。でも A から F まで６問ある中の３問しか相手にしていないのに、時間内に完成させられないんだなあ。
実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。
B 問題 Increasing Triples
ただの貪欲。提出まで 15 分>提出 #24363550
A 問題 Arithmetic Sequence
AC まで 2 WA、33 分。どういうこと？ 10 分時点で９割５分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き！(知らないわけではない。括弧と波括弧に使い分けがありそう？ それは知らない)
AC>提出 #24361099。ほとんど違いませんよ(２回目)。
2021年07月17日 (土)
最終更新: 2022-01-25T19:28+0900
♪ [AtCoder]AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)
A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。
提出 #24322478 (RE×11 / AC×19)
30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。
提出 #24337207 (AC / 273 ms)
複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。
D 問題 National Railway
DP です。１行目から行ごとに考える。
- ある行について。処理済みの地点に建てた駅からこの行この列に至る最小のコストを記録することにする。
- その次の行にて。各列 Aij の費用を払って駅を建てたとする。前の行の j 列に記録されたコスト(の先にある地点)をもうひとつの駅として、建設費用を計算する。
- 建設費用の最小値が答え。
罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。
提出 #24314328 (AC / 559 ms)
m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。
その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。
ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。
」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています
」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。