Atcoder-ABC150-D 1/n

abc150 D　導順

問題抜粋

入力　偶数N　整数M　偶数からなる正の整数列A=a1,a2…

任意のk(1<=k<=N)に対し，正の整数である半公倍数Xの数を求める問題

X=ak*(p+0.5)　pは負でない整数

1以上M以下のXの数を出力する

入力例

2 50

6 10

出力例

2

＝PLOT＝

int n,m;

int a[n];

for (i <=0; i <= n; i++){

scanf(“%d”,a[i]);

}

除算した際の余りが0ならcount++;

X=ak*(p+0.5);

for (p = 1; p <= M; p++){

}

共通の公倍数を求める問題の場合

6,10 - 30

両方ともに倍数かけていき、一致した場合カウントするでいける、ただし計算量

D.SemiCommonMultiple writer : yuma000)

XがAの半公倍数である条件は、以下のように言い換えられます。

• 任意のk（1≤k≤N）に対して、X＝（az/2）＊（2p＋1）を満たす負でない整数pが存在する。

Xがan/2の奇数倍であることから、これは以下のような二つの条件に分割できます。

•   任意のk（1≤k≤N）に対して、Xは an/2の倍数である。

ここまでは問題なく理解

•   任意のk（1≤k≤N）に対して、Xが2で割り切れる回数と ak/2が2で割り切れる回数は同じである。

2p+1が奇数で2では割り切れないから、2で割り切れるかどうかの判定はak/2で判断できるということ

aiが2で割り切れる回数と ajが2で割り切れる回数が異なるようなi,jが存在するとき、条件を満たすXはありません。

そのようなi,jが存在しないときについて考えます。

例えば数列4 5 の場合、ai/2がそれぞれ2,2.5で後者は2で割り切れないので両数の間で半公倍数Xは存在しない.

６と10は2でそれぞれ1回ずつ割り切れるので

Xが存在する

a1/2,a2/2，..，aN/2の最小公倍数をTとします。すると、Tを奇数倍したものが条件を満たすので、条件を満たすXの個数が求まります。

そもそもこの問題の出力が最大公倍数または最小公倍数を求める問題だった場合どうなるか、

最小公倍数は素因数分解して指数の大きい方の数同士を掛け算すると求められる、

5=5x1 6=2x3 7=7x1

最小公倍数は2x3x5x7=210

素数の平方根の整数部分もまた素数

下記提出した回答

吐き出し 1/n

頭の中に溜まってきたので吐き出す

１ヶ月以内に実現？

• 認定整備済Mac book Air M3、SSD512GB、でもなぜM2じゃだめか？このスペックが必要な理由がない…
• 身の回りのものをコンパクトに、もしくは手放しサブスク化(特に車)

中長期

• IT系資格、情報工学、もしくは個人開発で自分の理想とするソフトを実装し公開し続ける
• 新居周囲でかかりつけ医見つける(内科外科、歯、目)
• 新しいスパイク欲しい、アディダスのトラックスパイクが欲しい
• トラックレース出る100、400かな
• Benqディスプレイ、フリマ出品
•  

休日

角砂糖のような真四角の空間に何時間も閉じこもって

何をするでもなく，SNSを見続けた人間の末路を考えて冷や汗を描く

ああいう風になりたくないとオトナを見て思うが，自分を振り返ると1日でアリの一歩ほどしか進んでいない

腕強な宇宙飛行士はどうやって月面着陸を果たしたのか？

紙を42回折り畳めれば到達できる一歩と言うと，とてもcheap

アキレスと亀のごとく無限に続く時間の中で決して追いつけない物語を歩むよりも

空想の中で一足に追い越す寓話を歩みたい

モヤモヤが続く頭の中で，解放できない衝動や感情を使って，

ゼロとイコールで結ぶ作業は果たして意味のないことなのだろうか？

いつも溢れ出てくるこの感情と思考をカタチにする，必要な要素は何も与えてくれない

逃れようがない現実と向き合いながら

今日は控えめな晩御飯をと決心する

https://chatgpt.com/share/67ade009-57d8-8004-9a73-7ab69e376e2e

居酒屋にて（二）

@izakaya

いつぶりに会うかな？

同じグループ会社に勤めていたけど，それぞれ別の子会社に所属していて，拠点が離れていたから面直で会うことはほとんどなかった．

