/ 最近 .rdf 追記 設定 本棚

脳log[2020-08-20~]



2020年08月20日 (木)

最終更新: 2020-08-24T19:08+0900

[AtCoder] AtCoder Beginner Contest 175D 問題 Moving Piece

コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出

 最初の提出 #15953114 (RE / TLE)

バグが2種類あったけど方針は間違ってなかった。

 バグ1:K が各巡回グループ(配列 A の要素)の要素数より大きいときの端数(K%A[i].size)の扱い。

巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum 1個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。

RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。

 バグ2:1以上 K 個以下の連続する部分数列のうち和が最大となるものの求め方。

バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。

 最初の AC #16057773 (729 Byte / 77 ms)

やっとバグ2がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。

こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。

 Ruby によるすべての提出(実行時間昇順)

現在の2番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。

理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)

普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の3倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。

ss[l] が回路全体のスコアの和。0...l の範囲の1点を始点にして長さ k(+1) の部分列を切り出す。k = mi[K, l + K%l] だから、最大で [l-1+(l+l-1)+1] の要素にアクセスする。長さは 3l 必要。 ma[0, ss[l]] によって回路全体のスコアの和が正か負かの場合分けを省略している。

Array#max を分岐と見ることもできるかもしれないけど、場合分けをしてそれぞれに固有のスペシャルな式を書くより、Array#max, Array#min を含んでいようとも1つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)

そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。


2020年08月18日 (火) ソニーストアはXperia SIMフリーモデルのご購入をしっかりサポート!」だってさ。とても良い。アマゾンで香港のストアからグローバルモデルを買うしかなかったけど故障したときが不安、というのに応えてくれるといい。Xperia 10 から買い換えるときまでやっていてほしい。


2020年08月14日 (金) 『なぜ左利きはボールペンが書きづらいのか』を図解「ボールペンってこういうものなのかと思ってた」「どいつもこいつも右利き用」など共感の声 - Togetter」■つい数日前に銀行でふと見かけたぎっちょの人が、手首を鉤のように曲げて書いているのを不思議に思っていたところ。紙を削っちゃうからそうなるのね。


2020年08月13日 (木) 知り合いとか知り合いの知り合いくらいの人がなるべく多くの人に届けたいであろうツイートはRTしているが、「拡散希望」って書いていると一気に絶対やらないという気になる。なぜかはよくわからない」■自分は YouTube 動画の冒頭末尾の定型文句は様式美として嫌いではないけど、たぶんブックマークしてる投稿者の人柄込みでそういう評価なんだけど、拡散希望から受ける印象はまるで異なる。発端となったツイートの事例からはあなたに知ってほしいという利他の気持ちが伺えるが、拡散希望からは邪悪な意思を読み取る。邪悪というのはたぶんに主観的な評価で、数を募る、数を頼みにする、数を力に変えようという意図が、自分の価値観とは決定的に相容れない。だから拡散希望は邪悪。


2020年08月11日 (火) [Xperia 10] だいぶ後回しにされていたが今日 Android 10 が降ってきた。あまり変わってなくて満足(←そういう評価)。さしあたり気がついた相違点は3つ。■1.いたわり充電が学習に基づいたブラックボックス動作のみから、手動でパターンを設定できるようにもなっていた。20190518p01.06に書いた通り。誰でも考えるってことだ。■2.STAMINA モードを「常用」していたのだけど、そうすると勝手にダークモードになるようになった。ダークモードは常用しないので STAMINA モードもオフになった。バックライトの強弱と比べて画面の黒白にユーザーの好みを上書きして正当化されるほど意味のある差があるか? 有機EL ではなく液晶だぞ。■3.Android の仕様だと思うけど、画面上部に常駐するステータスアイコンが飾りになった。何のアイコンなのか説明しないし反応もしない。場所を占めるだけの模様になった。20200513にスクリーンショットを貼り付けた画面にアクセスしにくくなったし、そもそもバッテリー画面からあの残量遷移グラフがなくなっていて有用性が下がった。点々メニューの中にはあるのか知らんけど、見えないものは存在しない。隠して平気な顔をしていられるなら最初からいらないものだったんだ(必要だから最初から見せろと言っている)。■エキスパートモード(一部の設定やメニューを隠すこと)は役に立たないとマイクロソフトの人が書いている。結局のところそれらは必要があるから存在しているのだし、何が必要かは人による。何を隠しても誰かを欺くし、ある意味で誰もが何らかの項目が見つけられなくて欺かれる。■4.アラームの通知が制御できなくなった。持ち主の意向を無視する何の特権があるってんだ。どうでもいい通知が紛れてくるなら、あらゆる通知がどうでもよくなる。通知なんてそんなもんだ。ただのきっかけを与えるに過ぎない。しかしそれは極論であって、あると便利な通知もある。だが制御できないならすべて視界から消えろ。■5.色彩がきつくなった。もともと妙な強調はオフにしていたのだけど、そのオフの設定での色調がきつくなった。


