しずくぶろぐ

競技ぷろぐらみんぐしたり、なんかしたりします

不定期解説記事企画 ARC008-D タコヤキオイシクナール #雫ぷよ

こんにちは。研究室の先輩と仲良くなった気がする綿谷雫です。今日は ARC008Dの解説をしたいと思います。

今回はあるものを試したいと思って解いたものなので思考回路的なものはないです。ネタバレを聞かずに過ごしたい人はブラウザバックをしてください

続きを読む

不定期解説記事企画 第一回 アルゴリズム実技検定 過去問 F #雫ぷよ

御機嫌よう、一週間かけて作った試料が壊れてしまったのでちょっとさげぽよの綿谷雫です。今日は第一回 アルゴリズム実技検定 過去問 Fの解説をします。

問題のリンクは下に貼っておきます。

atcoder.jp

いっぱいコンパイルエラーが出ました。

問題概要

単語がくっついた文字列が与えられるので単語で区切って並び替えて出力してね、という問題です。

解答までの道程

とりあえず大文字のところで区切られているようなので、大文字かどうか調べる関数を作ります。

logical function Omoji(x)
character(1)::x
Omoji=(ichar(x)>=ichar("A").and.ichar(x)<=ichar("Z"))
end function

大文字かどうか確認するすべを手に入れたところで、単語を配列にしてみます。

    character(10**5)::S
    character(10**5)::W(1:10**5)
    integer::WS,WE,Wcnt
    integer::i
    read*,S
    WS=1;Wcnt=0
    do i=1,len_trim(S)
        if(i==WS)cycle
        if( Omoji(S(i:i)) )then
            WE=i
            Wcnt=Wcnt+1
            W(Wcnt)=S(WS:WE)
            WS=WE+1
        endif
    end do

これでWに単語一つ一つをいれることができました。これをヒープソートしてやればできるはずです。

サンプルで試してみました。

FisHDoGCaTAAAaAAbCAC を入力すると AAACAaAAbCCaTDoGFisH が出てきました。 答えは AAAaAAbCACCaTDoGFisH なのでちょっとおかしいですね。ACがAaAよりも先にきてしまっています。これはCが大文字だからでしょう。ヒープソートをする時は全部小文字にしてやって比較する必要があるんですね。

というわけで突っ込むときに小文字になるようにしました。

    do i=1,len_trim(S)
        if(i==WS)then
            S(i:i)=char(ichar(S(i:i)) -ichar("A")+ichar("a") )
            cycle
        endif
        if( Omoji(S(i:i)) )then
            WE=i
            Wcnt=Wcnt+1
            S(i:i)=char(ichar(S(i:i)) -ichar("A")+ichar("a") )
            W(Wcnt)=S(WS:WE)
            WS=WE+1
        endif
    end do

サンプルも合ったしこれで大丈夫、、、? 

f:id:kapt0nH:20200919234945p:plain
コンパイルエラーが出ました。