年一回あるかないかの頻度で，どちらからともなく近況をチャット上でやり取りする程度だった．

数年前の同じ年，偶然，当時の勤め先を両者とも退職し，より疎遠になっていたが，ふと先方から連絡が来て，都合よければメシでもという話になった．

久しぶりに会う同僚は生え際あたりが少し薄くなったようだが，今では一児の父親であり，転職当初思い描いていた目標と違えど，安定した業界への再転職を果たし立派に家族を養っているようだ．

「おっ久しぶりっ！」

「いや〜，大人になったなぁ〜笑．てっきり昔のまま中学生みたいな奴が来るってお思ってたよ」

「どういう意味だよっw．俺もう30だぜ．大人っていうか，もう，おっさんの仲間入りよ」

「そっかぁ〜．もう三十かぁ．時間が経つの早いなぁ〜」

そんな会話を交わして，以前と変わらない猫背で迎えてくれた同僚が運転する車で，目的の居酒屋に向かう．

待ち合わせ場所周辺は彼のテリトリーで，おすすめのお店に連れて行ってもらうことに．

渋い店構えの居酒屋へ到着し，この時間帯にしてはガラガラの駐車場に’営業中’なのか心配になりながらも，とりあえず入口へ向かう．助手席を降りて外の冷たい空気に身震いしながら，後部座席を見るとチャイルドシートが見えた．

「あれ，子供いるんすか？」

「いるぅ．言ってなかったっけ？？」

「聞いてない笑．マジかー，パパやんっ．『パパ，おしっこ．．．』」

「おしっこ行きたいの？？」

馬鹿みたいな会話をしながら店先の営業中の文字に安堵する2人．

めちゃくちゃ僕好みの個人店．早くメニューを見たい．

店内は思ったよりも広く，畳座席・カウンター・テーブル席と数十人入るスペースがある．各座席に準備されたメニュー表には定食・海鮮・焼き鳥・豊富な一品料理の数々・おでんのセルフサービスがあり，さらに壁にズラリと並ぶ短冊に書かれたメニューもある．中規模の宴会もできるみたいなので個人店にしては規模が大きい．

僕らが入店した時は貸切状態だったけど，徐々にお客さんは増えていきそれぞれの席で食事を楽しんでいた．

「どこに座る？ここは？」

と僕はテーブル席エリアの中央を指したけど，

「いや，あそこにしよ．」

と窓際の，一番入口から遠い席に座る．

「遠ぉ．．．」

豊富なメニューに感動しながら食事の構成を考えていると，まずは飲み物をと，

ノンアルコールビール，それにレモンサワーを注文する．

彼は車なので今日は飲めない．

「キャバクラに一緒に行った時のこと覚えてる？」

「キャバクラ？いや覚えてないよ．．．ていうか一緒に行ったことない．」

「あれそうだっけ？あれはキャバクラじゃなかったっけ．．．？」

「”相席屋”やろ？」

「あぁ〜，そうだった笑．相席屋だ．相手に（なんか中学生みたいなやつがきたな）って思われてたやつ」

「相席した相手にことごとく惨敗したやつね笑．もう1人同僚と一緒に3人で行って，そいつが「初対面の相手にあんな態度取るのは失礼」って言ってたの覚えてる笑．．．いや仕方ないやん．3人とも顔が良くないんやからって思ったけどね笑笑」

「だぁーはっはははっ笑笑」

懐かしく，こういう時にぴったりの会話に大笑いしながら，暫くして到着したノンアルビールとサワーで乾杯した．

お通しの白和えとセルフサービスのおでんに，もうこれだけで十分ウマいと満足感に浸りながら両者近況を共有しあう．仕事の話や家族の話などなど．．．

仕事の話をしている最中，AIの話になった．

「俺ほんとは，ITやソフトウェアエンジニアの業界にいきたいんよねー．ちょっと前に友達のプログラマーに話聞いて，どうするかもわかってるけど，今取り組んでいる問題っていうか，やっていることが俺には難しくて放置してる．．．」

「君でもそんなことあるの？」

「あるよ，そりゃぁ．俺昔からコードを書くの得意じゃないし．高専生時代，プログラミングの授業とかあったけど，周りに比べて全然かけなかったよ」