2020年08月04日 (火) 1年目に片付けて9年間その状態を維持するのと、9年間散らかしたままにして10年目に片付けるのと、かけた労力と最終結果が同じでも9年間の QOL がまるで違う。これが(改心した)片付ける者の考え。散らかり度合いの上げ下げで労力を計り、時間軸の積分で QOL への悪影響を計る。一方で片付けない者に片付いた状態は永遠に訪れないので、比較が意味を成さない。■右折でどこかに入りたい車が対向車線を塞いでいる状態もこれに似ている。1台目が譲るのと100台目が譲るのでは、譲った側の車線のスローダウンが同じでも、対向車線がストールしていた時間がまるで違う。職業ドライバーは自分が苦労するからか全体最適をよく考えていると思う。


2020年08月03日 (月) Ruby には商と余りを同時に求める Integer#divmod メソッドがあるけど、それを q,r = 7777.divmod(101) みたいに多重代入で受けると、多重代入が遅いせいで(20200428p01.08.01)密かに期待するパフォーマンスメリットが相殺されてしまう罠がある。

最終更新: 2020-09-03T17:14+0900

[AtCoder] AtCoder Beginner Contest 174C 問題 Repsept

時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。

解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。

 提出 #15651178 (AC / 306 Byte / 136 ms / 14428 KB)

 提出 #15663806 (AC / 294 Byte / 118 ms / 14508 KB) ※無駄を省いて整理したもの

布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。

たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか

うん、これが解らない。

K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列7の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。

でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。

 Ruby によるすべての提出

他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え? 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの? (※桁が大きくなりすぎるので余りにだけ注目する必要はある)

たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に2回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。

 「おかしなこと」の説明をば

  1. 与えられた K の1の位の数字を見る。
  2. 1、3、7、9なら掛ける数を(1から9から)選べば1の位に7が作れる。
  3. 作りました。1の位の7はもう無視します。(K にある数を掛けてできた数の)1の位ではないところに7か7ではない数字が残ります。
  4. 次はそれに、K に(0から9の)何を掛けたものを足せば末尾に7が作れるかを考えます。
  5. 以下3へループ。
  6. 3から5は要は K に何を掛ければ7の列になるのか、1の位から順に決定していこうという手順。筆算をイメージしながら。
  7. たぶん、運が良ければ、もしくは不思議な法則に従って、掛けてできた数字のどの桁も7になることがあるでしょう。
  8. 全部で7がいくつ作られましたか? というのが答え。

 「7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた」

「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。

 逆元?

この問題の2つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。