Main.f08:(.text+0x44): relocation truncated to fit: R_X86_64_PC32 against `.bss' で調べてみるとメモリを使いすぎてるようなことがわかります。確かに出てくる単語の長さも個数も分からないからといって100000文字の単語を100000個記憶させるのは無理がありそうです、、、

記憶量を減らすにはまず単語の量を測ってからその分だけメモリを確保すればいいんでしょうか? 単語の長さが事前に分からないのでfortranではそこまでメモリの確保量はかわらなそうです。

そもそも文字列Sがあるのに同じようなことをいちいち記憶する必要はなさそうです。各単語の最初の文字の位置と最後の文字の位置だけを記録して並び替えることにしましょう。

    type WSWE
        integer::H,O
    end type

(H)初めの文字と(O)終わりの文字をセットにして記憶させます。これをヒープソートにかけます。ヒープソートの中の比較演算子をいちいちいじりたくないのでオーバーロードを使います。(BADやNICEでもコンボが続きそうですね)

    interface operator (<)
        module procedure lessWSWE
    end interface operator (<)

 
logical function lessWSWE(X,Y)
    type(WSWE),intent(in)::X,Y
    lessWSWE=S(X%H:X%O)<S(Y%H:Y%O)
end function

比較演算子は<だけやっておけば<=とか>もよしなにしてくれるみたいですね。

ともかくこうしてACすることができました。

実装

module WSWE_mod
    character(10**5)::S
    type WSWE
        integer::H,O
    end type
    interface operator (<)
        module procedure lessWSWE
    end interface operator (<)
contains
 
logical function lessWSWE(X,Y)
    type(WSWE),intent(in)::X,Y
    lessWSWE=S(X%H:X%O)<S(Y%H:Y%O)
end function
end module 
program PAST
    use WSWE_mod
    implicit none
    integer::WS,WE,Wcnt,Wnum=0
    type(WSWE),allocatable,dimension(:)::W
    integer::i
    read*,S
    do i=1,len_trim(S)
        if( Omoji(S(i:i)) )WNum=Wnum+1
    end do
    Wnum=Wnum/2
    allocate(W(Wnum))
 
    WS=1;Wcnt=0
    do i=1,len_trim(S)
        if(i==WS)then
            S(i:i)=char(ichar(S(i:i)) -ichar("A")+ichar("a") )
            cycle
        endif
        if( Omoji(S(i:i)) )then
            WE=i
            Wcnt=Wcnt+1
            S(i:i)=char(ichar(S(i:i)) -ichar("A")+ichar("a") )
            W(Wcnt)%H=WS
            W(Wcnt)%O=WE
            WS=WE+1
        endif
    end do
    call heapsort(Wnum,W(1:Wcnt))
    do i=1,Wnum
        write(*,"(A)",advance='no') char(ichar(S(W(i)%H:W(i)%H)) -ichar("a")+ichar("A") )
        write(*,"(A)",advance='no') S(W(i)%H+1:W(i)%O-1)
        write(*,"(A)",advance='no') char(ichar(S(W(i)%O:W(i)%O)) -ichar("a")+ichar("A") )
    end do
contains
logical function Omoji(x)
character(1)::x
Omoji=(ichar(x)>=ichar("A").and.ichar(x)<=ichar("Z"))
end function
subroutine heapsort(n,array)
  implicit none
!ここの入力は状況に応じて変更すること
  integer,intent(in) :: n
  type(WSWE),intent(inout) :: array(1:n)
  integer::i,k,j,l
  type(WSWE):: t
 
  l=n/2+1
  k=n
  do while(k /= 1)
     if(l > 1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k == 1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j<=k)
        if(j < k)then
           if(array(j) < array(j+1))j=j+1
        endif
        if (t < array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
  enddo
  return
end subroutine heapsort
 
end program PAST

おしまい。

参考

amanotk.github.io

院試受験記

院試に無事合格できたので受験記を書きます.

院試準備

4年生にあがるまでは院試対策は特に何もしませんでした.事前に受けたTOEFLの成績が使えるということだったので,TOEFLを受けようかどうしようかという話を3年の秋学期に友達とした程度です.

4年生の春学期前半は授業を演習など週3コマだけとり,残りの時間は研究室のミーティングとか卒論中間発表のための論文を読んで過ごしていました.

5月にTOEFLを事前に受けないといけないことが知らされたので,緊急事態宣言解除後すぐにパスポートなり何なりを揃えてあわてて申し込みをしました.クレジットカードを持っていなかったので母上に頼んで受験料を払ってもらい,なんとか7月の初めの中間発表が終わってから一週間後の会場でのTOEFLの予約を入れることができました.中間発表前からTOEFLの勉強をしておきたかったのですが,中間発表の準備に結構時間をとられたので結局直前一週間にTOEFLの勉強をしました.TOEFLの勉強には試験をやる団体が出してる太いやつを使いました.うちにでーぶいでーを再生できるものがなかったので研究室からパソコンを借りて勉強をしました.

中間発表とTOEFLが終わってからは院試勉強に集中しました*1.7月の中旬あたりにオンライン試験に必要なものがしらされ,机の上におけて自由に角度を変えられる鏡と外付けの机の上のどこにでもおけるwebカメラと封筒を用意しないといけないことがわかりました.鏡と封筒は百円ショップで,webカメラはクレジットカードを作ってあまぞんでぽちりしました.webカメラはえれこむの二千円から三千円くらいのものです.

院試本番

オンラインでの試験なので試験環境のチェックがありました.チェックでは手元と目線が入るようにwebカメラをセットするように言われたのですが,カメラが広角ではなかった故に机の上に置いても手元と目線どちらかが外れてしまうので,机の横に台を用意してwebカメラを置かないといけませんでした.

筆記試験では問題をパソコンでずっと見ないといけないので目が疲れました.

口述試験では,筆記試験と同じような環境を用意したのですが外付けwebカメラを使わなかったので意味のない用意でした.

後日,発表をネットで見て合格を確認しました.

ちゃんちゃん.

あどばいす的なまとめ

  • TOEFLとかは突然求められる
  • クレジットカードを用意しておくとオンラインで簡単に支払いができる
  • 鏡は100円ショップにある
  • webカメラは写す範囲も重要
  • オンラインで問題を見るのと紙で問題見るのとは違う
  • 口述試験はそこまで環境を求められなかった

*1:研究室によっては実験をさせられたりしたところもあったそうなので,研究室選びのポイントかもしれないですね

運転免許の更新に行ったよ

ごきげんよう、手続きの苦手な綿谷雫です。

今日はもう手放せない身分証であるところの運転免許の更新に行ってきました。

当日まで

免許の更新が近いよーという葉書が9月の初めにやってきました。運転免許取ったのは2年生の5月だし、もうそんな時期かー、と思いながら葉書が届いて次の次の日くらい(9/3)に行こうとしたのですが、更新できる日が誕生日(10/4)の1ヶ月前(9/4)からだと葉書に書いてあることに(9/3に)気付き、予定を変更しました。

9/4は大学行きたかったのと土曜日は免許更新やってくれないのと日曜日は眠かったのとで今日(9/7)免許更新に行くことにしました。

持ち物

持って行ったのは

  • 免許証
  • 葉書
  • 手数料
  • バッグ
  • 交通費
  • マスク

です。手数料はぴったり持って行ったほうがいいかなと思ってわざわざ諭吉崩して持っていったんですが、前の人はお釣りもらってました。

 

持ち物とは違いますが、4桁の暗証番号を2つ考えておく必要があります。

当日

午後2時までに受付を済ませなさい、と葉書に書いてあったので午後1時半くらいに免許センターに行きました。

 

誘導されるままに受付行って申請書もらって名前書いたり質問表を埋めたりしました。名前の文字が汚かったのか一字緑の鉛筆で注意が入りました。名前は綺麗に書きましょう。

 

申請書を書き終えたら手数料払って視力検査して写真を撮ります。視力検査で絶対右だろと思ったやつが上だったので自分の目が信じられなくなりました(でもなんかokだった)。

 

写真を撮り終えると細長いぴろぴろした紙が渡されるのでそれを持って講習を受けに行けと言われます。

 

講習

講習を受ける部屋にいくと部屋が満席になるまで待ってくださいと言われるので2時10分くらいまで待ちました。多分この日最後の講習だし2時に受付にきた人まで待ったんでしょうね。RTAする場合は受付に行く時間を変えた方が良さそうです。

待って部屋がいっぱいいっぱいになったら講習が始まります。講習中水は飲んでもいいですとか言われたので、ペットボトルの飲み物何か持っていくといいと思います。あと運転適正チェックみたいなのがありますが途中でやる時間があるので急いでやらなくていいです。

 

間休憩時間挟んで4時ちょっとすぎになったら終わりました。肝心の講習内容ですが、危ない運転はやめようという話でした。飲酒運転やら煽り運転のときは危険そうなBGMだったのに、夕方の運転だけプラネタリウムっぽいBGMで「薄暮です」とか言うので選曲って大事だと思いました。

 

講習が終わったらスタンプもらったぺらぺらの細長い紙を提出すると新しい免許がもらえました。これで安心して身分証明が出来ます。

 

おしまい。

単語帳を作った。

中二くらいから知らなかった英単語を小さいノートに書き溜めておいてたまに見返す、ということを繰り返して 単語を覚えようとしていました。 しかし、ノートに書くとどこに何を書いたか分からず、 うっかり同じ単語を入れてしまうことがありました。

中学生高校生のころは辞書に載っていない単語を調べることはほとんどなかったので、 辞書に調べたよマークをつけておけば、過去に調べていたのを忘れていたのに気づくことができていたのですが、 大学に入って専門の論文を読み始めると 辞書に載っていない単語もが多くなり同じ単語を何回も調べていることに気づきづらくなってきました。

そこで 知らなかった単語だけを辞書順で並べてくれる単語帳 があったらいいなぁと思い、探したのですが、あんまりいいのがなかった*1ので、 エクセルで作りました。

追加したい単語の綴りと意味を太字で囲ったところに入力して追加ボタンを押すとアルファベット順に並んでくれます(Fig.1,2)。

f:id:kapt0nH:20200719001557p:plain
Fig.1 知らなかった単語の綴りと意味を入力して追加ボタンをクリック
f:id:kapt0nH:20200719001744p:plain
Fig.2 アルファベット順に並べてくれる

綺麗に並んでくれると嬉しいですね。

問題はこのシートを開くのが面倒ということです。

作り方

Mac用のエクセル(バージョン16.39)を使っています

  1. エクセルを開きます。
  2. ツール>マクロ>Visual Basic Editor でなんかプログラマーっぽい画面にします.
  3. コードを書きます
Sub Narabikae()
     Range(" B7").CurrentRegion.Sort _
     key1:=Range("B7"), Order1:=xlAscending, _
     key2:=Range("C7"), Order2:=xlAscending, _
     Header:=xlYes
End Sub

 Sub Plus()
    Range("B1048576").End(xlUp).Offset(1).Select
    ActiveCell.FormulaR1C1 = Range("B4").Value
    Range("C1048576").End(xlUp).Offset(1).Select
    ActiveCell.FormulaR1C1 = Range("C4").Value
    Call Narabikae
     Range(" B4").ClearContents
     Range("C4").ClearContents
 End Sub
  1. エクセルシートに戻って、挿入で、ボタン用の四角形を作ります。
  2. 作った四角形をクリックして、「マクロの登録」でPlusを登録します
  3. できあがり

コードの説明

Narabikae(並び替え)
Sub Narabikae()
     Range(" B7").CurrentRegion.Sort _
     key1:=Range("B7"), Order1:=xlAscending, _
     key2:=Range("C7"), Order2:=xlAscending, _
     Header:=xlYes
End Sub

並び替えてくれるマクロです

セルB7を含むひとまとまりのグループを並び替えします

     Range(" B7").CurrentRegion.Sort _

比較するのはB7が含まれている列で、順番はAからZです。 一番最初の行は見出しなので並び替えません。

     key1:=Range("B7"), Order1:=xlAscending, _
     key2:=Range("C7"), Order2:=xlAscending, _
     Header:=xlYes
Plus(追加)
 Sub Plus()
    Range("B1048576").End(xlUp).Offset(1).Select
    ActiveCell.FormulaR1C1 = Range("B4").Value
    Range("C1048576").End(xlUp).Offset(1).Select
    ActiveCell.FormulaR1C1 = Range("C4").Value
    Call Narabikae
     Range(" B4").ClearContents
     Range("C4").ClearContents
 End Sub

実際に追加します

B列のシートの一番下から何か入力されているところまで上がってきて一個下がったセルを選択します

    Range("B1048576").End(xlUp).Offset(1).Select

選択したセルにB4セルの値を入れます

    ActiveCell.FormulaR1C1 = Range("B4").Value

並び替えを呼び出します

   Call Narabikae

入力欄の内容を消します

     Range(" B4").ClearContents

*1:単語カードは嵩張って好かない

TOEFL を受けたよ

院試のためにTOEFL iBT を受けてきました。帰りのエレベーターで一緒だった人と喋ったりできていい感じでした。

 

申し込み

ETSアカウントを作って申し込みをしました。料金の支払いにクレジットカードを使うとスムーズなのですが持ってなかったのでクレジットカードを持っている母上に頼んで試験料を払ってもらいました。クレジットカードを早く作らねばなー。会場は西新宿のにしました。

 

当日

30分前についておいてねって書いてあったので1時間前くらいに試験会場につくように家を出ました。持ち物としてパスポートと予約情報印刷した紙と休憩用のゼリー(と電車賃と携帯)をバッグに入れて持って行きました。

 

試験会場への行き方をGoogle mapで調べたらclosedと書いてあった上に、実際行ってみると入り口がよく分からなかったので、まさか某ウイルスで大変だからテスト中止!? と焦りました。ビルに入って管理員っぽい人に「TOEFL受けたいんですけど〜」って言ったら「そこのエレベーターで6Fいきゃいいよ」と優しく教えてもらえました。Google mapの情報は特に関係ないっぽいです。

 

会場にいくと予約番号を訊かれたので印刷しておいた紙を見て答えました。印刷しておいてよかったよかった。

 

あとはなんか適当に指示に従ってたらテストが始まって、なんだかんだでテストが終わりました。

 

10分の休憩時間でなにをしていいか分からずゼリーを食べ損ねたので終わってから20秒チャージしました。

gnuplotでグラフを書いた #雫ぷよ

いつも試行錯誤しながらgnuplotを使っているので自分用にまとめます。

set terminal postscript eps enhanced
eps_file = "2_3.eps";
unset label 
set output eps_file
#eps fileで出力

set key font ",25"

set xlabel "k_x" font "Arial,30"
set ylabel "k_y"font "Arial,30"
#x軸 y軸の名前

set tics font "Arial,20"


set autoscale
#サイズを適当に

set size ratio -1
#軸のスケールを同じに

set parametric
#媒介変数表示

set xrange[-6:6]
set yrange[-6:6]
#グラフの範囲を指定

set xtics ('{/Symbol p}/a' pi,'0' 0, '-{/Symbol p}/a' -pi)
set ytics ('{/Symbol p}/a' pi,'0' 0, '-{/Symbol p}/a' -pi)
#目盛に数値をつける
#ギリシア文字も/Symbol ほにゃららで打てる

set label 1 "{/Symbol G}" font 'Arial,30' point pt 31 at 0,0
set label 2 "M" font 'Arial,30' point pt 31 at pi,pi
set label 3 "X" font 'Arial,30' point pt 31 at pi,0

plot [0:2*pi] (3*pi*pi)**(1.0/3)*cos(t),(3*pi*pi)**(1.0/3)*sin(t) with l lw 3 lt 1 title "circle",\
 pi,-pi+t with l lw 3 lt 2 notitle,\
 -pi,-pi+t  with l lw 3 lt 2 notitle,\
 -pi+t,pi with l lw 3 lt 2 notitle,\
-pi+t,-pi  with l lw 3 lt 2 title  "square"

#プロット、複数の線をプロットする場合は","で区切る。長くなって見辛いときは \で改行

このテキスト(名前をgraph1とする)を持っておいてターミナルで

gnuplot> load "graph1"

とすればepsファイルが吐き出されている。

f:id:kapt0nH:20200601180043p:plain

次の目標としてはデータを取得してからグラフを作るまでをFortranか何かでやってもらいたい