「なんか，アルゴリズムはわかるけど．．．例えば，数学の問題の解法をコーディングするとして，頭の中では解けるけど，それをプログラムに落とす際，記述の仕方とか方法が分からんくて詰まるみたいな．でもそれって，プログラムを書かないと上達しないってわかっていてもやってないから，全然ダメやね．．．笑」

「そんなもんなの？俺は全くやったことないから分からないけど．行きたいITの会社に直接連絡とって，数ヶ月無給で働かせてもらってから，今はその会社と契約してるフリーランスの友達いるけど，そういう方法もあるんじゃない？」

「そうやね．それも一つの方法としてありやね．」

「東京に来たらいいやん．その業界の仕事たくさんあるんじゃない？」

「都市部にはめちゃくちゃあるね．実際求人見るとそうやし．でも，九州に住みたいんよねー，って考えると福岡とかね．実際，福岡で別業界から転職してソフトウェアエンジニアしている奴も知ってるし」

「いいじゃん．そういうツテ使えばいけそうじゃない？」

「いけるかもね．でも結局入った後も技術向上させないと置いていかれるだけやから，まぁ今でも言えることやけど，取り組んでいることを進めていくしかないかなと」

「んぅーぅん．あれはどうなよ．AI」

「やばいね．俺も実際使ってるし今朝も簡単な調査に使ったよ．去年くらいからガッと進歩してきてるイメージで，あれは進みが早すぎてついていけない」

「どうなっちゃうのぉ．ああいうの出ると俺って必要ないって思っちゃう．元職場でRPA作ったけど，今は使われてないかなぁ〜？」

「使われてるんじゃない？流石に以前の紙でやり取りしている時代に戻れないっしょ」

「そうかな？難しい話は分からないけど，RPAをやってた時はあらかじめ用意されたパネルを動かして簡単に作れたし，そのー，システムにデータを飛ばすのも簡単にできたけど．AIはシステムへのアクセスとかできるんかね？」

「どうなんやろね？．．．できると思う．今はまだ人による認証ありきでログインするみたいやけど，いずれそれも無しでできるようになるみたい．」

「ヤベェーな〜．そんなことになったらますます俺いらなくなる．．．でも，地震とか災害が起きて電気使えなくなって，それが使えないってなったら人間困っちゃうよね」

「まぁ，そん時はそん時でまた考えればいいじゃない？今は，使える技術があるなら全力で使えば良い．今の仕事でも使う？」

「あれは使ってるよ？ChatGPT．でもこのChatGPTをさっき話したRPAの代わりに使うとしたら，何，チャットでお願いしたら良いってこと？」

「．．．チャットでお願いするっていうより，多分API使ってシステム間にGPTを噛ませてやり取りする感じになる」

「API？？難しいなぁ〜．それをやるとRPAと何が違うの？」

「汎用性が広がるかな．今RPAでやっていることはもちろんできるけど，それを使って別のこともできるみたいな」

「ふぅ〜ん」

「っていうか，そもそもAIって，これまで人類が使ったことない全く新しい技術だから，今の技術を置き換えて使うというより，もっと違う使い方をしていかないといけないと思う．だから，使い方によって人間の在り方も変わっていくと思う．」

「難しいなぁ〜．なんでもできるAIができちゃったら，この先どうなる〜？」

「わからん」

「そのAIを作った人がすごいのか？それともそれを実行できるAI本体がすごいのか？」

「おっ，それは良い問いというか，ジレンマよね．．．良かったなぁ，今日は深いところまで会話できたと思う！」

「そうぉお？？こんなん誰でも思いついてることだと思うよ笑笑」

「いや，少なくとも俺の周りにはいないから笑」

AIの精度の話とかもっと色々な会話をした記憶があるが，酔っ払いの記憶なので信用できなく，飛び飛びの内容になってしまった．

何が言いたいのか．．．？

．．．そんなこと，考える意味ないよね．．．？

それでも．．．何か．．．この先が．．．あ．．．

//

重異能竹

• 自分の認知バイアスを意識する．また相手にも認知バイアスが存在することを認識し対人コミュニケーションをとる．