(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……

公式解説は累積和だね、横一列を1回の掛け算で済ます方法

僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた

抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う

* この提出はお仲間かな。 https://atcoder.jp/contests/abc174/submissions/15654939

本日のツッコミ(全2件) ツッコミを入れる

nishio「循環ルートに入る」=「kの1の位が偶数か5」ということみたいです、追記しました。

ds14050お知らせありがとうございます。しかも代わりに考えていただいて^^。 循環する場合に「B-AはKの倍数」からの「..


2020年07月29日 (水) バッチファイルってどうやら実行中に内容の書き換えができる。現在実行中のコマンドの次の行に新しくコマンドを挿入したりできる。先読みとかないし、書き込みの禁止もない。


2020年07月27日 (月) リツイートとトリミングと権利の侵害の話。最高裁上告棄却。新聞の見出しから受けた印象とは裏腹に、記事を読めばトンデモとは思えなかった。■転載禁止の写真をツイートしたのが悪の根源。ではそのツイートをリツイートして転載禁止の画像を URL としてではなく見える状態で拡散した者の責任は? 悪人を一人挟むだけで、数や実際に及ぼす影響力の点で権利者の権利をより大きく踏みにじりかねないリツイートを行った者の責任が消えるのか?■クリックすれば権利表記を含む画像の全体が見えるというのなら、リツイートをした者が、リツイートをする前に権利表記と転載禁止の文言を確認してリツイートをやめる分別を見せるべきだったろう。「クリックすれば」は通らない。■フェイクニュースの拡散など負の側面が話題になるなかで、リツイートが無節操に後押しされるべき行為だとも思えない。一人なら無力であり無知であっても目こぼしが可能かもしれないけど、数が集まれば力になり暴力ともなる。ツイッター社に考えさせるのがいいのでは。■■■批判的。「リツイート行為と著作者人格権最判令2.7.21(平30受1412) - IT・システム判例メモ」 知らなかったのだけど、「原審では,リツイート行為について,複製権侵害,公衆送信権侵害を否定」していたらしい。この結論は変わっていない。転載禁止をツイートするのがダメだとして、リツイートはその限りではないと。その代わり「最高裁では,このうち,氏名表示権侵害の点について主に判断された。」■その判断に関わってくるのがインラインリンク、直リンクとかいう、定義が紛糾しそうな概念。「インラインリンク(直リンク)と著作権侵害 | デライブ知的財産事務所」■20世紀のインターネットではバナー画像の直リンク(IMGタグのSRC属性にオリジナルのバナー画像ファイルのURLを指定して、バナー作成者、バナー置き場のサーバーに負荷をかける行為)を戒める文言がよく見られ、宣伝に協力する者は自分が管理するWebサーバーにバナー画像をコピーして、Webページに画像を埋め込むときにはそのURLを呼び出すことが求められていた。■このような価値観になじんできたので、他人のサーバーに置かれた転載禁止の画像ファイルを、自分が作成するWebページに埋め込んで表示した場合、これは複製して表示するよりも悪質度が高いと考える。もし、他所のサーバーに置かれた画像を直に埋め込むことで何らかの権利の侵害行為を回避できる、責任を逃れられるという判断が為されるとしたら、これほど有害なことはない。同じような理屈でリツイートにある種の責任がないと判断されるなら、これもまた有害であると考える。■知財高裁も最高裁も問題を正面から捉えていないと思えるし、判断の根拠が誤っていると思う。画像のビット列がどのサーバーからどのサーバーを経由して送信されてくるかは事の本質ではない。それってストリーミングかローカルキャッシュかみたいなクッソどうでもいい議論と同じでしょう。■つまるところ、判断の向いている方向は間違っていないと思うけど、裁判所が駆使するテクニカルな部分が現実から乖離していてナンセンスだから、結論を支持したくない。


2020年07月26日 (日) [AtCoder] 昨日は ABC 級の「M-SOLUTIONS プロコンオープン 2020」があった。パフォーマンス 1683 でレートが 83 上がって Highest を更新したが、あまり喜ばしいことではない。というのも、昨日の自分が一皮むけた結果というわけでは全然なく、いつも通りの不甲斐なさを味わっていたからだ。では何が違ったか。コンテストの(自分より優れた)他の参加者が自分同様に E 問題、F 問題が解けなかった(だから提出の早さを評価する上限が高くなった)というだけのことだ(たぶん)。臨時ボーナスをもらったみたいなもので、自分は何も変わっていない。■E 問題。手を抜くと WA になり、総当たりすると TLE になる。制限時間がいつもの2秒でなく3秒であり、N の上限が 15 と相当に控えめであることから、想定解法の複雑度はかなり高いと考えられる。Ruby で工夫のない総当たりをすると N=10 と 11 のあいだに TLE の壁がある。2^20(=約100万) と 2^22(=約400万) の違い。N=15 が遠い。解説はまだ見たくない。しかしこれがヒントか。@chokudai「E、自分だったら4^Nと3^N区別したくないからめちゃゆるい制約で出すんだけど、Writerが調整めちゃ頑張ってた。」 いやでも 3^15(=約1400万) は手の抜きどころがないと Ruby では無理だけどね。■(お風呂にて) ポイントごとに縦・横・無の三択の総当たりということなのか。そうなのか。ポイントの数と同じだけの直線を選べば確実に S が 0 になることを踏まえれば、あるポイントに縦か横の直線を引いたあとは他のポイントに注意を移していいわけだ。■TLE の壁が N=12 と 13 のあいだに移動した雰囲気。3^12(=約53万) と 3^13(=約160万) の違い。■結局 C++ で書いて TLE を回避しても MLE と WA になるという。ただの総当たりなのにな。WA になるテストケースがないとデバッグが捗らないよ。■■■@chokudai「作問窓眺めてみたら、「大きいと書かれてますが同じの場合はどうなりますか?」みたいな質問が来るので、「真に」をつけてみたけど、今度は「真に大きいとはどういうことですか?」って質問が来てる、みたいな感じの流れだった twitter.com/yamasaKit_/sta…」 問題文を読んでいてちょっと引っかかった表現だった。「真に」が自分の知らない専門用語であり、わざわざ書くからには明確に画された無視できない定義があるのかと疑った。自分は「同じかより大きい」という表現をある時点から知っており、そこから「より大きい(more than)」がイコールを含まないことを覚えていった。「真に」というのが謎用語だったのなら、ある語(「より大きい」)の定義を他の語(「真に大きい」)に丸投げしているだけであり、そういうこと(循環定義)は国語辞典でときどきあるみたいだけど、説明しようという親切が伝わらないものになっていると思う。■■■@2020-07-29 E 問題。綱引きにおいて 1×22×1(1×1)+(1×1) の中には仲間外れがあるんだけどどれも一緒くたにしていた。最初によく考えて当然の前提としていたところにこんな見落としがあっちゃあ答えにはたどりつかねーよ。


2020年07月18日 (土) 何故お役所ってオワコンIEが大好きなの?|楠 正憲(国際大学GLOCOM 客員研究員)」■ブラウザにインフラがないのは知ってた。頭のいい人が正しいが機能しないやり方でやろうとしてるのも薄々知ってる。日本人(国民と消費者)って採算とかリスクとかまるで度外視するよね。とりあえず不完全でもやってやろう、では済まさないよね。■関連「国政選挙のインターネット投票はなぜ解禁されないのか?若者の投票率の低下を解決することはできる?|本日もトントン拍子」「[B! 選挙] 高梨ひひひ on Twitter: "いやまじで、どんなに技術が発達してもネット投票は基本的に無理なんです。 上司が後ろに立ってて、「じゃあ今から目の前で⚪︎⚪︎さんに投票してね」ができちゃうんで… 効率性とか技術力の問題じゃないんです。"


2020年07月14日 (火) 形式的べき級数って聞くと「何それ怖い」しかないんだけど、formal power series って聞くと、「累乗の、連なりの、一般形? う……ん、ちょっとだけならどうにかなるかも」という気がしてくる。錯覚だけどな!


2020年07月13日 (月) fujisan.co.jp を何度か利用しているが、今回初めて良くないふるまいを身につけていると思った。自動継続とメールマガジンのオプションだ。自動継続オプションは購読確定画面とそこまでの経路にはなく、別画面に、デフォルト ON の状態で隠されていた。選ばせる気がない。お知らせ(宣伝)メールのオプションは確定ボタン下方の画面外に配置されていた。購読確定前に選ばせる気がない。下を見て右へ倣えで自ら落ちていくんだろうか。