• 組織は信用できない．年配，属に言う高齢者の話すことも所属によらず信用できない．なぜ，そんな言葉を発することができるのか分からない．
• 昔の話は所詮どうでも良い．今どうしているかを重視する．
• 正義と悪の対立は世代間格差の影響や組織に染まった年数による差が存在する．同じ年代の同僚と束になって一定の悪に染まっている人たちの集団と関わりたくない．
• 場内で理由の説明もなく高圧的な指導態度なおっさんが，場外でも同様な態度をとることに憎しみに近い感情を抱く．もし自分がそれを編集できるとすれば「邪魔だから削除する」
• これは各々の’’’正義と悪’’’という思想が対立する方向の思想？実際に削除する行動をとった時，どちらに傾くか分からないが共感と敵対による衝突が発生すると仮定．そうすると場内権力(対人用圧力の強さ)の衝突に置き換わり，力が強い方が勝利し生き残る．勝者への報酬は相手方の削除で，敗北した方は削除される．
• 集団，利己的個体の群れの幾何学，捕食者に襲われる危険領域は群れの外縁ほど広い．ので，各個体は群れの中心に向かって移動し続ける．
• タカと鳥の一群が存在する．タカは一群に気づいておらず，鳥の一羽がタカに気づく．鳥はそのままじっとしていることもできるが周囲で他の鳥が騒いでいてタカに気づかれる可能性がある．その場から飛び立って木の中に隠れることができれば助かる可能性があるが，群れから孤立する事になる．この鳥はどうすべきか？
• 最善策は，その鳥が飛び立つと同時に他の仲間も同じように飛び立つように仕向けること．「操作」
• ガゼルのストッティング，「こんなに高く飛べる健康的な僕なら君から逃げ切れるから，他の連中を追いかけた方が利口だぞ」
• 女王蜂と子育てワーカー，女王が自分の利益のためにワーカーを操作しているvsワーカーが繁殖虫を自分の利益のために養っている（養殖業の対象にしている）

TBC

AtCoder-ABC150 C問，導出過程 4/n

3/nを下書きのまま放置して数ヶ月と数週間経過．

隙間時間で問題を考えてみるけど，ダッシュしたり，逆立ちしても問題のメインのプログラムがわからず今に至る．

もう，他の人の正しい解答見て理解するしかない．．．

下記参考にした解答例(参照先UserID失念しました，ごめんなさい)

関数 int permutation_rankの動きが分かれば，後は自分のコードと同じ．でも全然理解できない．

試しに順列(3,1,2)の場合のrank,factorの動きを解析してみる．

初期値; i=2の時,jのfor分は条件不成立で動かず，

smaller_count = 0

rank = 1 + 0 * 1 = 1

factor = 1*(3-2) = 1 のまま

i=1の時，perm[j]=2,perm[i]=1でif文不成立で,

smaller_count = 0

rank = 1 + 0 * 1 = 1

factor = 1 * (3-1) = 2 に更新

i=0の時，j=1,2に対しperm[j]<perm[i]=3が成り立ち

smaller_count = 2

rank = 1 + 2 * 2 = 5

factor = 2 *(3-0) = 6 ←これは使われない

以上でプログラムが終了する．

これは，入力例1の解説にある結果と一致するので動作はおそらく正しいと思うけど，なぜこれで辞書順が計算できるのか解らない．

ここで辞書順の定義に立ち返る．問題の注記には

2つの数列 $X, Y$ について、ある整数 $k$ が存在して $X_i = Y_i$$(1 \leq i < k)$かつ $X_k < Y_k$が成り立つとき、$X$は$Y$より辞書順で小さいと定義されます。

とある．

んーでも，X=(1,2)とY=(2,1)で考えてみるとこの定義不成立で辞書順付けれなくない？ってなるのは俺だけ？

でも実際は，Xが1番目でYが2番目となる．理由は数列の1番目からX_k < Y_kが成立するかららしい（．．．$X_i = Y_i$$(1\le i<k)はどこいった？）．$

(3,2,1)の時，rank=7になりそうかなと思ったけど，smaller_countは毎回0に初期化されるので，i=1の時rank=1+1*1=2になり結果6を返す仕組み．

すごい，よくできてる！

頭の中でこの問題を解く場合と違い，コーディングの場合には言語仕様に従って，適宜コードを分けて実装が必要．

今回はsmaller_countとfactorの計算はそれぞれ独立に計算されていて，factorはj番目に入る数の総数を示しているわけではないことを理解する必要がある．

i番目の数より小さい右側の数が何個あるかをsmaller_countに格納して，独立してN!を計算．このfactorが順番の決め手で，for分の最初が1!,2周目が2!になるよう設計されている．iが小さければ小さいほど，factorは大きくなる．

総数＝組み合わせと混同しそうになることを注意．j番目に入る可能性のある数の個数，つまり(N-i)!を計算しrankに足し込んでいる．

[1，2，3]はi番目の右側が小さくなることがないので，rankは増えず初期値の1

[1，3，2]はi=1のとき3より小さい2が右側に存在し，rankに[1，3，2]より小さい順列の数が足し込まれて2になる

[2，1，3]はi=0のとき，j=1の数が小さいので rank = 1+1*2=3となる

…

以下同様

再度factorについて考えると，入力された順列より辞書順で小さい順列の個数を記録している数式になっている．そして，この数式を組めるかどうかがこの問題をCで解けるかどうかに直結しているように思う．

また僕がこの問題に苦戦した理由は，机上での解法をコーディングしようとしたことが誤り．

コーディングでは，殊更，関数や数式のまとまりを無理に関連付ける必要はなく，独立して計算させておいて，結果を算出するときに利用する方が実装上便利だし，実行もできそう．

//$(1 \leq i < k)$

AtCoder-ABC150 C問，導出過程 3/n

tatk.hatenadiary.com

表題の件，続き

具体例を示しながらこの問題の理解をさらに深める(コード書く前にやるべき!!!)

n=3の時，生成される順列と辞書順

(1,2,3), 1

(1,3,2), 2

(2,1,3), 3

(2,3,1), 4

(3,1,2), 5

(3,2,1), 6

組み合わせの総数はn!で与えられるので，3!=6通り

n=4の場合，4!=24通り

☆1配列s[0]の数字につき(n-1)!個の順列が生成される．．．これ順列生成に使えそう

　→int j=0;と置いて，j=n-1になるまで順列を生成する

☆2 s[0]にくる数字を生成する順番は[0]⇄[2],[0]⇄[1]の順．．．これは☆1より先に条件分岐させる必要があるので，コード的には☆2{☆1}の形になる

・・・

記事の書き初めから数日経ってしまった．ので，支離滅裂な読みにくい文章になっているかもしれないけど，ごめんなさい．

とりあえず昇順ソート関数をpermuteにぶっ込んで結果を表示してみた．

#include<stdio.h>
#include<stdlib.h>

  int n;
  int p[10],q[10],s[10];
  int y,z,count=1;
  
  // 配列の要素をスワップする関数
  void swap(int *a, int *b) {
      int temp = *a;
      *a = *b;
      *b = temp;
  }
  
  // 昇順ソート関数
  int compare(const void *c, const void *d){
    return (*(int *)c - *(int*)d);
  }

  // 配列が等しいか確認する関数
  int is_equal(int a, int b){
    for (int i = 0; i < n; i++){
      if (a[i] != b[i]) return 0;
    }
    return 1;
  }

  //順列を生成し，辞書順の位置を確認する関数
  void permute(int arr[], int l, int r) {
    if(l==r){
      qsort(arr+1,n-1,sizeof(int),compare);
      if (is_equal(arr, p)) y = count;
      if (is_equal(arr, q)) z = count;
      count++;
      return;
    }
    for (int i = l; i <= r; i++) {
        swap(&arr[l], &arr[i]);
        permute(arr, l + 1, r);
        swap(&arr[l], &arr[i]);  // 元に戻す
    }
  }

int main() {
  scanf("%d",&n);
  for(int i=0; i < n; i++) {
    s[i] = i + 1;
  }
  for(int i=0; i < n; i++){
    scanf("%d",&p[i]);
  }
  for(int i=0; i < n; i++){
    scanf("%d",&q[i]);
  }
  permute(s,0,n-1);
  printf("%d %d\n",y,z);
  printf("%d\n",abs(y-z));
  return 0;
}

入力

3
1 2 3
1 3 2

出力

6 0
6

全っ然違うけど，カウント総数は意図通りなので，if(l==r)条件分はこれで良いっぽい．後はどうやって要素0番目swap直後の新しい順列を昇順ソートにかけるか．．．